Пожалуйста, задавайте возникающие у вас вопросы по задачам. Особенно это касается задачи D, так как она оказалась наиболее сложной.

Задача <<Экзамены>> По условию 2n ≤ k ≤ 5n. Если k < 3n то некоторые экзамены мы сможем сдать только на 2. Таких будет 3n - k. Если же 3n ≤ k, то мы все экзамены сдадим как минимум на три.

Задача <<Квадрат>> Пусть карандаш идет по прямой и ставит крестики через каждые (n + 1) точку. Поставим в соответствие положению на прямой положение на квадрате. А именно, точке x на прямой будет соответствовать точка, в которую придет карандаш, сдвинувшись по периметру квадрата на x. Тогда левому нижнему углу квадрата соответствуют все точки вида 4np для некоторого целого неотрицательного p. Поставленным крестиками будут соответствовать точки k(n + 1). Самая ближайшая точка совпадения двух семейств, за исключением начальной, будет в LCM(n + 1, 4n) (LCM — НОК). Тогда всего мы поставим крестиков.

Задача <<Разрезание фигуры>>

Основная идея: учитывая, что ответ не превышает двух, проверим существование ответа 1.

Докажем, что ответ в задаче не превосходит двух. Пусть площадь фигуры не менее 4. Тогда рассмотрим самую левую из самых верхних клеток. У нее нет левого и верхнего соседей по стороне. Значит, у нее не будет более двух соседей. Тогда, удалив ее соседей мы уже разделим фигуру на две. Если площадь равна трем, то всегда можно разрезать ее, удалив одну клетку, это можно проверить, так как существует всего два принципиальных случая. Если площадь фигуры не превышает двух, то какое бы множество клеток мы не удалили, она не распадется.

Проверим, существует ли ответ, величины один. Удаляемую клетку можно просто перебрать, а затем запустить dfs из любой неудаленной клетки. Если dfs посетит не все оставшиеся клетки, то, удалив нужную клетку мы разрежем фигуру. Если подходящая клетка нашлась — ответ равен 1. Если нет — 2.

Еще нужно было не забыть, что иногда ответа может просто не существовать. Это бывает тогда, когда площадь фигуры меньше либо равна двум (площадь фигуры — кол-во клеток в ней)ю

Асимптотика решения O(n⁴). Еще можно было воспользоваться алгоритмом поиска точек сочленения и решить эту задачу за O(n²). Но это, наверное, требовало больших трудозатрат.

Задача <>

Основная идея: перебор за O(F_un). F_u — u-е число Фибоначчи.

У этой задачи было довольно сложное условие. С массивом a можно было проводить операции двух типов. Нужно было провести ровно u таких операций, чтобы максимизировать сумму значений массива с заданными коэффициентами.

Если просто перебрать все возможные комбинации операций, а потом промоделировать их, то получится решение за O(2^u·nu). Это слишом долго. Можно было улучшить это решение, перебирая комбинации операций рекурсивно и по ходу рекурсии моделируя их. Тогда асимптотика улучшается до O(2^u·n). Собственно, ничего сильно лучше этого решения не требовалось. Возникает лишь одно соображение: если у нас были две операции подряд, то они ничего не изменили и их можно переместить в любое место нашего алгоритма, не изменив его результат. Тогда можно перебирать только те алгоритмы, в которых все парные операции стоят в конце. Это тоже можно было делать рекурсивно, не идя в ветки с двумя, подряд идущими операциями и обновляя лучший ответ не только в конце рекурсии, но и тогда, когда в конце осталось четное число операций. Это работает сильно лучше. Вспомнив известную задачу "кол-во последовательностей из нулей и единиц, без двух единиц подряд" можно понять, что кол-во таких последовательностей, длиной k, равно F_k + 1, где F_i — i-е число Фибоначчи. Тогда кол-во допустимых алгоритмов равно сумме первых u чисел Фибоначчи. Эта сумма примерно равна (u + 2)-му чмслу Фибоначчи. Итоговая асимптотика составляет O(F_u·n). Для максимальных значений входных данных эта величина равна примерно 30 миллионам.

Мне не удалось написать на эту задачу отжиг или какое-либо рандом-решение, которое проходило бы все или хотя бы большинство тестов.

Задача <<Расстояние Хемминга>>

Основная идея: сведение к СЛАУ и решение ее методом Гаусса.

Заметим, что если мы одинаковым образом переставим символы во всех строках, то ответ не изменится. Рассмотрим <<столбцы>> ответа, то есть строки s_1, i + s_2, i + s_3, i + s_4, i для некоторого i. Всего существует 2⁴ = 16 типов таких строк. Получается, что, если существует ответ на задачу, длины l, то существует и ответ той же длины в котором столбцы упорядочены по типу. Тогда, чтобы перебрать ответ, достаточно перебрать 16 чисел — количества столбцов каждого типа. По этим числам легко восстановить все расстояния Хемминга. Расстояние между строками s_i и s_j будет равно сумме количеств столбцов в которых различны символы c номерами i и j.

