Приглашаем на MosCode Festival и разбираем задачи прошлых лет
Привет, Хабр! Центр развития ИТ-образования МФТИ приглашает тебя на международный студенческий чемпионат по спортивному программированию MosCode Festival. Это хорошая возможность потренироваться на задачах уровня финала ACM ICPC вместе с участниками из других стран. Контест пройдёт 31 марта (личный тур) и 1 апреля (командный тур) в технопарке «Сколково». Онлайн-отбор пройдёт в ближайшее воскресенье, 11 февраля, в 11:00 по московскому времени. Пока вы думаете о регистрации, рассказываем подробности и делимся двумя задачами прошлого года с разбором.
MosCode Festival, ранее известный как Московский фестиваль по спортивному программирования Кубка им. И.Н. Векуа, является значимым мероприятием в мире олимпиадного программирования. В прошлом году на фестиваль приехали 200 человек из 19 стран, в том числе впервые участвовали команды из Австралии, Японии и Испании. В этом году ожидаются 360 студентов из 40 стран. На данный момент заявку на участие подали команды из Канады, Индии, Великобритании, Китая и Бразилии.
А теперь разминка.
Задача «Нечто с точками и прямоугольниками»
Задача «Игра на поле»
Задача «Нечто с точками и прямоугольниками»
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 3 секунды
Ограничение по памяти: 256 мегабайт
На плоскости дан набор из n различных точек с целочисленными координатами. Назовем прямоугольник хорошим, если его углы находятся в точках с целочисленными координатами, и все точки с целочисленными координаты внутри и на границе принадлежат данному набору. При этом такой прямоугольник может быть и вырожденным (иметь нулевую площадь). Для каждой точки нужно найти количество хороших прямоугольников, которым она принадлежит.
Формат входных данных
В первой строке записано число n (1 ⩽ n ⩽ 105) — количество точек. В следующих строках записаны координаты точек (−105 ⩽ xi, yi ⩽ 105)
Формат выходных данных
Выведите 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^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 клетку вправо, несложно понять что данная стратегия выигрышна, для всех однострочных полей, и проигрышна для всех остальных.
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 |
