Разбор задач. Алгоритм победы 2022.

Тренировка.

A. Разбор задачи «Олимпиада»

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

• Олимпиада С++
• Олимпиада Python
• Олимпиада Python

B. Разбор задачи «Незнайка»

Задачу на отрезке от a до b можно свести к задачам на отрезке от 1 до a и от 1 до b. Так как F(a..b) = F(1..b) - F(1..(a - 1)) Теперь нужно научиться считать количество чисел от 1 до какого-то b. Заметим, что числа, в которых нет девяток – это числа в девятеричной системе счисления. Воспользуемся теперь тем, что границы a и b не имеют девяток в своем представлении. Следовательно, все что там остается сделать – это перевести входные данные в десятичную систему счисления и вывести их разность. К сожалению, F(a..b) = F(1..b) - F(1..(a - 1)) данная формула будет не совсем правильно работать в контексте данной задачи, так как значение a - 1 может содержать девятки. Поэтому ответом на задачу будет являться F(b) - F(a) + 1, где F(n) – десятичное представление девятеричного числа n.

• Незнайка C++
• Незнайка Python

C. Разбор задачи «Очередь»

1. Наивное решение за O(n^2)

Для каждого коротышки, ищем линейно более высокого или равного ему по росту слева в массиве. Недовольство – разница их индексов или 0 если таковой не нашелся. Решение в худшем случае работает за квадрат. Например, когда коротышки отсортированы по возрастанию, нам придется пробегать по всем индексам слева, чтобы убедиться, что там все ниже. Это решение не пройдет по времени. Можно получить 22 балла на маленьких тестах. Что и сделали некоторые школьники.

2. Решение с помощью дерева отрезков за O(n*log n)

Проходим по коротышкам слева направо поддерживая структуру данных позволяющую искать максимальный индекс коротышки с ростом выше или равным текущему. Такой структурой может быть дерево отрезков по росту, где в узлах хранится максимальный индекс.
Решение пройдет по времени, но не самое эффективное. Кроме того, требует знания и реализации нетривиальной структуры данных. Что может отнять много времени на олимпиаде.

*3. Решение с помощью стека за O(n)

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

• Очередь C++
• Очередь Python

D. Разбор задачи «Кнопочка»

Желаемого результата можно достичь, если существуют два цвета таких, что количества камушков таких цветов равны по модулю 3. Заметим, что a и b дают всегда одинаковый остаток по модулю 3, a и c дают одинаковый остаток по модулю 3 и b и c дают одинаковый остаток по модулю 3. Если существует способ получить такой набор, что два из трех чисел в нем равны 0, то те числа, которые станут равны 0 должны были изначально давать одинаковый остаток по модулю 3. Теперь докажем, что если изначально есть два таких числа, то можно их превратить в 0. Пока оба числа больше 0, будем брать по камушку этих цветов и получать два камушка третьего цвета. Когда камушков какого-то из цветов не осталось, если не осталось камушков ни одного из этих цветов, то мы получили искомый набор. Иначе, если количество камушков третьего цвета равно 0, то мы также получили искомый набор. Иначе, не умаляя общности, пусть осталось 0 камушков красного цвета, хотя бы 1 камушек зеленого цвета и хотя бы 1 камушек синего цвета. При этом, количество камушков зеленого цвета делится на 3 (а значит, их хотя бы 3), то есть количество камушков красного цвета по модулю 3 равно количеству камушков зеленого цвета по модулю 3. Тогда из зеленого и синего камушков получим два красных, потом из красного и зеленого два раза получим по два синих. В итоге, мы уменьшили количество зеленых камушков на 3. Будем так повторять, пока их не останется 0.

• Кнопочка C++
• Кнопочка Python

E. Разбор задачи «Пёстренький»

Задача на реализацию. Однако, некоторые школьники могут и вывести формулу для оптимизации решения задачи.

• Пёстренький C++
• Пёстренький Python
• Пёстренький Python

F. Разбор задачи «Подарок»

Если Пёстренький может добраться до кочки с номером i, то он может добраться и до всех предыдущих кочек. Будем рассматривать кочки слева направо и поддерживать номер самой правой кочки, до которой сможет добраться Пёстренький.
Обозначим за X максимальный номер кочки, до которой сможет добраться Пёстренький. Изначально скажем, что X = 1, так как в начале Пёстренький находится на кочке с номером 1. Пусть мы рассмотрели первые i – 1 кочек, и на данный момент известно, что Пёстренький сможет добраться до кочки с номером X. Теперь рассмотрим кочку с номером i и поймём, насколько далеко Пестренький сможет прыгнуть используя её.
Если X < i, то Пёстренький никак не сможет попасть на кочку с номером i, а значит он не сможет воспользоваться данной кочкой. В этом случае ответ на задачу равен X.
Если же X ≥ i, то можно попробовать воспользоваться текущей кочкой. Известно, что с неё Пёстренький может прыгнуть не далее, чем a_i метров вправо. Так как расстояние между соседними кочками равно D, Пёстренький сможет допрыгнуть с текущей кочки на кочку с номером i + a_i / D. Если данное число больше, чем X, то обновим значение X, ведь теперь Пёстренький смог добраться до кочки с большим номером.

• Подарок C++
• Подарок C++
• Подарок Python
• Подарок Python

G. Разбор задачи «День рукавичек»

Эта задача легко решается сортировкой подсчётом для подсчёта совпадающих цветов рукавичек.

• День рукавичек C++
• День рукавичек Python
• День рукавичек Python