Однако перебирать все возможные количества столбцов каждого типа слишком долго. Заметим, что мы можем записать систему из 6 уравнений с 16 неизвестными (вспомнив, что расстояние между строками s_i и s_j будет равно сумме количеств столбцов в которых различны символы c номерами i и j). Неизвестными в этой системе уравнений будут количества столбцов каждого из типов. Заметим, что некоторые варианты столбцов полностью идентичны с точки зрения вклада, вносимого в расстояния Хемминга. А именно, столбцы, получаемые друг из друга инвертированием всех букв (заменой <> на <> и наоборот) вносят идентичный вклад в расстояния Хемминга. Например, если добавить в ответ столбец <>, расстояния Хемминга между всеми парами строк изменятся тем же образом, что и при добавлении столбца <>. Получается, что мы можем рассматривать лишь 8 возможных столбцов. Кроме того, столбцы <> и <> вносят нулевой вклад во все расстояния Хемминга. Один из них мы уже исключили из рассмотрения, но можно исключить и второй. Таким образом, мы сократили количество переменных до 7. Решим СЛАУ относительно каких-нибудь шести переменных. Свободным осталось значение одной из переменных. Так как столбцы, количеству которых соответствует эта переменная, вносят ненулевой вклад хотя бы в одно расстояние Хемминга, значение этой переменной не может превосходить максимума из заданных расстояний Хемминга. Тогда можно перебрать его и выбрать наилучший из получившихся ответов.

Алгоритм получается следующий:

• Для каждого типа столбцов определим, какой вклад один такой столбец вносит в каждое из расстояний Хемминга
• Запустим алгоритм Гаусса для полученной матрицы
• Переберем значение свободной переменной, выразим через нее остальные, проверим, что все они неотрицательны и целы, выберем наилучший из ответов.
• Выведем ответ.

Асимптотика этого решения составляла O(max(d_i, j)), если пользоваться типом double и , если решать задачу в рациональных числах.

Наверное, могло показаться, что при решении в рациональных числах могло быть переполнение. Но, так как мы применяем наш алгоритм к одной и той же матрице (за исключением последнего столбца), наши вычисления всегда одинаковы, то есть мы домножаем строки на одни и те же числа. Можно заметить, что в нашей матрице все числа будут единицами или двойками, тогда никакой коэффициент в итоге не превысит . Таким образом, можно решать задачу в рациональных числах или в типе double.

Задача <<Два отрезка>>

Основная идея: обратить перестановку и решать упрощенную задачу (см. ниже), рассмотреть функцию <<количество отрезков в перестановке, которые образуют данный отрезок натурального ряда>>.

Чтобы решить эту задачу, можно решить обратную: <<дана перестановка p_n, нужно посчитать в них количество отрезков, элементы которых образуют 1 или 2 отрезка натурального ряда>>.

Если мы решим эту задачу для некоторой перестановки q_n, такой, что , то мы получим ответ для исходной задачи и перестановки.

Первое решение, которое приходит в голову: переберем отрезок перестановки и в булевом массиве отметим элементы, принадлежащие ему. Проверим, что в булевском массиве получилось два отрезка. Такое решение будет иметь асимптотику O(n³).

После некоторых размышлений можно понять, что при переходе от отрезка пере [l, r] к [l, r + 1] количество отрезков изменится некоторым предсказуемым образом. Обозначим s([a, b]) количество отрезков, которые образуют элементы отрезка [a, b] перестановки. Если новый элемент p_r + 1 будет находиться между уже поставленными элементами (то есть, элементы со значениями p_r + 1 - 1 и p_r + 1 + 1 будут принадлежать отрезку [l, r]), то s([l, r + 1]) = s([l, r]) - 1. Новый элемент <<склеит>> два отрезка между которыми появится. Если у элемента p_r + 1 будет один сосед, принадлежащий отрезку [l, r], то s([l, r]) = s([l, r + 1]) (один из существующих отрезков удлинится). Если же у элемента p_r + 1 не будет соседей на отрезке [l, r], то новый элемент образует новый отрезок и s([l, r + 1]) = s([l, r]) + 1. Это иллюстрирует рисунок ниже:

Новый элемент помечен красным, уже поставленные — черным.

Из этих соображений можно получить следующее решение: переберем левую границу и, перебирая правую слева направо, будем пересчитывать количество отрезков, которые образует текущий отрезок перестановки. Если это число равно 1 или 2, прибавим к ответу единицу. Получаем асимптотику O(n²). Это решение работало достаточно быстро даже на n = 20000. Но, разумеется, этого было недостаточно, чтобы решить задачу.

