Здравствуйте! Пытаюсь сдать задачу "882. Губернатор" с сайта acmp.ru. Недавно я создавал аналогичный пост для другой задачи, под которым подсказали, что в задачах такого рода должен работать жадный алгоритм и нужно лишь определить предикат для сортировки.

В этой же задаче я понял, что ответ не зависит от K и необходимо минимизировать сумму:

Здесь индексами обозначена последовательность взятия.

Я генерировал маленькие случайные тесты, для которых можно перебрать все n! перестановок и пробовал подобрать предикат, но все безрезультатно. Максимально близко к случайным тестам размера 10 подошел предикат , где — произведение всех a_i. На этом идеи кончились и нужна помощь. Может из-за маленького n решение предполагает динамику за O(n²) времени с памятью O(n), но с ней тоже не вяжется.

Здравствуйте! Этот пост написан для всех тех, кто хочет освоить полиномиальные хэши и научиться применять их в решении различных задач. Я кратко приведу теоретический материал, рассмотрю особенности реализации и разберу некоторые задачи, среди них:

1. Поиск всех вхождений одной строки длины n в другую длины m за O(n + m)

2. Поиск наибольшей общей подстроки двух строк длин n и m (n ≥ m) за O((n + m·log(n))·log(m)) и O(n·log(m))

3. Нахождение лексикографически минимального циклического сдвига строки длины n за O(n·log(n))

4. Сортировка всех циклических сдвигов строки длины n в лексикографическом порядке за O(n·log(n)²)

5. Нахождение количества подпалиндромов строки длины n за O(n·log(n))

6. Количество подстрок строки длины n, являющихся циклическими сдвигами строки длины m за O((n + m)·log(n))

7. Количество суффиксов строки длины n, бесконечное расширение которых совпадает с бесконечным расширением всей строки за O(n·log(n)) (расширение — дублирование строки бесконечное число раз)

8. Наибольший общий префикс двух строк длины n с обменом двух произвольных символов одной строки местами за O(n·log(n))

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

Примечание 2. В задачах выше приведена оценка, когда поиск хэша осуществляется при помощи сортировки и бинарного поиска. Если у Вас есть своя хэш-таблица с открытым перемешиванием или цепочками переполнения, то Вы — счастливчик, смело заменяйте бинарный поиск хэша на поиск в Вашей хэш-таблице, но не вздумайте использовать std::unordered_set, так как на практике поиск в std::unordered_set проигрывает сортировке и бинарному поиску в связи с тем, что эта штука подчиняется стандарту C++ и обязана много чего гарантировать пользователю, что полезно при промышленной разработке и, зачастую, бесполезно в олимпиадном программировании, поэтому сортировка и бинарный поиск для несложных структур одерживают абсолютное первенство в C++ по скорости работы, если не тянуть что-то свое.

Примечание 3. В тех случаях, когда сравнение элементов затратно (например, сравнение по хэшам за O(log(n))), то в худшем случае std::random_shuffle + std::sort всегда проигрывает std::stable_sort, так как std::stable_sort гарантирует минимальное число сравнений среди всех сортировок (основанных на сравнениях) для худшего случая.

Решение перечисленных задач будет приведено ниже, исходники тоже.

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

Среди минусов полиномиального хэширования: а) Слишком много операций остатка от деления, порой на грани TLE на больших задачах и б) на codeforces в программах на C++ зачастую маленькие гарантии от взлома из-за MinGW: std::random_device генерирует каждый раз одно и то же число, std::chrono::high_resolution_clock тикает в микросекундах вместо наносекунд. (Компилятор cygwin на windows лишен всех недостатков MinGW, в том числе и медленного ввода/вывода).

x = (x >> 31) + (x & 2147483647);
x = (x >> 31) + (x & 2147483647);
return x;

Что такое полиномиальный хэш?

Хэш-функция должна сопоставлять некоторому объекту некоторое число (его хэш) и обладать следующими свойствами:

1. Если два объекта совпадают, то их хэши равны.

2. Если два хэша равны, то объекты совпадают с большой вероятностью.

Коллизией называется очень неприятная ситуация равенства двух хэшей у несовпадающих объектов. В идеале, при выборе хэш-функции необходимо обеспечить как можно меньшую вероятность коллизии. На практике — такую вероятность, чтобы успешно пройти набор тестов к задаче.

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

Рассмотрим последовательность {a₀, a₁, ..., a_n - 1}. Под полиномиальным хэшем слева-направо для этой последовательности будем иметь в виду результат вычисления следующего выражения:

Здесь p и m — точка (или основание) и модуль хэширования соответственно.

Условия, которые мы наложим: , .

Примечание. Если подумать об интерпретации выражения, то мы сопоставляем последовательности {a₀, a₁, ..., a_n - 1} число длины n в системе счисления p и берем остаток от его деления на число m, или значение многочлена (n - 1)-й степени с коэффициентами a_i в точке p по модулю m. О выборе p и m поговорим позже.

