A div2

Требовалось просто найти наименьшую отсутствующую в числе цифру и сравнить результат с данным k.

B div2

Хороший отрезок либо содержит все нули, либо длина его мала. Второе следует из того, что длина отрезка не может превосходить длины последовательности {0, 1, 2, 3, 5, 8, ..., x, y} (y > 10⁹; x < 10⁹). Длина этой последовательности, в свою очередь, меньше 50. Тогда второй случай можно разобрать наивным алгоритмом, а второй, например, динамикой (d_i = 0 eсли a_i ≠ 0 и d_i = d_i - 1 + 1 если a_i = 0).

A div1

Заметим, что сумма в прямоугольнике (x1, y1, x2, y2) равна sum(x1, x2)·sum(y1, y2). Здесь sum(l, r) = s_l + s_l + 1 + ... + s_r. Теперь осталось посчитать sum(l, r) для всех (l, r) и посчитать сколько отрезков дают в сумме x для всех возможных x (0 ≤ x ≤ 9·|s|). В итоге нужно пробежать по всем возможным суммам на [x1, x2] и найти . Не стоит забывать про случай a = 0.

B div1

Можно считать, что Джон может x на y, если s(x) + d ≥ s(y) (не важно, если x пересекает y). Можно стандартной динамикой посчитать все возможные суммы в множествах (задача о рюкзаке). Тогда Джон должен всегда менять все свое текущее множество на другое, потому что, если он обменял подмножество x (текущее) z (подмножество) на y, можно сказать, что он поменял x to . Теперь осталось найти кратчайшую последовательность множеств a, такую, что s(a_i + 1) - d ≥ s(a_i) для любого i и a₀ = {}. Это может быть решено следующей жадностью. a_i, i > 0 максимальная корректная сумма, такая, что a_i ≤ a_i - 1 + d. Рассмотрим оптимальный ответ c и ответ жадности a. Пусть k — первая позиция, такая что a_k ≠ c_k, очевидно a_k > c_k (так как a_k выбрано наибольшим). Затем рассмотрим q такое, что q_i = c_i для i ≠ k и q_k = a_k. q так же оптимален. Такими заменами можно получить a. Тогда a оптимально.

C div1

Пока не переведено.

D div1

1. Возьмем случайный элемент a_r из a. С вероятностью где g is ghd of a.
2. Пусть x_i = gcd(a_i, a_r). Существует не более d различных x_i, где d — количество делителей a_r.
3. Можно найти количество a_i, таких, что для любого k за O(d²) обычным перебором. Здесь D — множество делителей a_r.
4. Если повторить пункт 1 x раз, то полученное решение будет корректным с вероятностью 1 - 2^- x.

Можно решать эту задачу O(n·plog + d·2^plog) на итерацию (примерно в 10 раз быстрее решения выше), где plog — максимальное количество различных простых в факторизации a_r. Это решение и предполагалось, но перед контестом оказалось, что можно получить ОК решением выше, если уменьшить количество итераций до минимально возможного. Уменьшать до предела количество итераций в авторском решении мы не стали.

E div1

1. Найдем количество прямоугольников не более чем с k единицами внутри, пересекающих в декартовой системе координат.
2. Можно это сделать за n²·k. Нужно найти k ближайших единиц сверху и снизк от , перебрать все отрезки [l, r] такие, что 1 ≤ l ≤ r ≤ n и найти ближайшие k единиц сверху и снизу от отрезка.
3. Это можно сделать слиянием соответствующих массивов для строк.
4. Найдя ближайшие слева и справа от [l, r] k единиц можно найти количество прямоугольников, пересекающих по отрезку [l, r].
5. Это можно сделать, перебрав количество единиц сверху, которое входит в прямоугольник. По нему однозначно восстанавливается количество единиц снизу и определяются границы, в которых может лежать верхняя и нижняя сторона прямоугольника.
6. Теперь осталось поделить доску пополам и запустить этот алгоритм для половинок. При этом нужно сменить ориентацию разрезающей прямой. Нетрудно увидеть, что такой алгоритм посчитает все прямоугольники.
7. для квадратных досок. Для прямоугольных это сумма соответствующих выражений для n и m.

На рисунке 1 ближайшие сверху единицы (помечены черным) лежат на 4й и 2й горизонтали. Ближайшие снизу — на 5й и 7й. Тогда при k = 2 Корректных прямоугольников, которые содержат две единицы сверху и пересекают красную прямую нет. Есть 4 прямоугольника, которые содержат по одной единице сверху и снизу. На рисунках 2, 3 и 4 показано расширение имеющегося отрезка. Каждый раз требуется слить текущий массив ближайших единиц с массивом ближайших к строке единиц.