Перейдем к полному решению. Оно основывается на предыдущем. Мы уже умеем пересчитывать число отрезков при движении правой границы. Теперь нужно понять, как найти s([l - 1, r]) для любых r, используя s([l, r]). Будем перебирать позицию левой границы отрезков справа налево и поддерживать структуру данных, которая позволит нам хранить s([l, r]) для всех r и сможет считать в себе количество чисел 1 и 2.

Обозначим за Δ_i s([l - 1, i]) - s([l, i]). Δ_l = 1 так как один элемент образует ровно 1 отрезок. Далее, если мы будем увеличивать i, Δ_i будет зависеть от количества соседей элемента l на отрезке [l - 1, i].

• Если на отрезке нет соседей l, то количество отрезков, которым он соответствует увеличится на 1 при добавлении элемента l (так как l не присоединится ни к какому существующему отрезку).
• Если на отрезке ровно один сосед l, то количество отрезков, которым он соответствует не изменится при его добавлении (так как l просто присоединится к отрезку своего соседа).
• Если на отрезке два соседа l, то при его добавлении, количество образуемых отрезков уменьшится на 1.

Найдем соседей l, лежащих после него. Обозначим их за a и b. (если после l лежит только один его сосед, b = inf) тогда для всех i, таких что l ≤ i < a Δ_i = 1. Для всех i, таких что a ≤ i < b Δ_i = 0 и для всех i удовлетворяющих b ≤ i ≤ n Δ_i =  - 1. Тогда, чтобы обновить нашу структуру достаточно сделать два прибавления на отрезке.

На картинке выше видно, что у элемента 5 оба соседа лежат правее его. Поэтому получается три отрезка эквивалентности Δ_i (первый из них находится в самом элементе 5). После первого встреченного соседа (4) Δ_i принимает значение 0 и, наконец, начиная с соседа 6, Δ_i принимают значение  - 1.

Остается только придумать структуру, позволяющую прибавлять на отрезке +1 и -1 и искать в семе числа 1 и 2. Во-первых, заметим, что неположительных чисел структура хранить не будет. Тогда числа 1 и 2 будут являться первым или вторым минимумом в структуре. Тогда структуре достаточно уметь искать два минимума в себе и уметь прибавлять +1 и -1 на отрезке. Два минимума ищутся почти так же, как и один, поэтому можно адаптировать дерево отрезков или sqrt-декомпозицию под эти цели. Сумма ответов структуры на каждой итерации будет ответом на задачу. Авторская sqrt-декомпозиция работала 1.3 секунды, авторское дерево отрезков — 1.1 секунды. sqrt-декомпозиция на Java — 3.6 секунд.

Задача <<Число Фибоначчи>>

Решение: baby-step-giant-step

В этой задаче было дано некоторое число Фибоначчи f по модулю 10¹³, требовалось определить его первое вхождение в последовательность (позицию).

• Рассмотрим два взаимно простых модуля, делящих 10¹³. Пометим их как a и b.
• Остаток от деления f на a будет равен остатку от деления настоящего числа Фибоначчи F, такого, что . ().
• Найдем вхождения в период последовательности Фибоначчи по модулю a.
• Найдем вхождения в период последовательности Фибоначчи по модулю b.
• Зафиксируем пару этих вхождений. Пусть вхождение в последовательность Фибоначчи по модулю a будет в позиции i, а по модулю b — в позиции j.
• Обозначим за t(m) период последовательности Фибоначчи по модулю m.
• Из Китайской Теоремы об Остатках следует, что t(ab) = LCM(t(a), t(b)) (так как a и b выбраны взаимно простыми).
• Тогда по зафиксированным вхождениям f по модулям a и b можно восстановить вхождение f в последовательность по модулю ab. Это можно сделать, решив Диофантово уравнение i + t(a)·x = j + t(b)·y. Это уравнение можно решить перебором одного из корней.
• Если найденное вхождение в последовательность по модулю ab обозначить за u, то все вхождения f в последовательность по модулю 10¹³ будут представимы в виде t(ab)·k + u. Тогда переберем k и найдем все вхождения f в последовательность Фибоначчи по модулю 10¹³. Чтобы получить из числа Фибоначчи на позиции α, чиcло Фибоначчи на позиции α + t(ab) нужно домножить вектор из F_α и F_α + 1 на некоторую матрицу.
• Выберем a = 5⁹ и b = 2¹³. Заметим, что никакое число не входит в период последовательности Фибоначчи по каждому из этих модулей более 8 раз. Тогда пар вхождений будет не более 64. Для каждого вхождения мы переберем до чисел.

Еще можно было более эффективно воспользоваться тем, что число вхождений любого числа в период последовательности Фибоначчи по модулям вроде 10^k невелико. Можно было получать из вхождений числа f в последовательность по модулю 10ⁱ получить вхождения по модулю 10(i + 1) подобно тому, как в авторском решении осуществляется переход от модуля ab к модулю 10¹³.