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

Правка ru1, от thematdev, 2021-03-19 20:40:52

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

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

Вторая часть это подсчёт ответа. Мы должны для каждого числа вида $$$\frac{\frac{x}{d_x} + d}{c}$$$ прибавить $$$2^k$$$, где $$$k$$$ -- количество различных простых делителей. ($$$d_x$$$ делится на $$$x$$$). Если не предподсчитывать, то это будет $$$O(\log x)$$$ на делитель, иначе $$$O(1)$$$.

Теперь попробуем подобрать числа $$$c, d, x$$$ чтобы взломать решение за $$$O(t\sqrt{x} \log x + N \log \log N)$$$. Поскольку мы считаем количество различных простых делителей у чисел вида $$$\frac{\frac{x}{d_x} + d}{c}$$$, мы будем использовать $$$c = 1$$$. Также мы факторизуем число $$$x$$$. Сначала найдем $$$x$$$ с наибольшим количеством делителей, и этот $$$x$$$ есть $$$8648640$$$. Затем попробуем максимизировать

$$$\sum\limits_{d_x \mid x} s(x/d_x + d)$$$

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

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

https://codeforces.me/contest/1499/hacks/714699

https://codeforces.me/contest/1499/hacks/714697

https://codeforces.me/contest/1499/hacks/714692

https://codeforces.me/contest/1499/hacks/714688

https://codeforces.me/contest/1499/hacks/714629

https://codeforces.me/contest/1499/hacks/714683

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

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

User: haruki_K

Submission: 110353111

Существуют и другие сильные взломы, например $$$d = (3 \cdot 5 \cdot 7 \cdot 11 \dots) - x$$$. Но также есть более странные вещи. Например три посылки(все из них мои, и все из них имеют разное время на макстесте): 110370237, 110420633, 110439475

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

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

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru2 Русский thematdev 2021-03-19 20:42:03 47 (опубликовано)
ru1 Русский thematdev 2021-03-19 20:40:52 3063 Первая редакция перевода на Русский (сохранено в черновиках)
en9 Английский thematdev 2021-03-19 20:11:43 0 (published)
en8 Английский thematdev 2021-03-19 20:08:17 203
en7 Английский thematdev 2021-03-19 20:02:34 10
en6 Английский thematdev 2021-03-19 19:57:46 1566
en5 Английский thematdev 2021-03-19 19:43:25 52 Reverted to en3
en4 Английский thematdev 2021-03-19 19:40:39 52
en3 Английский thematdev 2021-03-19 19:36:55 2072
en2 Английский 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 Английский thematdev 2021-03-19 19:18:15 1065 Initial revision (saved to drafts)