Примечание. Если значение , не взятое по модулю, помещается в целочисленный тип данных (например, 64-битный тип), то можно каждой последовательности сопоставить это число. Тогда сравнение на больше / меньше / равно можно выполнять за O(1).

Сравнение на равенство за O(1)

Теперь ответим на вопрос, как сравнивать произвольные непрерывные подотрезки последовательности за O(1)? Покажем, что для их сравнения достаточно посчитать полиномиальный хэш на каждом префиксе исходной последовательности {a₀, a₁, ..., a_n - 1} .

Определим полиномиальный хэш на префиксе как:

Кратко обозначим как и будем иметь в виду, что итоговое значение берется по модулю m. Тогда:

Общий вид:

Полиномиальный хэш на каждом префиксе можно находить за O(n), используя рекуррентные соотношения:

Допустим, нам нужно сравнить две подстроки, начинающиеся в позициях i и j и имеющие длину len, на равенство:

Рассмотрим разности и . Не трудно видеть, что:

Домножим 1-е уравнение на p^j, а 2-е на pⁱ. Получим:

Видим, что в правой части выражений в скобках были получены полиномиальные хэши от подотрезков:

Таким образом, чтобы определить, совпали ли искомые подотрезки, необходимо проверить выполнение следующего равенства:

Одно такое сравнение можно выполнять за O(1), предподсчитав степени p по модулю. С учетом модуля m, имеем:

Проблема: сравнение одной строки зависит от параметров другой строки (от j).

Первое решение данной проблемы (предложил veschii_nevstrui) основывается на домножении первого уравнения на p^- i, а второго на p^- j. Тогда получим:

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

Для реализации этого необходимо найти обратный элемент для p по модулю m. Из условия gcd(p, m) = 1 обратный элемент всегда существует. Для этого необходимо вычислить значение функции Эйлера для выбранного модуля φ(m) и возвести p в степень φ(m) - 1. Если предподсчитать степени обратного элемента по выбранному модулю, то сравнение можно выполнять за O(1).

Второе решение данной проблемы основывается на знании максимальной длины сравниваемых строк. Обозначим максимальную длину сравниваемых строк как . Домножим 1-е уравнение на p в степени mxPow - i - len + 1, а 2-е на p в степени mxPow - j - len + 1. Тогда:

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

Этот подход позволяет сравнивать одну подстроку длины len со всеми подстроками длины len на равенство, в том числе, и подстроками другой строки, так как выражение для подстроки длины len, начинающейся в позиции i, зависит только от параметров подстроки i, len и константы mxPow, а не от параметров другой подстроки.

Теперь рассмотрим другой вариант выбора функции полиномиального хэширования. Определим полиномиальный хэш на префиксе как:

Кратко обозначим как и будем иметь в виду, что итоговое значение берется по модулю m. Тогда:

Полиномиальный хэш на каждом префиксе можно находить за O(n), используя рекуррентные соотношения:

Допустим, нам нужно сравнить две подстроки, начинающиеся в позициях i и j и имеющие длину len, на равенство:

Рассмотрим выражение и . Не трудно видеть, что:

Видим, что в правой части выражений в скобках были получены полиномиальные хэши от подотрезков:

Таким образом, чтобы определить, совпали ли искомые подотрезки, необходимо проверить выполнение следующего равенства:

Одно такое сравнение можно выполнять за O(1), предподсчитав степени p по модулю m.

Сравнение на больше / меньше за O(log(n))

Рассмотрим две подстроки возможно разных строк длин len1 и len2, (len1 ≤ len2), начинающиеся в позициях i и j соответственно. Заметим, что отношение больше / меньше определяется первым несовпадающим символом в этих подстроках, а до позиции этого символа строки совпадают. Таким образом, необходимо найти позицию первого несовпадающего символа методом бинарного поиска, а затем сравнить найденные символы. Благодаря сравнению подстрок на равенство за O(1), можно решить задачу сравнения подстрок на больше / меньше за O(log(len1)):

low = 0; high = len1+1;
while (high-low > 1) {
    mid = (low + high) / 2;
    if (hash(i,mid) == hash(j,mid)) {
        low = mid;
    } else {
        high = mid;
    }
}
low - позиция первого различия

Минимизация вероятности коллизии

Используя парадокс дней рождений, приведем (возможно, грубую) оценку вероятности коллизии. Пусть мы вычисляем полиномиальный хэш по модулю m и в ходе работы программы нам нужно сравнить n строк. Тогда вероятность того, что произойдет коллизия:

Отсюда очевидно, что m нужно брать значительно больше, чем n². Тогда, аппроксимируя экспоненту рядом Тейлора, получаем вероятность коллизии на одном тесте:

Если мы рассмотрим задачу о поиске вхождений всех циклических сдвигов одной строки в другую строку длин до 10⁵, то мы можем получить 10¹⁵ сравнений строк.

Тогда, если мы возьмем простой модуль порядка 10⁹, то мы не пройдем ни один из максимальных тестов.

