Задачи A(div2), B(div2)

В этих задачах требовалось реализовать ровно то, что описано в условии. В задаче B не рекомендовалось использовать BigInteger в Java из за скорости работы с ним.

Задача C(div2), A(div1)

В этой задаче буквы из строки s1 следовало набирать жадно: брать самую левую букву справа от последней использованной, если требуемой буквы не было справа от последней использованной, то следовало начать поиск с начала строки s1 и увеличить ответ на единицу. Однако реализация "в лоб" получала TL и имела асимптотику O(Ans * |s1|). 

Это решение можно оптимизировать, например, следующим образом. Для каждой позиции в s1 предпосчитать позиции самых левых символов от текущего для всего алфавита. Это можно было реализовать идя справа налево в строке s1 храня позиции последнего вхождения символа каждого вида в строку. Такое решение имеет асимптотику O(|s1| * K + |s2|), где K --- размер алфавита.

Другая оптимизация подразумевала хранение 26-и сбалансированных деревьев или отсортированных списков (по одному для каждого символа) состоящих из позиций вхождения того или иного символа. С помощью них, используя lower_bound, можно было искать самый левый нужный нам символ справа от текущей позиции. Такое решение имеет асимптотику O(|s1| + |s2| * log(|s1|).

Задача D(div2), B(div1)

Авторское решение подразумевает следующее. Предпосчитаем все минимумы на отрезках вида [i, n]. Это можно выполнить за O(n) также идя справа налево. Обозначим минимум на отрезке [i, n] за Min_i. Очевидно, что Min_i <  = Min_i + 1. Теперь для каждой позиции i с помощью бинарного поиска найдем такое число j > i, что Min_j < a_i и Min_j + 1 >  = a{i}. Для такого числа j утверждается, что среди моржей с номером j и более нету моржей младше моржа i. Это очевидно так, как Min_j принимает значение минимального возраста моржа на отрезке [j, n]. Если такого j не нашлось то следует вывести  - 1 иначе j - i - 1.

Задача E(div2), C(div1)

Будем считать количество лыжных баз включая базу из пустого подмножества ребер (при выводе просто отнимем единицу). Изначально количество лыжных баз равно 1. Если мы соединяем вершины которые были в одной компоненте связности, то результат умножим на два, в противном случае ничего делать не надо. Для того, чтобы быстро узнавать лежат ли две вершины в одной компоненте связности и быстро объединять компоненты можно было использовать DJS.

Теперь самый смак. Почему же это верно?
Для доказательства используем матрицу инцидентности I, строками будут являть ребра, столбцами --- вершины. Определим xor двух строк. Xor'ом двух строк a и b является строка c такая, что c_i = a_i xor b_i. Заметим, что если xor нескольких строк равен строке содержащей только нули, то ребра соответствующие взятым строкам образуют лыжную базу. Действительно, степень смежности каждой вершины четна, а значит в каждой компоненте из взятых можно построить эйлеров цикл (Необходимые и достаточное условие существования эйлерова цикла: четность степени смежности каждой вершины и связность графа). Ответом будет являться 2(m - rank(I)). 

Почему это так? Если справа от каждой строки в матрице приписать индекс соответствующего ребра и искать ранг матрицы с помощью метода Гаусса и при xor'e строк выполнять xor наборов ребер записанных справа, то в итоге наборы ребер которые будут записаны справа от нулевых строк будут образовывать базис линейного пространства. В доказательство корректности этого я приведу алгоритм поиска ранга матрицы из которого это будет очевидно.

Найдем ранг матрицы, как обычно, используя метод Гаусса и пометим строки которые остались не нулевыми. Теперь вернемся к исходной матрице, но с запоминанием помеченных строк. Теперь будем искать так же ранг матрицы, но не помеченную строку приводить к нулевой будем только выполняя ее xor с помеченными строками.

Пример:
1 1 0 a*
0 1 1 b*
1 0 1 c
1 0 1 d

1 1 0 a*
0 1 1 b*
0 0 0 c + a +b
0 0 0 d + a +b

Так как наборы ребер записанные справа образуют базис, то ни один набор записанный справа от нулевой строки не должен получаться путем комбинации (xor'а) других наборов записанных справа от нулевых строк. Действительно это так потому, что справа от нулевой строки будет находиться ребро соответствующее ей изначально и ни в каком наборе записанном справа от нулевой строки оно не встретится т.к. мы выполняли xor только с помеченными строками.

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

Задача D(div1)
Выделим все циклы в подстановке вида:
1 2 3 4 5 ...
a₁ a₂ a₃ a₄ a₅ ...
Например, в последовательности a = {2, 1, 4, 5, 3} есть 2 цикла длины 2 и 3 на позициях 1 2 и 3 4 5 соответственно. Если длина цикла больше 5, то взяв 5 последовательных элементов можно их переставить так, что 4 из них встанут на свои места. Так же можно взять 4 элемента и получить 3 элемента на своих местах. В общем виде: если мы берем p элементов в цикле длины больше p, то можно переставить их так, чтобы p - 1 встали на свои места. Если длина цикла равна p, то можно взять p элементов и поставить все из них на свои места. Поэтому для общность далее я буду говорить о длине цикла, как о его длине - 1 (теперь можно всегда говорить, что если взять p элементов, то p-1 встанут на свои места).
Не всегда все элементы выгодно брать в одном цикле, можно брать несколько в одном и несколько в другом. Таким образом можно получить разбиения чисел до 5 на их сумму: 5, 4, 3, 2, 2 + 3, 2 + 2. Можно взять, например, три элемента в первом цикле и два во втором, их длины уменьшатся на 2 и 1 соответственно.
Задача заключается в том, чтобы довести все длины циклов до нуля. Предположим в что в оптимальном решении нам следовало бы четыре раза уменьшать один и тот же цикл (a) на единицу. Будем считать, что выполнялись операции где берется ровно по 5 элементов и они не применялись к одним и тем же циклам, за исключением a. Такое условие является более строгим так как при пересечении операций в других циклах или при выборе меньшего количества элементов можно использовать менее продуктивные операции.
Схематично это можно представить в виде таблицы: строки --- это операции, столбцы --- циклы, а в клетках записаны значения на которые уменьшается тот или иной цикл.
a    b   c    d    e
1    2
1        2
1              2
1                   2 
Заменим операции на следующие:
a    b    c    d    e
4
      2   1
           1    2
                       2
Количество операций не изменилось, но теперь стало видно, что если существует оптимальное решение, где встречается четырежды уменьшение цикла на единицу, то существует оптимальное решение где не встречается четырежды уменьшение цикла на единицу. Приведем еще несколько замен подобной выше:
a    b    c
2    1
2          1
Заменим на:
a    b    c
4
      1    1

и

a    b    c    d
2    1
1         2
1               2
Заменим на:
a    b    c    d
4
      1   2
                 2
Из этих замен вытекает то, что существует оптимальное решение в котором один и тот же цикл не уменьшался на 1 + 1 + 1 + 1, 2 + 2, 1 + 1 + 2. Отсюда следует, что каждый цикл следует уменьшать жадно на 4 элемента пока его размер  >  = 4. Таким же методом докажем, что если остались после жадного набора циклы длины 3, то их следует уменьшать сразу на 3.

a    b    c  
2    1
1          2
Заменим на:
a    b    c    d
3
      1    2

a    b    c    d
1    2
1         2
1               2
Заменим на:
a    b    c    d
3
      2   1
           1    2

Теперь остались только циклы длины 2 и 1. Будем перебирать количество операций вида {2, 2} -  > {0, 1} (один цикл длины два уменьшается на два, другой цикл длины два уменьшается на единицу), которые следует выполнить. Пусть мы зафиксировали некоторое количество таких операций. Теперь выполним максимальное количество операций вида {2, 1} -  > {0, 0}. После их выполнения у нас либо не останется циклов положительной длины, либо останутся циклы только длины 1, либо останутся циклы только длины 2. Во втором случае следует выполнять операции вида {1, 1} -  > {0, 0} и если останется один цикл, то следует применить операцию {1} -  > {0}. В третьем случае следует выполнять операции {2} -  > {0}. Перебирая количество операций {2, 2} -  > {0, 1} и выполняя описанные выше действия мы найдем оптимальное решение. Разбивать цикл не несколько циклов меньшего размера не имеет смысла. Стресс тест показал, что объединение циклов тоже не ведет к улучшению.

Задача E(div1)

Формально нам задан массив значение в ячейке которого описывается функцией зависящей от времени T val_i = a_i + b_i * T (в геометрическом смысле это уравнения прямых). Разобьем массив на блоки величины d ~ sqrt(n): [0;d), [d, d * 2), [d * 2, d * 3), ..., [d * k, n). Теперь предпросчитаем моменты времени, когда меняется лидер на блоке. Так как у нас есть уравнения прямых, то можно воспользоваться алгоритмом пересечения полуплоскостей образованных разрезанием плоскости уравнениями прямых из обрабатываемого блока. На оси Oy отмечаются высоты, на оси Ox --- время. Нас будет интересовать только координаты x точек пересечения полуплоскостей и номера прямых которые пересекаются в этой точке. Будем считать, что для каждого блока мы нашли моменты времени, когда меняется лидер и номер лидирующего после этого момента. Для каждого блока это займет O(d * log(d)) времени. так как блоков (k) у нас примерно n / d ~ n / sqrt(n) ~ sqrt(n), то весь препроцессинг займет O(n * log(n)) времени.

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

Всего удалений моментов времени смены лидера будет не больше O(n), а не считая удаление моментов времени смены лидера, каждый запрос обрабатывается за O(sqrt(n)). Итоговая асимптотика равна O(n * log(n) + m * sqrt(n)). 

Для решения этой задачи можно было воспользоваться деревом отрезков и получить асимптотику O(n * log(n)), но использование O(n * log(n)) памяти.