Интеллектуальный вендинг

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

Заметим, что суммарное количество мелочи в обороте не меняется и составляет c + d. При этом, если c + d ≥ 999 999, то либо у Аркадия всегда найдётся мелочь, чтобы купить очередную бутылку, либо автомат сможет дать сдачу, если платить только с помощью банкнот. В этом случае ответ равен z.

Если же c + d < 999 999, то может быть, что у Аркадия хватает мелочи для совершения покупки без сдачи, может быть, что в автомате достаточно сдачи для покупки банкнотами, но не может быть одновременно выполнено и то и другое, а значит, действия Аркадия определяются однозначно. В этом случае можно было бы промоделировать его действия, однако, их может оказаться слишком много.

Обозначим через a_i количество монет у Аркадия после первых i действий (то есть a₀ = c). Заметим, что если a_i = a_j, то a_i + 1 = a_j + 1 (действительно, следующее действие однозначно определяется величиной a_i), а значит последовательность зацикливается и повторяется. Будем моделировать действия Аркадия по покупке бутылок напитка Квас-Класс, до тех пор пока какое-то из значений a_i не повторится, либо не возникнет ситуация, когда Аркадий не может совершить следующую покупку. В случае повторения значения a_i в качестве ответа выведем величину z, в противном случае номер итерации, на котором не получилось совершить очередную покупку.

Упражнение: придумайте решение задачи, если все банкноты имеют номинал 10¹².

Прогулки за едой

Сначала решим версию задачи, в которой изначальное перемещение совершается бесплатно, а после x съеденных единиц еды перемещение на 1 стоит x. Несложно видеть, что оптимальной стратегией будет дойти до какой-то позиции k, а затем двигаться только в сторону позиции 0, заходя в какие-то рестораны. Пусть мы зашли в ресторан i, тогда вес увеличился на a_i и каждое перемещение также стало на a_i дороже. Поскольку в оптимальной стратегии мы посещаем рестораны только двигаясь в сторону позиции 0, то можно сразу сказать, что посещение ресторана i в итоге обойдётся в a_i·i единиц энергии.

Получаем задачу о рюкзаке, есть n предметов, i-й из них имеет вес a_i·i и стоимость a_i, требуется выбрать подмножество предметов с максимальной суммарной стоимостью и весом не более e. Стандартный способ решения такой задачи предполагает использовать динамическое программирование d(i, x) — максимально возможная суммарная стоимость, если из первых i предметов набрать подмножество веса x.

Произведём замену параметра, будем вычислять динамическое программирование d(i, c) — минимально возможный вес, если из первых i предметов выбрать подмножество суммарного веса c. Далее, будем добавлять предметы в порядке уменьшения значения i, то есть для получения d(i, c) можно использовать только рестораны с i-го по n-й. Какие значения параметра c имеет смысл рассматривать? Любая единица стоимости (то есть насыщения в терминах исходной задачи), полученная в ресторанах с номерами  ≥ i требует затрат хотя бы i единиц энергии, поэтому имеет смысл рассматривать только . Воспользуемся формулами оценки суммы гармонического ряда и получим, что количество значений динамического программирования, которые нам требуется вычислить оценивается как .

Последним штрихом будет учесть исходную стоимость перемещения до позиции, где будет посещён ресторан с наибольшим индексом. Пусть эта будет ресторан k, тогда к ответу требуется прибавить 2k, что можно учесть в момент перехода из состояния d(i, 0) при вычислении значений динамического программирования.

Поисковик

Для начала заметим, что в конце, после приписывания всех букв, Алиса получит в точности строку s.

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

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

Построим по строке суффиксное дерево, то есть бор, в который добавили все суффиксы строки s.

Будем делать динамику от вершины — dp[v] =  максимальной сумме, которую можно получить, если начать со строки, соответствующей пути от корня до v и выкидывать буквы с краёв, считая сумму вхождений по всей большой строке s.

В этой динамике всего два перехода — можно подняться в предка (что соответствует выкидыванию буквы справа), или перейти по суффиксной ссылке (что соответствует выкидыванию буквы слева). Считать динамику можно лениво, а количество вхождений~--- это количество терминальных вершин в поддереве (что можно предподсчитать заранее для всех вершин).

Правда, чтобы в динамике было меньше n² состояний, придётся перейти к сжатому суфдереву.

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

Единственное что мы не учли, так это то, что возможно в оптимальном ответе переходы наверх по ребру и по суффиксной ссылке "перемешаны", и из-за сжатия суфдерева мы таких переходов не увидим. На самом деле это ничего не портит. Действительно, если мы поднимались по длинном ребру, сделали переход по суфссылке и доподнимались по ребру, то можно было сразу пойти по суфссылке, а уж затем подниматься по ребру — количество вхождений от такой перестановки может только увеличится.

Асимптотика решения — , задачу можно также решить с помощью суффиксного автомата и динамики на нём, в таком случае переходами динамики тоже являются суффиксные ссылки и обратные рёбра.

Упражнение: решите задачу, если в качестве стартовой строки даётся не пустая строка, а некоторая подстрока исходной строки, заданная как границы вхождения (l_i и r_i). При этом требуется решить задачу для 100 000 различных запросов.

Угадай меня, если сможешь

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

Посмотрим на тройку элементов i, j и k, такую что p_i + 1 = p_j = p_k - 1. В случае, если мы перечислим все элементы в таком порядке, что j будет идти раньше i и раньше k, то в момент когда p_j увеличится на один, количество различных элементов уменьшится и мы сможем с уверенностью сказать, то на позиции j не находится максимум.

Выберем случайную перестановку и назовём элементы в соответствующем ей порядке. В тройке i, j, k, описанной выше, вероятность того, что j будет назван раньше i и k составляет . Таким образом, если проделать эту операцию 50 раз, используя каждый раз новую случайную перестановку, то вероятность, что элемент j не являющийся максимумом всё ещё не будет помечен составляет лишь . Поскольку события выполнения для каждой тройки i, j, k нельзя назвать независимыми, то оценим вероятность ошибки хотя бы на одном элементе как 2·10^- 9·n ≤ 2·10^- 6 в указанных ограничениях.