Если мы возьмем модуль порядка 10¹⁸, то вероятность коллизии на одном тесте  ≈ 0.001. Если максимальных тестов 100, то вероятность коллизии в одном из тестов  ≈ 0.1, то есть 10%.

Если мы возьмем модуль порядка 10²⁷, то на 100 максимальных тестах вероятность коллизии равна  ≈ 10^- 10.

Вывод: чем больше модуль — тем больше вероятность пройти тест. Эта вероятность не учитывает взломы.

Двойной полиномиальный хэш

Разумеется, в реальных программах мы не можем брать модули порядка 10²⁷. Как быть? На помощь приходит китайская теорема об остатках. Если мы возьмем два взаимно простых модуля m₁ и m₂, то кольцо остатков по модулю m = m₁·m₂ эквивалентно произведению колец по модулям m₁ и m₂, т.е. между ними существует взаимно однозначное соответствие, основанное на идемпотентах кольца вычетов по модулю m. Иными словами, если вычислять по модулю m₁ и по модулю m₂, а затем сравнивать два искомых подотрезка по и одновременно, то это эквивалентно сравнению полиномиальным хэшем по модулю m. Аналогично, можно брать три взаимно простых модуля m₁, m₂, m₃.

Особенности реализации

Итак, мы подошли к реализации описанного выше. Цель — минимум взятий остатка от деления, т.е. получить два умножения в 64-битном типе и одно взятие остатка от деления в 64-битном типе на одно вычисление двойного полиномиального хэша, при этом получить хэш по модулю порядка 10^27 и защитить код от взлома на codeforces.

Выбор модулей. Выгодно использовать двойной полиномиальный хэш по модулям m1 = 1000000123 и m2 = 2^64. Если Вам не нравится такой выбор m1, можете выбрать 1000000321, главное выбрать такое простое число, чтобы разность двух остатков лежала в пределах знакового 32-битного типа (int). Простое число брать удобнее, так как автоматически обеспечиваются условия gcd(m1, m2) = 1 и gcd(m1, p) = 1. Выбор в качестве m2 = 2^64 не случаен. Стандарт C++ гарантирует, что все вычисления в unsigned long long выполняются по модулю 2^64 автоматически. Отдельно модуль 2^64 брать нельзя, так как существует анти-хэш тест, который не зависит от выбора точки хэширования p. Модуль m1 необходимо задать как константу для ускорения взятия модуля (компилятор (не MinGW) оптимизирует, заменяя умножением и побитовым сдвигом).

Кодирование последовательности. Если дана последовательность символов, состоящая, например, из маленьких латинских букв, то можно ничего не кодировать, так как каждому символу уже соответствует его код. Если дана последовательность целых чисел разумной для представления в памяти длины, то можно собрать в один массив все встречающиеся числа, отсортировать, удалить повторы и сопоставить каждому числу в последовательности его порядковый номер в полученном упорядоченном множестве. Начинать нумерацию с нуля запрещено: все последовательности вида 0,0,0,..,0 разной длины будут иметь один и тот же полиномиальный хэш.

Выбор основания. В качестве основания p достаточно взять любое нечетное число, удовлетворяющее условию max(a[i]) < p < m1. (нечетное, потому что тогда gcd(p, 2^64) = 1). Если Вас могут взломать, то необходимо генерировать p случайным образом с каждым новым запуском программы, причем генерация при помощи std::srand(std::time(0)) и std::rand() не подходит, так как std::time(0) тикает очень медленно, а std::rand() не обеспечивает достаточной равномерности. Если компилятор НЕ MinGW (к сожалению, на codeforces установлен MinGW), то можно использовать std::random_device, std::mt19937, std::uniform_int_distribution<int> (в cygwin на windows и gnu gcc на linux данный набор обеспечивает почти абсолютную случайность). Если не повезло и Вас посадили на MinGW, то ничего не остается, как std::random_device заменить на std::chrono::high_resolution_clock и надеяться на лучшее (или есть способ достать какой-нибудь счетчик из процессора?). На MinGW этот таймер тикает в микросекундах, на cygwin и gnu gcc в наносекундах.

Гарантии от взлома. Нечетных чисел до модуля порядка 10^9 тоже порядка 10^9. Взломщику необходимо будет сгенерировать для каждого нечетного числа анти-хэш тест так, чтобы была коллизия в пространстве до 10^27, скомпоновать все тесты в один большой тест и сломать Вас. Это если использовать не MinGW на Windows. На MinGW таймер тикает, как уже говорилось, в микросекундах. Зная время запуска решения на сервере с точностью до секунд, можно для каждой из 10^6 микросекунд вычислить, какое случайное p сгенерировалось, и тогда вариантов в 1000 раз меньше. Если 10^9 это какая-то космическая величина, то 10^6 уже кажется не такой безопасной. При использовании std::time(0) всего 10^3 вариантов (миллисекунды) — можно ломать. В комментариях я видел, что гроссмейстеры умеют ломать полиномиальный хэш до 10^36.

