Anti-hash test. - Codeforces

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всем привет. Хочу поделиться с общественностью некоторым фактом, который позволяет ломать с гарантией почти любое решение, использующее полиномиальные хэши от строк, где в качестве модуля используется 2⁶⁴ тестом длины порядка нескольких тысяч. Причём, не важно, какое число берётся за точку в полиноме, важно лишь, что все вычисления производятся в типе int64 со стандартными переполнениями — а так пишут большинство олимпиадников.

Для привлечения внимания ключевые слова: не пишите, как написано у е-макса! И только сегодня, только для вас — ломаем решение Petr на задаче 7D - Палиндромность с Codeforces Beta Round #7!

Интересно? Прошу под кат. Для начала, для самых нетерпеливых. Тест генерируется следующим кодом:

const int Q = 11;
const int N = 1 << Q;

char S[N];

// ЛОПАТА ибо нефиг копипастить во время контеста :-)

for (int i = 0; i < N; i++)
    S[i] = 'A' + __builtin_popcount(i) % 2; 
    // кто не знает, эта функция возвращает 
    // количество единиц в двоичной записи числа i

Берём и стравливаем на таком тесте решения двух победителей Codeforces Beta Round #7 — Петра Митричева и Влада Епифанова. Решение vepifanov не содержит хэшей и работает правильно — выдаёт ответ 6. Решение же Petr выдаёт ответ 8. Если чуть-чуть подумать, то становится ясно, что ответ на таком тесте к этой задаче есть (Q + 1) / 2 — Влад безусловно прав. Более того, если в качестве Q взять 20, то решение Влада выдаёт правильный ответ 11, а решение Пети — 2055, что совершенно не похоже на правду.

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

Давайте поймём, в чём дело. Как получается такая строка? Она начинается так:

ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABABBABAABBAABABBA...

Эта строку называют строкой Туэ-Морса по имени товарищей, впервые её упомянувших.

Можно понять, что она получается по рекурсивному правилу S -> S + (not S), стартуя с S = 'A', где под (not S) подразумевается строка после замены A на B и наоборот. Давайте обозначим S для фиксированного Q как S_Q.

Вспомним, что есть полиномиальный хэш от строки S длины l. Это есть величина $\text{[math]}$ . В качестве P мы берём некоторое нечётное число (не знаю, почему многие считают, что его надо брать простым — это ничем не обосновано).

Я утверждаю, что hash(S[0... (2^k - 1)]) при достаточно малом k совпадёт с hash(S[(2^k)... (2^k + 1 - 1)]). Иными словами, при Q = 10, hash(S_Q) = hash(not S_Q). Это будет очень круто, потому что сами по себе S_Q и not S_Q встретятся в б**о**льших строках много-много раз, что следует из рекуррентного соотношения.

Разберёмся, что значит hash(S_Q) = hash(not S_Q). Во-первых, можно смело взять вместо ord('A') и ord('B') нули и единицы в коэффициентах многочлена — тем самым мы просто сократим обе части на $\text{[math]}$ .

Что такое hash(not S_Q) — hash(S_Q)? Нетрудно сообразить, что эта величина есть

T = P⁰ - P¹ - P² + P³ - P⁴ + P⁵ + P⁶ - P⁷... ± P^{2^Q - 1}

--- то есть это знакопеременная сумма степеней P, где знаки чередуются по тому же правилу ABBABAAB... Давайте последовательно выносить из этой суммы множители за скобку:

T = (P¹ - 1)( - P⁰ + P² + P⁴ - P⁶ + P⁸ - P¹⁰ - P¹² + P¹⁴...) = = (P¹ - 1)(P² - 1)(P⁰ - P⁴ - P⁸ + P¹²...) = ... = (P¹ - 1)(P² - 1)(P⁴ - 1)... (P^{2^Q - 1} - 1).

(возможно, ещё на (-1), но это роли не играет).

А теперь основная фишка — эта величина по модулю 2^64 моментально занулится. Почему?

Давайте поймём, на какую максимальную степень двойки делится каждая из Q - 1 скобок. Заметим, что (i + 1)-ая скобка P^{2^i + 1} - 1 = (P^2ⁱ - 1)(P^2ⁱ + 1) делится на i-ую и ещё на какое-то чётное число P^2ⁱ + 1. Это означает, что если i-ая скобка делится на 2^r, то (i + 1)-ая скобка делится по меньшей мере на 2^r + 1.

Вот и выходит, что (P¹ - 1)(P² - 1)(P⁴ - 1)...(P^{2^Q - 1} - 1) делится по меньшей мере на 2·2²·2³·... = 2^{Q(Q — 1) / 2}. Значит достаточно взять Q >= 12. Ура, анти-хэш построен!

Отсюда и выходит такая маленькая длина теста по сравнению с размером модуля 2^64. Выходит, что размер контртеста есть что-то порядка $\text{[math]}$ , если используется x-битный тип данных.

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

Как такой тест образовался? Первое использование такого теста, которое я знаю, было в 2003 году на городской олимпиаде школьников в Санкт-Петербурге в задаче cubes. Эта задача потом перекочевала в проблемсет ЛКШ, в которой множество школьников старших параллелей много лет натыкалось на WA27, отправляя хэшовые решения. Одним из таких школьников был я — к сожалению, мне никто не смог объяснить. что же это за тест, Burunduk1 поковырялся, поковырялся, но в тесте не разобрался. С тех пор в памяти осталась зарубка о той злосчастной задаче.

И вот, по прошествии пары лет, всё же решил сесть и разобраться, что с ней не так. Спасибо Серёже — он же предложил поделиться с общественностью. Я, к слову, пытался нагуглить хоть какой материал в сети по известным человечеству антихэш-тестам, почти ничего дельного не нашёл. Может это общеизвестное знание, а у меня просто навыков поиска англоязычных статей не хватает?

long long p; // множитель, основание, называйте как хотите while (true) { p = random(); long long x = 1; for (int i = 0; i < 300000; i++) { x *= p; if (x == 0 || x == 1) break; } if (x != 0 && x != 1) break; // порядок элемента p больше 300000, видимо, он подойдет }

const int q = 11; const int n = 3 * (1 << q); string s, t; for (int i = 0; i < n; i++) { if (i % 3 != 0) s += 'a', t += 'a'; else { int bit = (__builtin_popcount(i / 3) % 2); s += 'a' + bit; t += 'a' + (1 - bit); } }

Блог пользователя Zlobober