Привет, Хабр! Центр развития ИТ-образования МФТИ приглашает тебя на международный студенческий чемпионат по спортивному программированию MosCode Festival. Это хорошая возможность потренироваться на задачах уровня финала ACM ICPC вместе с участниками из других стран. Контест пройдёт 31 марта (личный тур) и 1 апреля (командный тур) в технопарке «Сколково». Онлайн-отбор пройдёт в ближайшее воскресенье, 11 февраля, в 11:00 по московскому времени. Пока вы думаете о регистрации, рассказываем подробности и делимся двумя задачами прошлого года с разбором.
MosCode Festival, ранее известный как Московский фестиваль по спортивному программирования Кубка им. И. Н. Векуа, является значимым мероприятием в мире олимпиадного программирования. В прошлом году на фестиваль приехали 200 человек из 19 стран, в том числе впервые участвовали команды из Австралии, Японии и Испании. В этом году ожидаются 360 студентов из 40 стран. На данный момент заявку на участие подали команды из Канады, Индии, Великобритании, Китая и Бразилии.
А теперь разминка.
Задача «Нечто с точками и прямоугольниками»
Задача «Игра на поле»
Задача «Нечто с точками и прямоугольниками»
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 3 секунды
Ограничение по памяти: 256 мегабайт
На плоскости дан набор из n различных точек с целочисленными координатами. Назовем прямоугольник хорошим, если его углы находятся в точках с целочисленными координатами, и все точки с целочисленными координаты внутри и на границе принадлежат данному набору. При этом такой прямоугольник может быть и вырожденным (иметь нулевую площадь). Для каждой точки нужно найти количество хороших прямоугольников, которым она принадлежит.
Формат входных данных
В первой строке записано число n (1 ⩽ n ⩽ 10^5) – количество точек. В следующих строках записаны координаты точек (−10^5 ⩽ xi,yi ⩽ 10^5)
Формат выходных данных
Выведите n строк. В i-й строке должно быть записано количество хороших прямоугольников, содержащих i-ю точку.
Примеры
| стандартный ввод | стандартный вывод |
|---|---|
| 4 -1 -1 -1 -2 -2 -1 -2 -2 |
4 4 4 4 |
| 8 1 1 1 2 1 3 2 1 2 3 3 1 3 2 3 3 |
5 4 5 4 4 5 4 5 |
Разбор задачи «Нечто с точками и прямоугольниками»
Наивное решение за O(n^3) Переберем два противоположных угла прямоугольника, проверяем, что он хороший. Если хороший, то для каждой точки проверяем, принадлежит ли она этому прямоугольнику. Если принадлежит, увеличиваем ответ для точки на единицу.
Решение за O(n^2) Кратко: мы хотим перебрать любой горизонтальный отрезок из точек в наборе и посчитать в скольких прямоугольниках со стороной, равной длине отрезка, он лежит.
Сначала за O(nlogn) предподсчитаемдлякаждойточкиеенепосредственноговерхнего, нижнего и правого соседа. Затем за линию считаем toright[i] = 1 + количество точек подряд справа от i-й точки.
Перебираем длину отрезка len. Считаем за линию up[i] и down[i] для каждой точки up[i] = 0 если toright[i] < len up[i] = 1 + количество точек подряд сверху с toright[i] >= len, иначе down[i] аналогично для точек снизу. Тогда горизонтальный отрезок длиной len, начинающийся в i-й точке лежит в up[i] * down[i] прямоугольниках со стороной len. Как пересчитать ответ для всех точек на отрезке? Давайте хранить точки отсортированными по (y, x) и затем прибавлять на отрезке с помощью префиксных сумм.
Решение за O(n√n) Модифицируем предыдущее решение. Будем перебирать не только горизонтальные, но и вертикальные отрезки. Но при этом не рассматривать отрезки, длина которых совпадает с большей стороной прямоугольника. Следовательно, нам не придется перебирать отрезки с длиной больше √n При этом нужно не считать квадраты два раза. Это можно сделать, запустившись сначала по горизонтальным отрезкам, считая квадраты, а потом по вертикальным, не считая квадраты.
При этом усложняется формула количества прямоугольников. Нам нужно считать количество прямоугольников, со стороной не меньше зафиксированного отрезка. Так что теперь нам даны какие-то числа up, down, cut и нужно считать количество пар целых чисел (i, j), где 1 ⩽ i ⩽ up,1 ⩽ j ⩽ down,i + j > cut
Если cut ⩽ up, то для всех i = cut,..,up подходят любые j. Прибавляем к ответу (up−cut + 1)·down, присваиваем up := cut−1 и дальше считаем, что up < cut ∑up i=1∑down 1 (1,i + j > cut) =∑up i=1 max(0,down−(cut−i)) =∑up i=max(1,cut−down) (down−cut + i)
Обозначим l = max(1,cut − down), r = up. Если l ⩽ r, то к ответу нужно прибавить (r−l + 1)·(down−cut) + (r·(r + 1)/2−(l−1)·l/2)
Решение за O(n^2) Кратко: мы хотим перебрать любой горизонтальный отрезок из точек в наборе и посчитать в скольких прямоугольниках со стороной, равной длине отрезка, он лежит.
Сначала за O(nlogn) предподсчитаемдлякаждойточкиеенепосредственноговерхнего, нижнего и правого соседа. Затем за линию считаем toright[i] = 1 + количество точек подряд справа от i-й точки.
Перебираем длину отрезка len. Считаем за линию up[i] и down[i] для каждой точки up[i] = 0 если toright[i] < len up[i] = 1 + количество точек подряд сверху с toright[i] >= len, иначе down[i] аналогично для точек снизу. Тогда горизонтальный отрезок длиной len, начинающийся в i-й точке лежит в up[i] * down[i] прямоугольниках со стороной len. Как пересчитать ответ для всех точек на отрезке? Давайте хранить точки отсортированными по (y, x) и затем прибавлять на отрезке с помощью префиксных сумм.
Решение за O(n√n) Модифицируем предыдущее решение. Будем перебирать не только горизонтальные, но и вертикальные отрезки. Но при этом не рассматривать отрезки, длина которых совпадает с большей стороной прямоугольника. Следовательно, нам не придется перебирать отрезки с длиной больше √n При этом нужно не считать квадраты два раза. Это можно сделать, запустившись сначала по горизонтальным отрезкам, считая квадраты, а потом по вертикальным, не считая квадраты.
При этом усложняется формула количества прямоугольников. Нам нужно считать количество прямоугольников, со стороной не меньше зафиксированного отрезка. Так что теперь нам даны какие-то числа up, down, cut и нужно считать количество пар целых чисел (i, j), где 1 ⩽ i ⩽ up,1 ⩽ j ⩽ down,i + j > cut
Если cut ⩽ up, то для всех i = cut,..,up подходят любые j. Прибавляем к ответу (up−cut + 1)·down, присваиваем up := cut−1 и дальше считаем, что up < cut ∑up i=1∑down 1 (1,i + j > cut) =∑up i=1 max(0,down−(cut−i)) =∑up i=max(1,cut−down) (down−cut + i)
Обозначим l = max(1,cut − down), r = up. Если l ⩽ r, то к ответу нужно прибавить (r−l + 1)·(down−cut) + (r·(r + 1)/2−(l−1)·l/2)
Задача «Игра на поле»
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 64 мегабайта
Иннокентий решил поиграть в следующую забавную игру: Дано поле N x M клеток (высота — N клеток, ширина — M клеток). Пусть клетка (x, y) — это клетка в x-м ряду и y-м столбце (ряды нумеруются сверху-вниз, а столбцы слева-направо). Изначально в клетке (1, 1) лежит S камней (S >= 4), нужно эти камни переместить в клетку (N, M). Игра поделена на ходы, каждый ход Иннокентий должен из каждой клетки поля какую-то часть камней переместить на 1 клетку вверх/вправо/вниз/влево, а какую-то часть оставить в данной клетке, части могут быть нулевыми (не содержать ни одного камня), также сумма по количеству камней в частях должна равняться изначальному количеству камней в клетке, а также камни не могут выходить за границы поля. Стоит заметить, что Иннокентий применяет передвижения для всех клеток одновременно.
Формальные правила: Пусть до совершения хода в i-й строке, j-м столбце будет a[i][j] камней, и пусть правило перемещения камней для этой клетки задается 4-мя числами: b[i][j][0], b[i][j][1], b[i][j][2], b[i][j][3] — количество камней которое переместиться из клетки (i, j) в клетку (i — 1, j), (i, j + 1), (i — 1, j), (i, j — 1) соответственно (b[i][j][0] + b[i][j][1] + b[i][j][2] + b[i][j][3] <= a[i][j]). Пусть после совершения хода в i-й строке, j-м столбце будет с[i][j] камней тогда
с[i][j] = a[i][j] — (b[i][j][0] + b[i][j][1] + b[i][j][2] + b[i][j][3]) + b[i + 1][j][0] + b[i][j — 1][1] + b[i + 1][j][2] + b[i][j + 1][3]. Считаем, что b[i][j][k] = 0, для i, j выходящих за пределы (1..N) и (1..M) соответственно. Игра считается выигранной, если существует ход с номером меньшим либо равным H, такой что, на этом ходу b[N][M] станет равным S, и после этого хода не будет совершаться никаких перемещений.
*Ходы пронумерованы от 1-го до H-го.
Однако Иннокентий быстро понял, что данная игра является слишком простой для него. И он придумал себе некоторые ограничения, для усложнения игры. Во первых, теперь вместо того, что-бы задавать правило для каждой отдельной клетки, он теперь задает правило для каждого возможного количества камней в клетках, то-есть для каждого z (количество камней в клетке), придумывает правило, состоящие из 4-х чисел: d[z][0], d[z][1], d[z][2], d[z][3]. И тогда на каждом ходу происходит перемещения камней по «формальным правиламно b[i][j][k] = d[a[i][j]][k] для всех i, j, k. Также b[i][j][k] = 0, вне зависимости от d[a[i][j]][k], если для данных i, j, k клетка куда должны переходить b[i][j][k] камней выходит за границы поля.
Вскоре Иннокентию наскучила игра и с такими ограничениями, и поэтому он захотел разобраться с данной игрой раз и навсегда придумав такую стратегию (то-есть такие d[z][0], d[z][1], d[z][2], d[z][3] для каждого z), которая будет выигрывать игру при всех возможных полях (то-есть для всех N, M: 1 <= N <= MAXN, 1 <= M <= MAXM), и при всех возможных начальных количествах камней (то-есть для всех S: 4 <= S <= MAXS).
Формат входных данных
На вход ничего не подается.
Формат выходных данных
Вывести MAXS строк, i-я строка должна состоять из 4-х чисел разделенных пробелами: d[i]][0], d[i][1], d[i][2], d[i][3]. Данные строки должны описывать стратегию, которая будет выигрывать игру для всех начальных данных, таких что:
1 <= N <= MAXN
1 <= M <= MAXM
MAXN = MAXM = 50
4 <= S <= MAXS
MAXS = 100 H = 300
Замечание
Пример возможной стратегии:
Для всех i: d[i][0]=0,d[i][1]=i,d[i][2]=0,d[i][3]=0, данная стратегия задает движение всех камней на 1 клетку вправо, несложно понять что данная стратегия выигрышна, для всех однострочных полей, и проигрышна для всех остальных.
Разбор задачи «Игра на поле»
В данной задаче существует 2 различных подхода к решению задачи.
1. Чисто математический подход — пытаемся придумать какую-то стратегию, которая будет удовлетворять всем условиям. Данных стратегий довольно много, однако у большинства из них есть много крайних случаев, которые нужно обработать отдельно. Пример одной из стратегий, и рассуждения, которые привели к ее придумыванию указаны ниже.
2. Написать перебор стратегий, с некоторыми отсечениями, и тестером, который будет проверять правильность решения. В таком случае решение находится довольно быстро, и к тому же гарантируется правильность стратегии.
Код:
Пример выигрышной стратегии:
Код: Описание: Пусть z — количество камней в некой клетке. Рассмотрим несколько соображений:
1. Если z ⩾ 4, то из этой клетки камни могут двигаться, только вправо и вниз, так-как в противном случае, при S = z, все S камней никогда не останутся лежать в нижней правой клетке.
2. Если z ⩾ 4, то какая-то не нулевая часть камней обязательна должна идти вправо, и какая-то не нулевая часть должна идти вниз, так-как в противном случае, при S = z, мы проиграем в таблицах состоящих из 1-й строки, или 1-го столбца.
3. Если количество камней, лежащих изначально в левой верхней клетки ⩾ 4, то можно считать значения 1, 2, 3 некоторыми базовыми частями, при помощи которых мы будем разбивать большие части.
На основании данных соображений и некоторых предположений можно прийти к стратегии следующего вида. Основная часть камней (назовем ее T) идет вниз, и на каждом ходу она отделяет от себя несколько базовых частей. 1 и 2 будут полностью передвигаться вправо, а 3-ка будет передвигаться полностью вниз, идея стратегии в том, что-бы выделять из T части 1 и 2, а 3-ки должны собираться только на правой границе, откуда они уже придут внижнюю клетку. ПустьT, состоящая из z камней делится таким образом:
• вниз идет основная часть без 3-х камней, то-есть z — 3 камня;
• вправо идет 2 камня;
• в данной клетке остается 1 камень.
Тогда единицы и двойки будут идти вправо, пока не соберутся в 3-ку н аправой границе. Однако в данной стратегии есть изъяны, а именно она не будет работать для маленького z. Например потому-что 6-ка по такой стратегии разделиться на 2, 1 и 3, и 3-ка пойдет вниз, хотя она и находиться пока на левой границе, поэтому еще нужно аккуратно рассмотреть количества камней от 4-х до 6-и, а остальные будут распадаться на базовые части и части ⩾ 4.
В итоге получаем такую стратегию:
1. Чисто математический подход — пытаемся придумать какую-то стратегию, которая будет удовлетворять всем условиям. Данных стратегий довольно много, однако у большинства из них есть много крайних случаев, которые нужно обработать отдельно. Пример одной из стратегий, и рассуждения, которые привели к ее придумыванию указаны ниже.
2. Написать перебор стратегий, с некоторыми отсечениями, и тестером, который будет проверять правильность решения. В таком случае решение находится довольно быстро, и к тому же гарантируется правильность стратегии.
Код:
Пример выигрышной стратегии:
Код: Описание: Пусть z — количество камней в некой клетке. Рассмотрим несколько соображений:
1. Если z ⩾ 4, то из этой клетки камни могут двигаться, только вправо и вниз, так-как в противном случае, при S = z, все S камней никогда не останутся лежать в нижней правой клетке.
2. Если z ⩾ 4, то какая-то не нулевая часть камней обязательна должна идти вправо, и какая-то не нулевая часть должна идти вниз, так-как в противном случае, при S = z, мы проиграем в таблицах состоящих из 1-й строки, или 1-го столбца.
3. Если количество камней, лежащих изначально в левой верхней клетки ⩾ 4, то можно считать значения 1, 2, 3 некоторыми базовыми частями, при помощи которых мы будем разбивать большие части.
На основании данных соображений и некоторых предположений можно прийти к стратегии следующего вида. Основная часть камней (назовем ее T) идет вниз, и на каждом ходу она отделяет от себя несколько базовых частей. 1 и 2 будут полностью передвигаться вправо, а 3-ка будет передвигаться полностью вниз, идея стратегии в том, что-бы выделять из T части 1 и 2, а 3-ки должны собираться только на правой границе, откуда они уже придут внижнюю клетку. ПустьT, состоящая из z камней делится таким образом:
• вниз идет основная часть без 3-х камней, то-есть z — 3 камня;
• вправо идет 2 камня;
• в данной клетке остается 1 камень.
Тогда единицы и двойки будут идти вправо, пока не соберутся в 3-ку н аправой границе. Однако в данной стратегии есть изъяны, а именно она не будет работать для маленького z. Например потому-что 6-ка по такой стратегии разделиться на 2, 1 и 3, и 3-ка пойдет вниз, хотя она и находиться пока на левой границе, поэтому еще нужно аккуратно рассмотреть количества камней от 4-х до 6-и, а остальные будут распадаться на базовые части и части ⩾ 4.
В итоге получаем такую стратегию:
| Количество | Вправо | Вниз |
|---|---|---|
| 1 2 3 4 5 6 z ⩾ 7 |
1 2 0 2 1 2 2 |
0 0 3 1 2 2 z−3 |
Only registered users can participate in poll. Log in, please.
Хотите еще больше задач?
87.5% Да7
12.5% Нет1
8 users voted. 2 users abstained.