Удобство в использовании. Удобно написать универсальный объект для полиномиального хэша и копировать его в ту задачу, где он может понадобиться. Лучше писать самостоятельно для своих нужд и целей в том стиле, в котором пишете Вы, чтобы разбираться в исходном коде при необходимости. Все задачи в этом посте решены при помощи копирования одного и того же объекта. Не исключено, что существуют специфические задачи, в которых это не сработает.

UPD: Для ускорения программ можно быстро вычислять остатки от делений на модули 2³¹ - 1 и 2⁶¹ - 1. Основная сложность заключается в умножении. Чтобы понять принцип, посмотрите следующий пост от dacin21 в параграфе Larger modulo и его комментарий с объяснениями.

constexpr uint64_t mod = (1ull<<61) - 1;
uint64_t modmul(uint64_t a, uint64_t b){
	uint64_t l1 = (uint32_t)a, h1 = a>>32, l2 = (uint32_t)b, h2 = b>>32;
	uint64_t l = l1*l2, m = l1*h2 + l2*h1, h = h1*h2;
	uint64_t ret = (l&mod) + (l>>61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
	ret = (ret & mod) + (ret>>61);
	ret = (ret & mod) + (ret>>61);
	return ret-1;
}

Задача 1. Поиск всех вхождений одной строки длины n в другую длины m за O(n + m)

Дано: Две строки S и T длин до 50000. Вывести все позиции вхождения строки T в строку S. Индексация с нуля.

Пример: Ввод S = "ababbababa", T = "aba", вывод: 0 5 7.

Ссылка на задачу на acmp.ru.

Задача 2. Поиск наибольшей общей подстроки двух строк длин n и m (n ≥ m) за O((n + m·log(n))·log(m)) и O(n·log(m))

Дано: Длина строк N и две строки A и B длины до 100000. Вывести длину наибольшей общей подстроки.

Пример: Ввод: N = 28, A = "VOTEFORTHEGREATALBANIAFORYOU", B = "CHOOSETHEGREATALBANIANFUTURE", вывод: THEGREATALBANIA

Ссылка на задачу на acm.timus.ru с длиной до 10^5.

Ссылка на задачу на spoj.com с длиной до 10^6.

Задача 3. Нахождение лексикографически минимального циклического сдвига строки длины n за O(n·log(n))

Дано: Строка S длины до 10^5. Вывести минимальный лексикографически сдвиг строки A.

Пример: Ввод: "program", Вывод: "amprogr"

Ссылка на задачу на acmp.ru.

Задача 4. Сортировка всех циклических сдвигов строки длины n в лексикографическом порядке за O(n·log(n)²)

Дано: Строка S длины до 10^5. Вывести номер позиции исходного слова в отсортированном списке циклических сдвигов. Если таких позиций несколько, то следует вывести позицию с наименьшим номером. Во второй строке вывести последний столбец таблицы циклических сдвигов.

Пример: Ввод: "abraka", Вывод: "2 karaab"

Ссылка на задачу на acmp.ru.

Задача 5. Нахождение количества подпалиндромов строки длины n за O(n·log(n))

Дано: Строка S длины до 10^5. Вывести количество подпалиндромов строки.

Пример: Ввод: "ABACABADABACABA", Вывод: 32

Ссылка на задачу на acmp.ru с ограничениями до 10^5.

Ссылка на задачу на acmp.ru с ограничениями до 10^6.

Задача 6. Количество подстрок строки длины n, являющихся циклическими сдвигами строки длины m за O((n + m)·log(n))

Дано: Заданы две строки S и T длины до 10^5. Необходимо определить, сколько подстрок строки S являются циклическими сдвигами строки T.

Пример: Ввод: S = "aAaa8aaAa", T="aAa", Вывод: 4

Ссылка на задачу на acmp.ru.

Задача 7. Количество суффиксов строки длины n, бесконечное расширение которых совпадает с бесконечным расширением всей строки за O(n·log(n))

Дано: Строка S длины до 10^5. Бесконечным расширением строки назовем строку, полученную выписыванием исходной строки бесконечное число раз. Например, бесконечное расширение строки "abс" равно "abcabcabcabcabc...". Необходимо ответить на вопрос, сколько суффиксов исходной строки имеют такое же бесконечное расширение, какое и строка S.

Пример: На входе: S = "qqqq", на выходе 4.

Ссылка на задачу на acmp.ru.

Задача 8. Наибольший общий префикс двух строк длины n с обменом двух произвольных символов одной строки местами за O(n·log(n))

Дано: Строки S и T длиной до 2*10^5. Разрешается один раз обменять местами два произвольных символа строки S или не менять вовсе. Найти максимальную длину наибольшего общего префикса среди всех возможных замен.

Пример: На входе: S = "aaabaaaaaa" и T = "aaaaaaaaab", на выходе 10.

Ссылка на задачу.

На этом все. Надеюсь, этот пост поможет Вам активно применять хэширование и решать более сложные задачи. Буду рад любым комментариям, исправлениям и предложениям. В ближайших планах перевести этот пост на английский язык, поэтому нужны ссылки, где эти задачи можно сдать на английском языке. Возможно, к тому времени Вы внесете существенные корректировки и дополнения в этот пост. Ребята из Индии говорят, что пытались сидеть с гугл-переводчиком и переводить с русского языка посты про полиномиальный хэш и у них это плохо вышло. Делитесь другими задачами и, возможно, их решениями, а также решениями указанных задач не через хэши. Спасибо за внимание!

Полезные ссылки:

Rolling Hash (Rabin-Karp Algorithm)

Anti-Hash test

Выбор точки хэширования

Anti-Double Hash test

Полиномиальные хеши

На просторах интернета с 2004 года существует игра "Жук".

Цель игры — построить такой лабиринт, в котором жук найдет выход за наибольшее количество шагов. Жук всегда находит выход, то есть, его алгоритм поиска выхода корректен, но не оптимален. Запирать жука нельзя, в конкурсе участвуют только лабиринты, из которых есть выход.

Существует также одноименная олимпиадная задача по программированию, посвященная этому жуку. В ней подробно описан алгоритм движения жука, поэтому, решив эту задачу, можно скармливать лабиринты жуку на домашнем компьютере:

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

На сайте есть таблица рекордов по всем лабиринтам, в которой указан пользователь и результат прохождения жуком его самого сложного лабиринта. Я там есть, 5-е место с 10 млн ходов. Кстати, 250 млн ходов у победителя было получено совсем недавно, еще в мае его не было.

За 14 лет существования игры не было получено хороших оценок сверху на максимально возможное количество шагов жука, а также не был получен алгоритм построения худшего теста.

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

UPD: для ускорения прогонки жука на ваших лабиринтах онлайн жмите F12 (консоль разработчика) и пропишите speed = 1/512. Для регистрации рекорда не нужно ждать, просто жмите сохранить и результат будет отправлен на сервер. Там он будет проверен и таблица будет обновлена.

Здравствуйте! Есть q запросов вида x_i к массиву a из n элементов — целых 32-битных беззнаковых чисел. Каждый запрос — побитовый xor всех элементов массива с элементом x_i. После каждого запроса нужно выводить максимум на всем массиве. Ограничения на n и q порядка 2·10⁵.

Я помню задачу с нахождением суммы на отрезке и применением xor на отрезке — там она решалась построением 32 деревьев отрезков под каждый разряд, а сумма формировалась как сумма элементов по модулю 2 умноженная на соответствующую степень двойки, которой соответствует дерево отрезков.

В этой же задаче отрезок не произвольный, а фиксированный — весь массив. Как решать эту задачу?

Приведу изначальную формулировку, может она легче: есть два массива a и b длины n, нужно найти максимальное значение среди всех попарных xor элементов пар (a[i], b[j]) элементов массивов.

Ну и еще более изначальную: есть корневое дерево с n вершинами и n-1 ребрами. На ребрах записаны некоторые целые числа, а на каждом ребре одно число. Нужно выбрать две различные вершины дерева u и v такие, что выписав все числа на пути от вершины u до корня и от вершины v до корня, а затем выполнить операцию xor для всех выписанных элементов, итоговое значение было бы максимальным среди всех пар (u,v). В ответ выдать это значение. Задача

UPD: Сдал задачу при помощи сортировки + неявного бора + бинарного поиска за O(n * log(n) * WORD_WIDTH). Код к задаче, исходная формулировка оказалась легче — не пришлось изменять элементы массива.

Зачастую мне удается подобрать контр-тесты к своим полным решениям уже после их сдачи. Я не помню всех задач, но я точно валил свое accepted-решение задачи с сортировкой по полярному углу в long double с применением atan2 в одном из первых образовательных раундов (или даже в самом первом). Есть ли на codeforces механизм добавления тестов к задачам в уже завершенных контестах и перетестирование решений? Если нет, то мне кажется, что сохранение возможности взламывать решения в любой момент времени с момента завершения контеста и добавление тестов из успешных взломов было бы неплохим усовершенствованием, ведь многие люди дорешивают старые задачи. Если каждый раз перетестировать решения затратно, то можно, например, накапливать изменения и делать это раз в сутки, пока все спят или ищут на какую кнопку стать легендарным гроссмейстером, и уведомлять пользователей о падении их старых решений.

UPD: Приношу свои извинения, задача C. Ближайшие вектора из образовательного раунда 1 была упомянута ошибочно, так как в ней ограничения на координаты 10^4 по модулю. Я перепутал ее с задачей 4774. Выпуклая оболочка с сайта e-olymp, где проходит неверное решение, не смотря на наличие 34 тестов к задаче. В ней ограничения на координаты до 10^9 по модулю, а, как известно, atan2(1, -10^9) и atan2(1, -10^9+1) отличаются в 18-м знаке после запятой. Используемый тип long long конвертируется в double и ошибка неизбежна. Нужно либо писать решение в целых числах, либо явно конвертировать в long double.

Все заминусовано в комментах, это какой-то флешмоб неадекватов? Если нет, то почему? Ну а если да, то зачем?

UPD: сдалось, доказательство dalex

Не могу решить задачу 788. Интересная игра с числами с сайта acmp.ru. Жадное решение (отсортировать пары по (a, b) и по (b, a) в двух массивах, идти по ним двумя указателями и набирать для каждого игрока из начала массивов еще никем не взятые пары) — не проходит, на этом идеи закончились. Подкиньте, пожалуйста, идеи, или направьте рассуждения в правильном направлении, может на codeforces есть аналогичная задача с разбором, заранее спасибо.

Последнее обновление: решение за O(n) динамическим программированием

Здравствуйте! Задача 736. Удаление с acmp.ru. Суть задачи: на каждой итерации из массива длины n до 5·10⁶ удаляются элементы с индексами k, 2k, 3k и т.д. Затем все неудаленные элементы сдвигаются и операция повторяется до тех пор, пока длина массива не станет меньше k. Нужно для каждого элемента во вводе сообщить, каким по счету он уйдет.

UPD: Решено за O(q * sqrt(n)). Решение Wild_Hamster

/*
    "Удаление": математика, оптимизация вычислений, O(q*sqrt(n))
*/

#include <stdio.h>
#include <algorithm>
#include <cassert>

inline int solve(int n, int k, int a) {
// Работает за O(sqrt(n))

    const int answ = n;
    while (a >= k && a % k != 0) {
        // Оптимальный параметр для n / k:
        int x = n / k;
        int t1 = (n - x * k + x - 1) / x;
        
        // Оптимальный параметр для a / k:
        int y = a / k;
        int t2 = (a - y * k + y - 1) / y;
        
        // Минимум из оптимальных параметров:
        int t = std::max(1, std::min(t1, t2));
        
        // Переход к следующей итерации:
        n -= t * x;
        a -= t * y;
    }
    return answ - n + a / k;
}
 
int main() {
    int n, k, q;
    scanf("%d %d %d", &n, &k, &q);
    
    while (q--) {
        int item;
        scanf("%d", &item);
        printf("%d\n", solve(n, k, item));
    }

     
    return 0;
}

UPD2: Так как задача находится в теме "структуры данных", то авторское решение использует некую хитрую структуру данных, которая укладывается и в предел по времени, и в предел по памяти. На это же и намекают лучшие попытки к задаче: там есть решения с 39 МБ и 59 МБ по памяти.

Попробовал сдать код деревом отрезков за O(n log(n)). На acmp.ru — Memory Limit Exceeded (на ideone.com 0.780 с, 84 MB)

UPD3: Написал код деревом Фенвика за O(n log(n)). На acmp.ru — Time Limit Exceeded на 19-м тесте. (на ideone.com 0.480 с, 40 MB).

UPD4: Решение динамическим программированием за O(n): можно решать задачу на префиксе количества итераций, совершенных алгоритмом. Для того, чтобы дать ответ, нам для каждого элемента нужно определить, на какой итерации алгоритма он будет удален, и какому элементу на предыдущей итерации он эквивалентен и использовать уже посчитанный ответ для этого элемента.

/*
    "Удаление": динамическое программирование, O(n)
*/

#include <stdio.h>
#include <vector>

int main() {
    int n, k, q;
    scanf("%d %d %d", &n, &k, &q);
    
    std::vector<int> answer(1+n), stages(1+n), erased(1+n);
    
    // Вычисление ответа для элементов, удаленных на первой итерации:
    for (int i = 1; i * k <= n; ++i) {
        answer[i * k] = i;
    }
    
    // Находим, куда перейдут элементы после удаления на последующих итерациях:
    for (int curr = k; curr <= n; ++curr) {
        if (answer[curr] == 0) {
            int prev = curr - curr / k;
            answer[curr] = answer[prev];
            stages[curr] = stages[prev] + 1;
        }
    }
    
    // Предподсчитаем количество удаленных элементов после каждой итерации:
    for (int i = 1; i <= n; ++i) {
        erased[i] = erased[i-1] + (n - erased[i-1]) / k;
    }
    
    // Отвечаем на запросы:
    while (q--) {
        int item;
        scanf("%d", &item);
        printf("%d\n", answer[item] + erased[stages[item]]);
    }
    
    return 0;
}

Здравствуйте! На acmp.ru есть задача о разрезании квадратного торта со свечками: необходимо определить, можно ли разрезать торт одним прямолинейным разрезом на две части равной площади так, чтобы все свечки оказались в одной половине. Задача с четвертьфинала Чемпионата мира Восточно-сибирского региона 2009 года.

Мое решение следующее:

1. Прямой разрез обязательно должен проходить через центр квадрата, поэтому масштабируем координаты точек в два раза, смещаем на сторону квадрата. После этой операции центр квадрата находится в центре координат. Если какая-то точка лежит в центре квадрата — ответ NO. Если всего одна точка — ответ YES.

2. Сортируем точки по полярному углу. Используя предикат x > 0 || (x == 0 && y > 0) разбиваем множество всех точек на две части, каждую из которых сортируем в целых числах, затем склеиваем две части и дублируем первую точку в конец.

3. Смотрим на знак векторного произведения соседних векторов. Если он отрицателен, то угол между векторами строго больше 180 градусов, следовательно можно провести разрез по прямой линии — ответ YES. Если ничего не подошло, ответ — NO.

Код выдает неправильный ответ на 9-м тесте.

UPD. Проблема решена. Контр-тест, который валит решение выше:

100
2
51 50
52 50

В данном случае после преобразования получаются векторы (2, 0) и (4, 0), которые имеют один и тот же полярный угол, их векторное произведение равно нулю, значит решение выдаст неверный ответ NO, а должно YES.

Исправить это просто: после сортировки нужно удалить повторяющиеся углы. Сделать это можно при помощи std::vector::erase и std::unique. Исправленное решение в целых числах, которое прошло все тесты.

Здравствуйте!

Дали задание написать сбалансированное дерево поиска с операциями: пробежаться по всем элементам за O(n) в порядке неубывания, вставить новый элемент за O(log(n)), найти определенный элемент за O(log(n)). Известно, что на любой момент работы программы в дереве  ≤ n элементов. Дерево должно работать поверх массива размера O(n).

Перед тем, как начать думать о написании своей реализации, полез в интернет, а там ничего нет о реализации сбалансированных деревьях на массивах, в связи с этим встал вопрос: может это и не возможно сделать вовсе?

Здравствуйте! На acmp.ru есть интересная задача — самая сложная задача с полуфинала ВКОШП 2016/2017 Красноярского края. Ниже приведу краткое условие.

Есть циклический массив длины n (1 ≤ n ≤ 10⁵) из целых неотрицательных чисел (все его элементы расположены по кругу), сумма элементов которого не превосходит 10⁹. Требуется для каждого k от 1 до n определить, можно ли разбить отрезок [1..n] массива на k непересекающихся отрезков, сумма элементов в которых равна и каждый элемент покрыт хотя бы одним отрезком. Так как массив циклический, то за элементом с индексом n следует элемент с индексом 1, таким образом, последний отрезок может переходить через границу массива.

Раньше этот пост содержал просьбу помочь, так как не проходило мое решение. После обсуждения и изучения контр-тестов, предоставленных YANORMALNOSUPERGOOD, выяснилось, что это решение и не должно проходить, так как оно основывается на жадности, после чего было придумано следующее решение: для каждого делителя s_i суммы всех элементов S для каждого отрезка [l,  r], содержащего начальный элемент массива, при помощи бинарного поиска и префикс-сумм предпринимается попытка построить еще k_i =  отрезков (k_i ≤ n), сумма на которых в точности равна s_i. Если я ничего не перепутал, то это решение занимает O(count(k_i)·n + sum(k_i)·log(n)) ≈ O(n^4 / 3·log(n)·log(log(n))) по времени. На сервере оно работает за 1.5 секунды.

Вопрос: можно ли решить оптимальнее, легче (возможно, за один проход по массиву), и нет ли контр-тестов, которые должны вызывать TLE у решения выше?

UPD: Aeon и YANORMALNOSUPERGOOD показали, что оптимальнее решить можно, а именно, за время O(n·numberOfDivisors(S). Причем, в оценке участвуют только делители, которые не превосходят n. Ключевой момент — избавиться от бинарного поиска, который выполнялся sumOfDivisors(S) раз. Для этого можно перейти к динамическому программированию и для одного делителя предподсчитать определенную величину, которая позволит за O(1) отвечать на запрос о максимальном количестве искомых отрезков. Решения с указанной асимптотикой приведены в комментариях здесь и здесь.

Возможно, асимптотику можно еще улучшить, воспользовавшись тем фактом, что если мы выяснили, что для какого-то делителя суммы ответ 0, то и для всех делителей, кратных ему, ответ 0, а если для какого-то делителя ответ 1, то и для всех делителей, на которые он делится, ответ 1.

Здравствуйте! Идеи, как решить следующую задачу, зашли в тупик, поэтому нужна помощь:

У нас есть массив a[1...n] (n ≤ 200000, 1 ≤ a[i] ≤ 1000000) из целых чисел и есть q запросов к этому массиву (q ≤ 200000) вида: l_i, r_i, x_i (1 ≤ l_i ≤ r_i ≤ n, 1 ≤ x_i ≤ 1000000). Для каждого запроса мы должны ответить сколько есть различных индексов j таких что l_i ≤ j ≤ r_i и gcd(a[j], x) = 1.

Вот, что удалось осознать:

1) До 1.000.000 всего 78.498 простых чисел.

2) Каждое число во вводе не может иметь более 7 различных простых делителей, так как 2 × 3 × 5 × 7 × 11 × 13 × 17 = 510.510

