### [А. Ярмарка оружия](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/problem/A) [реализация, математика]↵
↵
Необходимо последовательно сравнить силы наборов, если текущая сила строго больше максимальной предыдущей, то обновляем максимальную и индекс лучшего набора.↵
Вычислить силу набора можно было в нецелых числах как (сумма $s_{i,j}$ / $w_i$), или сохранить числитель и знаменатель дроби ($sum_{s_max}$ и $w_max$) и сравнивая с текущим набором домножить обе части на ($w_max \cdot w_i$).↵
Не стоит забывать, что суммирование $10^5$ чисел до $10^9$ приведёт к переполнению типа integer.↵
↵
Асимптотика: $O(n \cdot max(w_i))$↵
↵
[Код в нецелых числах](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29433143)↵
↵
[Код в целых числах](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29429166)↵
↵
### [B. Имённо-фамильный никнейм](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/problem/B) [перебор, строки]↵
↵
Любое решение сводится к тому, чтобы максимизировать подстроку в $n$ (ведь чем больше символов мы возьмём из $n$, тем меньше потребуется из $f$). ↵
↵
Обозначим длину такой подстроки за $k$.↵
↵
1) Наивное решение может проверять все подстроки строки $n$ для поиска максимального $k$, после чего искать недостающий конец строки в $f$. Это будет работать за $O(q \cdot |n|^2 + q \cdot |f|)$ в теории, однако лишь в худшем частном случае, когда множество раз наблюдается значительное совпадение подстроки с первой часть строки $s_i$ (пример: $n$ = " $\mathtt {aaaaaaaaab}$ ", $f$ = " $\mathtt {aaaaaabbbb}$ ", и все $s_i$ = " $\mathtt {aaaaabbbbb}$ ").↵
↵
[Код](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29433452)↵
↵
2) Подсчитать все возможные подстроки для $n$ за $|n|^2$, сложить в set[string] или бор, или подсчитать хеши (это будет работать аналогично set[string]). Теперь для каждого $s_i$ можно последовательно искать $k$, после чего можно пройтись последовательно по $f$, узнав, есть ли там оставшиеся $|s_i| - k$ символов. При использовании set[string] или хешей можно также искать $k$ бинарным поиском, укорачивая или удлиняя текущую строку до длины $M$ на каждой итерации и ища ей соответствие в подстроках $n$.↵
↵
Асимптотики такого решения:↵
↵
- Для хешей или set<string>:↵
- если искать $k$ последовательно: $O(q \cdot k \cdot log_2(|n|^2) + q \cdot |f|)$↵
- бинарным поиском: $O(q \cdot log_2(k) \cdot log_2(|n|^2) + q \cdot |f|)$↵
- Для бора: $O(q \cdot k + q \cdot |f|)$↵
↵
[Код с set[string], последовательная проверка k](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29433604)↵
↵
[Код с set[string], бинарный поиск по k](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29433637)↵
↵
[Код с бором](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29433684)↵
↵
3) Развернём $n$, $f$, и $s_i$ задом наперёд. Тогда нам нужно максимизировать не подстроку, а подпоследовательность в $f$, в этом единственное отличие от предыдущего варианта. Искать $k$ для подпоследовательности можно только последовательно, после чего нам нужно найти в $n$ подстроку длины $|n| - k$, для чего опять же следует предподсчитать все возможные подстроки для $n$ за $|n|^2$ и сложить их в какую-нибудь структуру.↵
↵
Асимптотика решения:↵
↵
- Для хешей или set[string]: $O(q \cdot k + q \cdot log_2(|n|^2))$↵
- Для бора: $O(q \cdot k + q \cdot |n|)$↵
↵
### [C. Два великана](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/problem/C) [игры, математика]↵
↵
Очевидно, что размер кучи от $1$ до $x$ является выигрышным для Тора, т.к. он может сломать её одним ударом. ↵
↵
А теперь давайте подумаем насчет $n = x + 1$. Если Тор сломает $1$ кирпич, останется $x$ кирпичей, и Арен победит, если Тор сломает $x$ кирпичей, Арену останется $1$ кирпич и он тоже выиграет.↵
↵
Значит, куча размера $x + 1$ всегда является $проигрышной$ для Тора. А это в свою очередь значит, что все кучи от $x + 2$ до $2x + 1$ являются выигрышными — Тор может всегда сломать столько кирпичей, что Арену достанется куча размера $x + 1$ и тот проиграет.↵
↵
Подобным образом рассуждаем дальше, применяя важное правило теории игр — если из состояния текущего игрока нет способа привести состояние в проигрышное (чтобы в нём оказался другой игрок, а текущий выиграл), значит для текущего игрока состояние проигрышное, и при оптимальной игре обеих сторон он всегда будет в проигрышном состоянии, а другой игрок наоборот, в выигрышном.↵
↵
И получаем, что проигрышными для Тора являются только кучи кратные $x + 1$ ($x + 1$, $2x + 2$, $3x + 3$, ..). Тогда ответ на отрезке $[1; n]$ можно найти как $(n - \frac{n}{x + 1})$, обозначим это функцией $f(n)$, тогда ответ на отрезке $[L; R]$ равняется $f(R) - f(L - 1)$.↵
↵
Асимптотика: $O(q)$↵
↵
[Код](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29433974)↵
↵
### [D. Кровожадная функция](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/problem/D) [математика]↵
↵
Итак, $f(x) = a^x \cdot (b + x)^x \cdot c$. Нам даны три значения этой функции, давайте распишем их в полном виде:↵
↵
$f(0) = a^0 \cdot (b + 0)^0 \cdot c = 1 \cdot 1 \cdot c = c$↵
↵
$f(1) = a^1 \cdot (b + 1)^1 \cdot c = a \cdot (b + 1) \cdot c$↵
↵
$f(2) = a^2 \cdot (b + 2)^2 \cdot c$↵
↵
Как видим, $c = f(0)$. Значит можно упростить два других выражения:↵
↵
$\frac{f(1)}{f(0)} = a \cdot (b + 1)$↵
↵
$\frac{f(2)}{f(0)} = a^2 \cdot (b + 2)^2$↵
↵
Что мешает избавиться от квадрата во втором выражении?↵
↵
$\sqrt{\frac{f(2)}{f(0)}} = \sqrt{a^2 \cdot (b + 2)^2} = a \cdot (b + 2)$↵
↵
Теперь можно найти $a$:↵
↵
$\sqrt{\frac{f(2)}{f(0)}} - \frac{f(1)}{f(0)} = a \cdot (b + 2) - a \cdot (b + 1) = (ab + 2a) - (ab + a) = a$↵
↵
И $b$:↵
↵
$\frac{f(1)}{f(0) \cdot a} = b + 1$↵
↵
$\frac{f(1)}{f(0) \cdot a} - 1 = b$↵
↵
Асимптотика: $O(1)$↵
↵
[Код](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29433986)↵
↵
### [E. Интересная структура](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/problem/E) [математика, реализация]↵
↵
Так как $x$ не превосходит $100$, можно было хранить массив $cnt[100]$ и прибавлять или отнимать количество чисел в явном виде. При запросе третьего типа необходимо пройтись по всем числам от $1$ до $100$ и умножить текущий остаток на $x^{cnt[x]}$ по модулю $m$.↵
↵
Однако $cnt[x]$ может быть весьма большим, и каждый раз умножать в явном виде слишком долго. Здесь есть два пути оптимизации:↵
↵
1) будем хранить стек значений $val[x]$, где $val[x][ cnt[x] ]$ равняется $x^{cnt[x]}$ % $m$. Сделаем $val[x][0] = 1$ изначально для всех $x$ от $1$ о $100$, тогда при добавлении нового числа $x$ в структуру будем помешать в конец стека новое значение на основе предыдущего: `val[x].push_back( (val[x][ cnt[x] ] * x) % m );`↵
А при запросе второго типа нам просто нужно убрать последнее значение из стека: `val[x].pop_back()`.↵
↵
Также вместо стека можно было использовать массив $val[100][100000]$ (т.к. очевидно что любое число будет повторяться не более $q$ раз, т.е. не более $10^5$ раз), но это более затратно по памяти.↵
↵
Асимптотика: $O(q + 100 \cdot cnt_t3)$↵
↵
[Код со стеком](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29430943)↵
↵
[Код с массивом](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29431275)↵
↵
2) воспользуемся быстрым возведением в степень (более подробно [здесь](http://e-maxx.ru/algo/binary_pow), основная идея в том, что $x^n = x^{n / 2} \cdot x^{n / 2}$)↵
↵
Асимптотика: $O(q + 100 \cdot cnt_t3 \cdot log2(cnt[x])$.↵
↵
[Код](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29430303)↵
↵
+) можно не пересчитывать ответ каждый раз на запрос третьего типа, а лишь в тех случаях когда мы вносили изменение (т.е. это оптимизация на случай множественный запросов третьего типа).↵
↵
+) можно хранить числа не в явном виде, а факторизовать их (раскладывать на простые) и считать ответ по степеням простых чисел от $1$ до $100$ (их 25 штук). Авторское решение использовало именно факторизацию + быстрое возведение в степень: $O(q \cdot log2(x) + 25 \cdot cnt_t3 \cdot log2(cnt[x]))$.↵
↵
[Код авторского решения](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29434003)↵
↵
### [F. Статически полный граф](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/problem/F) [тролль]↵
↵
Если Вы хоть немного знаете о том, что такое графы, Вы сможете решить эту задачу. ↵
↵
Главное — внимательно прочитать все условия и подумать что они означают.
↵
Необходимо последовательно сравнить силы наборов, если текущая сила строго больше максимальной предыдущей, то обновляем максимальную и индекс лучшего набора.↵
Вычислить силу набора можно было в нецелых числах как (сумма $s_{i,j}$ / $w_i$), или сохранить числитель и знаменатель дроби ($sum_{s_max}$ и $w_max$) и сравнивая с текущим набором домножить обе части на ($w_max \cdot w_i$).↵
Не стоит забывать, что суммирование $10^5$ чисел до $10^9$ приведёт к переполнению типа integer.↵
↵
Асимптотика: $O(n \cdot max(w_i))$↵
↵
[Код в нецелых числах](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29433143)↵
↵
[Код в целых числах](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29429166)↵
↵
### [B. Имённо-фамильный никнейм](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/problem/B) [перебор, строки]↵
↵
Любое решение сводится к тому, чтобы максимизировать подстроку в $n$ (ведь чем больше символов мы возьмём из $n$, тем меньше потребуется из $f$). ↵
↵
Обозначим длину такой подстроки за $k$.↵
↵
1) Наивное решение может проверять все подстроки строки $n$ для поиска максимального $k$, после чего искать недостающий конец строки в $f$. Это будет работать за $O(q \cdot |n|^2 + q \cdot |f|)$ в теории, однако лишь в худшем частном случае, когда множество раз наблюдается значительное совпадение подстроки с первой часть строки $s_i$ (пример: $n$ = " $\mathtt {aaaaaaaaab}$ ", $f$ = " $\mathtt {aaaaaabbbb}$ ", и все $s_i$ = " $\mathtt {aaaaabbbbb}$ ").↵
↵
[Код](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29433452)↵
↵
2) Подсчитать все возможные подстроки для $n$ за $|n|^2$, сложить в set[string] или бор, или подсчитать хеши (это будет работать аналогично set[string]). Теперь для каждого $s_i$ можно последовательно искать $k$, после чего можно пройтись последовательно по $f$, узнав, есть ли там оставшиеся $|s_i| - k$ символов. При использовании set[string] или хешей можно также искать $k$ бинарным поиском, укорачивая или удлиняя текущую строку до длины $M$ на каждой итерации и ища ей соответствие в подстроках $n$.↵
↵
Асимптотики такого решения:↵
↵
- Для хешей или set<string>:↵
- если искать $k$ последовательно: $O(q \cdot k \cdot log_2(|n|^2) + q \cdot |f|)$↵
- бинарным поиском: $O(q \cdot log_2(k) \cdot log_2(|n|^2) + q \cdot |f|)$↵
- Для бора: $O(q \cdot k + q \cdot |f|)$↵
↵
[Код с set[string], последовательная проверка k](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29433604)↵
↵
[Код с set[string], бинарный поиск по k](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29433637)↵
↵
[Код с бором](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29433684)↵
↵
3) Развернём $n$, $f$, и $s_i$ задом наперёд. Тогда нам нужно максимизировать не подстроку, а подпоследовательность в $f$, в этом единственное отличие от предыдущего варианта. Искать $k$ для подпоследовательности можно только последовательно, после чего нам нужно найти в $n$ подстроку длины $|n| - k$, для чего опять же следует предподсчитать все возможные подстроки для $n$ за $|n|^2$ и сложить их в какую-нибудь структуру.↵
↵
Асимптотика решения:↵
↵
- Для хешей или set[string]: $O(q \cdot k + q \cdot log_2(|n|^2))$↵
- Для бора: $O(q \cdot k + q \cdot |n|)$↵
↵
### [C. Два великана](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/problem/C) [игры, математика]↵
↵
Очевидно, что размер кучи от $1$ до $x$ является выигрышным для Тора, т.к. он может сломать её одним ударом. ↵
↵
А теперь давайте подумаем насчет $n = x + 1$. Если Тор сломает $1$ кирпич, останется $x$ кирпичей, и Арен победит, если Тор сломает $x$ кирпичей, Арену останется $1$ кирпич и он тоже выиграет.↵
↵
Значит, куча размера $x + 1$ всегда является $проигрышной$ для Тора. А это в свою очередь значит, что все кучи от $x + 2$ до $2x + 1$ являются выигрышными — Тор может всегда сломать столько кирпичей, что Арену достанется куча размера $x + 1$ и тот проиграет.↵
↵
Подобным образом рассуждаем дальше, применяя важное правило теории игр — если из состояния текущего игрока нет способа привести состояние в проигрышное (чтобы в нём оказался другой игрок, а текущий выиграл), значит для текущего игрока состояние проигрышное, и при оптимальной игре обеих сторон он всегда будет в проигрышном состоянии, а другой игрок наоборот, в выигрышном.↵
↵
И получаем, что проигрышными для Тора являются только кучи кратные $x + 1$ ($x + 1$, $2x + 2$, $3x + 3$, ..). Тогда ответ на отрезке $[1; n]$ можно найти как $(n - \frac{n}{x + 1})$, обозначим это функцией $f(n)$, тогда ответ на отрезке $[L; R]$ равняется $f(R) - f(L - 1)$.↵
↵
Асимптотика: $O(q)$↵
↵
[Код](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29433974)↵
↵
### [D. Кровожадная функция](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/problem/D) [математика]↵
↵
Итак, $f(x) = a^x \cdot (b + x)^x \cdot c$. Нам даны три значения этой функции, давайте распишем их в полном виде:↵
↵
$f(0) = a^0 \cdot (b + 0)^0 \cdot c = 1 \cdot 1 \cdot c = c$↵
↵
$f(1) = a^1 \cdot (b + 1)^1 \cdot c = a \cdot (b + 1) \cdot c$↵
↵
$f(2) = a^2 \cdot (b + 2)^2 \cdot c$↵
↵
Как видим, $c = f(0)$. Значит можно упростить два других выражения:↵
↵
$\frac{f(1)}{f(0)} = a \cdot (b + 1)$↵
↵
$\frac{f(2)}{f(0)} = a^2 \cdot (b + 2)^2$↵
↵
Что мешает избавиться от квадрата во втором выражении?↵
↵
$\sqrt{\frac{f(2)}{f(0)}} = \sqrt{a^2 \cdot (b + 2)^2} = a \cdot (b + 2)$↵
↵
Теперь можно найти $a$:↵
↵
$\sqrt{\frac{f(2)}{f(0)}} - \frac{f(1)}{f(0)} = a \cdot (b + 2) - a \cdot (b + 1) = (ab + 2a) - (ab + a) = a$↵
↵
И $b$:↵
↵
$\frac{f(1)}{f(0) \cdot a} = b + 1$↵
↵
$\frac{f(1)}{f(0) \cdot a} - 1 = b$↵
↵
Асимптотика: $O(1)$↵
↵
[Код](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29433986)↵
↵
### [E. Интересная структура](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/problem/E) [математика, реализация]↵
↵
Так как $x$ не превосходит $100$, можно было хранить массив $cnt[100]$ и прибавлять или отнимать количество чисел в явном виде. При запросе третьего типа необходимо пройтись по всем числам от $1$ до $100$ и умножить текущий остаток на $x^{cnt[x]}$ по модулю $m$.↵
↵
Однако $cnt[x]$ может быть весьма большим, и каждый раз умножать в явном виде слишком долго. Здесь есть два пути оптимизации:↵
↵
1) будем хранить стек значений $val[x]$, где $val[x][ cnt[x] ]$ равняется $x^{cnt[x]}$ % $m$. Сделаем $val[x][0] = 1$ изначально для всех $x$ от $1$ о $100$, тогда при добавлении нового числа $x$ в структуру будем помешать в конец стека новое значение на основе предыдущего: `val[x].push_back( (val[x][ cnt[x] ] * x) % m );`↵
А при запросе второго типа нам просто нужно убрать последнее значение из стека: `val[x].pop_back()`.↵
↵
Также вместо стека можно было использовать массив $val[100][100000]$ (т.к. очевидно что любое число будет повторяться не более $q$ раз, т.е. не более $10^5$ раз), но это более затратно по памяти.↵
↵
Асимптотика: $O(q + 100 \cdot cnt_t3)$↵
↵
[Код со стеком](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29430943)↵
↵
[Код с массивом](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29431275)↵
↵
2) воспользуемся быстрым возведением в степень (более подробно [здесь](http://e-maxx.ru/algo/binary_pow), основная идея в том, что $x^n = x^{n / 2} \cdot x^{n / 2}$)↵
↵
Асимптотика: $O(q + 100 \cdot cnt_t3 \cdot log2(cnt[x])$.↵
↵
[Код](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29430303)↵
↵
+) можно не пересчитывать ответ каждый раз на запрос третьего типа, а лишь в тех случаях когда мы вносили изменение (т.е. это оптимизация на случай множественный запросов третьего типа).↵
↵
+) можно хранить числа не в явном виде, а факторизовать их (раскладывать на простые) и считать ответ по степеням простых чисел от $1$ до $100$ (их 25 штук). Авторское решение использовало именно факторизацию + быстрое возведение в степень: $O(q \cdot log2(x) + 25 \cdot cnt_t3 \cdot log2(cnt[x]))$.↵
↵
[Код авторского решения](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29434003)↵
↵
### [F. Статически полный граф](http://mirror.codeforces.com/group/mEZDf6b5KH/contest/215086/problem/F) [тролль]↵
↵
Если Вы хоть немного знаете о том, что такое графы, Вы сможете решить эту задачу. ↵
↵
Главное — внимательно прочитать все условия и подумать что они означают.
