Ну, судя по тому, что тупое решение со слоном получает WA 8, а без него — TL 10 — таки нет

Какой у вас ответ на 7 3 1 1?

Заметим, что ответ не превышает 26*2. Так как каждую букву можно ввести и сразу удалить. Построим бор на всех подстроках длинны до 52. И намутим что-нибудь в этом боре.

Например будем рассматривать все возможные пути в боре. Предположим, что текущий путь мы введём в самом конце, а значит его не надо будет удалять. Такой путь, который можно будет не удалять очевидно только один. А значит за остальные мы не получим никакого бонуса, значит, что всё, что не покрылось полностью единственным неудаляемым путём имеет смысл покрыть вводя по одной букве и удаляя её. То-есть ответ это длинна пути + 2*(кол-во букв, непокрытых полностью этим путём). В процессе обхода бора будем поддерживать сколько букв у нас полностью покрыто. Для этого мне потребовалось хранить число строк проходящих через каждую вершину и строить в процессе обхода префикс функцию. Так как когда мы при обходе бора проходим через некоторый символ мы можем добавить его к покрытым только если он не был покрыт раньше префиксом текущего слова. Тоесть первое вхождение этого символа больше длинны префикс функции для текущей позиции

Полностью согласен. Без слона эта задача ни о чем

У меня не прошло. Только за KM.

Оказалось, что Пашка перепутал. MK на самом деле

Что-то типа MK logN я насчтал у себя, хотя наверно меньше все же.

NM проходило. Код

А я сдал предпосчёт. По модулю 2²⁰⁰²3⁴⁰⁰² посчитало за 10 минут. А как доказать, что та функция правильно себя ведёт? Как вообще можно анализировать такие функции, кроме как считать и искать закономерности?

Да, поэтому ГП, судя по-всему, будет незачетным

B D

D

Авторское по B. Lottery

Из 651432 нельзя получить 652143.

Из 651432 уже не получается 652143, вроде как.

Там на первое, из 2^k мест, ставится минимальный элемент.

Когда мы принимали решение по условию этой задачи, учитывалось, что турнир командный, а задача сама по себе сложная, и очень маловероятно, что все 3 участника будут не знакомы с правилами шахмат. Я при этом погуглил другие задачи про шахматы и убедился, что многие авторы опускают эту информацию, особенно когда речь идёт о всех фигурах — в этом случае описание ходов занимало бы пол страницы минимум.

То, что подразумевались все фигуры — это на наш взгляд очевидно. Просто представьте себе, что бы с нами сделали участники, если бы учитывались только некоторые :)

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

Добавлю, что на онсайте на вопрос о ходах пешки командам давался подробный ответ. Если бы такой же вопрос был задан на Кубке и передан нам координатором, мы бы поступили также.

Мы для каждого числа считали p[i] — расстояние до предыдущего такого же и затем d[i] — количество предыдущих p[j], совпадающих с нашим p[i]. Кроме того, дерево отрезков с максимумом из i — p[i]. Затем в онлайне отвечали на запросы. Может быть, можно как-то проще, если в оффлайне.

Решение попроще за O(N + M): В одном массиве B[i] будем хранить позицию, до которой мы можем двигаться вправо от i, пока все a[j] на пути будут различны. Это легко вычисляется как min(B[i + 1], следующее вхождение a[i]). Это позволит за O(1) найти размер блока из уникальных, обозначим его len. Затем найдем сколько от каждого числа a[i] двигаться влево до такого же, пусть это массив C. Надо быстро определять, чтобы все значения в C[l + len, r] = len. Заведем еще массив D, D[i] = (C[i] != C[i — 1]). Проинтегрируем его. Теперь все C[l + len, r] = len, если (D[r] — D[l + len] = 0) & (C[l + len] = len).

. Что за столько можно не соложно делается по индукции. Почему нельзя меньше не знаю, если честно. Но вроде из той же индукции понятно, что должно быть так.

Можно еще посмотреть для маленьких и сделать рекурсивную формулу,

,

Должен быть. И кстати они работают и не лежали вроде как.

Да. И у меня opencup.ru работал все те разы, что я пытался на него зайти

И opencup.ru, и snarknews.info доступны с очень ограниченного диапазона ip. В частности, из Германии вроде ниоткуда недоступны. Даже vpn не спасает. Похоже, "умный" хостер всё ещё думает, что opencup ддосят, и поэтому блокирует доступ почти отовсюду.