3) Задачу можно решать только на префиксе, так как: count(l_i, r_i, x_i) = count(1, r_i, x_i) - count(1, l_i - 1, x_i), l_i > 1

Ограничения по времени 1.5 с, памяти 32 MB.

Задача была на полуфинале ВКОШП в Красноярском крае в сезоне 2017/2018 как задача "G. Скучные запросы". Разбор и архив жюри найти не удалось, а очень хочется. Здесь ее можно сдать, ограничения по времени немного увеличены в сравнении с оригиналом, так как сервер не самый быстрый, а система 32-битная.

Пример:

6
1 2 3 4 5 6
4
1 6 1 --> 6
1 6 2 --> 3
2 4 6 --> 0
3 6 10 --> 1

UPD: решено Aeon. Memory: 21 MB, Time: 1.2 s на худшем случае.

Например, ко второму образовательному раунду? Это так задумано или забыли открыть после серии обновлений платформы? Если задумано, то почему? Среди официальных раундов встречаю такое впервые, раньше встречал эту ситуацию с раундами в разделе "тренировки", например, с задачами с квалификационного этапа ACM-ICPC моего региона

Привет, codeforces! В рамках проекта по подготовке к олимпиадам по программированию в качестве задания была выдана эта задача на двумерное динамическое программирование.

