Educational 106 Задача D, TL и взломы

Revision ru2, by thematdev, 2021-03-19 20:42:03

Привет, Codeforces! У меня 13 успешных взломов по задаче D, а также мое решение не прошло систесты(возможно один из моих :) ) У нас есть две части решения

Первая часть посчитать для числа наименьший делитель, это делается решетом Эратосфена за O(NlogN) если просеивать всеми числами, если только простыми, то за O(NloglogN), или же линейным решетом за O(N).

Вторая часть это подсчёт ответа. Мы должны для каждого числа вида xdx+dc прибавить 2k, где k -- количество различных простых делителей. (dx делится на x). Если не предподсчитывать, то это будет O(logx) на делитель, иначе O(1).

Теперь попробуем подобрать числа c,d,x чтобы взломать решение за O(txlogx+NloglogN). Поскольку мы считаем количество различных простых делителей у чисел вида xdx+dc, мы будем использовать c=1. Также мы факторизуем число x. Сначала найдем x с наибольшим количеством делителей, и этот x есть 8648640. Затем попробуем максимизировать

dxxs(x/dx+d)

где s(n) -- сумма степеней простых в факторизации n(именно столько операций мы делаем).

Теперь у нас есть мощный тест. 10000 раз по c=1,d=x=8648640. Ниже вы можете посмотреть взломанные таким способом решения https://mirror.codeforces.com/contest/1499/hacks/714784

https://mirror.codeforces.com/contest/1499/hacks/714699

https://mirror.codeforces.com/contest/1499/hacks/714697

https://mirror.codeforces.com/contest/1499/hacks/714692

https://mirror.codeforces.com/contest/1499/hacks/714688

https://mirror.codeforces.com/contest/1499/hacks/714629

https://mirror.codeforces.com/contest/1499/hacks/714683

Но некоторые решения не сломались, и тому много причин. Иногда люди предподсчитывали наименьшие делители сразу возведенные в степень вхождения, и тогда в среднем по Second Merten's Theorem ответ будет искаться за O(loglogx) для делителя в среднем и наше d уже не работает. Но основная проблема заключается в работе с памятью и кешем процессора, поэтому нужно генерировать различные числа с большим количеством делителей. Это можно сделать рандомом. Но как использовать рандомизированный генератор на кфе? Достаточно просто задать сид для mt19937.

Пример такого взлома

User: haruki_K

Submission: 110353111

Существуют и другие сильные взломы, например d=(35711)x. Но также есть более странные вещи. Например три посылки(все из них мои, и все из них имеют разное время на макстесте): 110370237, 110420633, 110439475

Если вы можете это объяснить, то пожалуйста, сделайте это.

Резюмируя, я хочу сказать, что ограничения были несбалансированы, потому что люди которые придумали идею, и просто не предподсчитали ответ, получили TL. Ограничения в ОБУЧАЮЩИХ раундах не должны быть такими жесткими, особенно учитывая такую погрешность (см.выше).

Также я хочу поблагодарить plagues за отправление моего решения, чтобы порофлить надо мной :)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian thematdev 2021-03-19 20:42:03 47 (опубликовано)
ru1 Russian thematdev 2021-03-19 20:40:52 3063 Первая редакция перевода на Русский (сохранено в черновиках)
en9 English thematdev 2021-03-19 20:11:43 0 (published)
en8 English thematdev 2021-03-19 20:08:17 203
en7 English thematdev 2021-03-19 20:02:34 10
en6 English thematdev 2021-03-19 19:57:46 1566
en5 English thematdev 2021-03-19 19:43:25 52 Reverted to en3
en4 English thematdev 2021-03-19 19:40:39 52
en3 English thematdev 2021-03-19 19:36:55 2072
en2 English thematdev 2021-03-19 19:29:02 664 Tiny change: '} + d}{c}$\n\n\n\n\n' -> '} + d}{c}$, we will use $c = 1$.\n\n\n\n\n'
en1 English thematdev 2021-03-19 19:18:15 1065 Initial revision (saved to drafts)