Кратко суть задачи: дана матрица размера n², где n ≤ 200 , в которой есть нулевые и ненулевые элементы. Расстояние на матрице между ячейками (x₁, y₁) и (x₂, y₂) определяется как dist = |x₁ - x₂| + |y₁ - y₂|. Каждый нулевой элемент нужно заменить ближайшим к нему ненулевым элементом, а если подходящих элементов несколько, то оставить без изменений.

Я написал решение на C++, которое получило вердикт Accepted, и решил ради эксперимента перенести его на python3, чтобы попрактиковаться с новым языком программирования. Вот что из этого вышло. Действий получается порядка O(n²), но с большой константой. При n = 200 должно пройти, но не проходит — вердикт TLE. Можно ли как-нибудь ускорить решение на python3, заменив ввод-вывод более быстрым (уже вроде как заменил, но может можно еще быстрее), или применив какие-нибудь другие хитрости, так, чтобы оно получило вердикт Accepted?

Кратко суть решения:

1. Поиск ближайшего элемента для (x, y) среди всех элементов (x * , y * ) таких что, x ≥ x *  и y ≥ y * .
2. Поиск ближайшего элемента для (x, y) среди всех элементов (x * , y * ) таких что, x ≤ x *  и y ≥ y * .
3. Поиск ближайшего элемента для (x, y) среди всех элементов (x * , y * ) таких что, x ≥ x *  и y ≤ y * .
4. Поиск ближайшего элемента для (x, y) среди всех элементов (x * , y * ) таких что, x ≤ x *  и y ≤ y * .
5. Объединение ответов

Для каждого прохода 1-4 используем метод ДП, комбинируя ответы для соседних элементов, например, в 1 пункте: answer[x][y] = combine(answer[x - 1][y], answer[x][y - 1]) + 1

Не знаю, как правильно решить следующую задачу. Есть идеи, но они не проходят. Кто знает, направьте в верное русло, пожалуйста. Также, если знаете похожие задачи, то поделитесь ссылками на них. Оригинальная формулировка задачи с тестами доступна здесь

Во входном файле до 50 тестов. Каждый тест — отдельная подзадача. Нужно вывести ответ для каждой подзадачи с новой строки. Подзадача состоит в следующем:

На нашем пути есть от 1 до 20 засад, в каждой засаде сидят k[i] разбойников (от 1 до 1000), чтобы они нас пропустили, нужно c[i] монет (от 1 до 1000). Изначально в нашем отряде 0 наемников.

Мы можем:

1. Нанять бандитов, сидящих в засаде, потратив 2 * c[i] монет

2. Заплатить бандитам c[i] монет, чтобы они нас пропустили

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

Необходимо проехать все засады, потратив наименьшую сумму денег. В ответ выдать эту сумму денег.

Ограничения: 3 секунды, 256 МБ на тест, таким образом, 0.06 секунд и 256 МБ на одну подзадачу.

Думал в сторону двумерного ДП. Параметры:

• количество пройденных засад

• набранная сумма

Для состояния dp[k][sum] хранить оптимальную тройку (n1, n2, n3) — сколько наемников могут участвовать в одной битве, двух и трех соответственно. Для недостижимых позиций ( - 1,  - 1,  - 1). Но не ясно, как выбирать из двух возможных троек лучшую при одинаковых переходах. Если выбирать по сумме, то тройка (1000, 0, 0) окажется лучше тройки (0, 0, 999). но все наемники убегут после первой битвы. Если выбирать по компонентам, то (0, 0, 2), окажется лучше, чем (999, 0, 1), но тогда не победить 1000 разбойников. Поэтому вариант с тройками не проходит, а больше адекватных идей нет.