Разбор задач Codeforces Round #327

Revision ru3, by GlebsHP, 2015-10-25 17:36:26

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

Div. 2A (Поединок волшебников)

Автор идеи: Роман Гусарев, разработка: timgaripov.

Найдем координату первого столкновения импульсов. Они сближаются со скоростью p + q, а значит первое столкновение произойдёт через секунд. Следовательно координата первого столкновения может быть вычислена как .

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

Div. 2B (Ребрендинг)

Автор идеи: glebushka98, разработка: thefacetakt.

Тривиальное решение: будем эмулировать работу дизайнеров, а именно каждый раз ходить и честно перекрашвать все xi в yi и наоборот. Работает за , получает TL.

Попробуем улучшить этот результат.

Заметим, что одинаковые буквы переходят в одинаковые. Это означает, что позиция буквы никак не влияет на результат, и достаточно помнить для каждого возможного значения символа, во что он перейдёт. Пусть result(i, c)~--- символ, который будет стоять вместо всех вхождений c после обработки i дизайнеров. Тогда: \begin{itemize} \item result(0, c) = c \item Если result(i - 1, c) = xi, то result(i, c) = yi \item Аналогично, если result(i - 1, c) = yi, то result(i, c) = xi \end{itemize}

Данное решение работает уже за O(Σ·m + n) и проходит все тесты.

Упражнение: доведите решение данной задачи до сложности O(Σ + n + m).

Div. 2C\Div. 1A (Медианное сглаживание)

Автор идеи и разработчик: Sender.

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

Исследуем влияние статичных точек на соседние элементы. Пусть ai - 1 = ai, то есть элемемнты i - 1 и i являются статичными точками. Пусть также ai + 1 статичной точкой пока не является, следовательно ai + 1 ≠ ai и ai + 1 ≠ ai + 2. Из предыдущего предложения и того, что возможны только 0 и 1 делаем вывод, что ai = ai + 2 и после одного применения алгоритма медианного сглаживания будет выполнено ai = ai + 1. То есть любая статичная точка за один шаг превращает все сосдение элементы в статичные точки. Таким образом, любая последовательность в итоге стабилизируется.

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

Итоговое решение: выделим все статичные точки в изначальной последовательности и найдём max(min(|i - sj|)), где sj — множество индексов позиций статичных точек. Сложност решения O(n).

Упражнение: взломайте решение честно моделирующее применение алгоритма медианного сглаживания до стабилизации процесса.

Div. 2D\Div. 1B (Чип и Дейл спешат на помощь) ------------------ Автор идеи и разработчик: StopKran.

Одним из ключевых моментов в решении задачи является понимание монотонности функции ответа по времени. Если дирижабль может достичь цели за секунд, то он сможет достичь её и за секунд, для любого x ≥ 0. Это очевидно вытекает из условия, что максимально возможная собственная скорость дирижабля строго превосходит

Заметим, что если собственная скорость дирижабля определяется

Div. 2E\Div. 1C (Три государства)

Автор идеи и разработчик: haku.

Div. 1D, (Сверхсекретное задание)

Автор идеи и разработчик: glebushka98.

Div. 1E (День рождения)

Автор идеи: meshanya, разработчик: romanandreev.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru9 Russian GlebsHP 2015-10-26 23:19:40 0 (опубликовано)
en2 English GlebsHP 2015-10-26 23:19:15 3120
en1 English GlebsHP 2015-10-26 22:23:36 11699 Initial revision for English translation (saved to drafts)
ru8 Russian GlebsHP 2015-10-26 03:57:40 625 Мелкая правка: '\n\nDiv. 2C\Div. 1A (' - (опубликовано)
ru7 Russian GlebsHP 2015-10-26 03:40:37 196 Мелкая правка: '-------------------------------------' -> '----------'
ru6 Russian GlebsHP 2015-10-26 02:35:21 15 Мелкая правка: 'а, а $\eps$ — ' -
ru5 Russian GlebsHP 2015-10-26 02:27:39 714 Мелкая правка: 'ть: $O(log(\frac{C}{\eps}))$, где $C' -> 'ть: $O(log \frac{C}{\eps})$, где $C'
ru4 Russian GlebsHP 2015-10-26 01:53:59 7863
ru3 Russian GlebsHP 2015-10-25 17:36:26 2 Мелкая правка: 'любого $x /ge 0$. Это' -> 'любого $x \ge 0$. Это'
ru2 Russian GlebsHP 2015-10-25 17:14:32 404
ru1 Russian GlebsHP 2015-10-25 16:57:48 4418 Первая редакция (сохранено в черновиках)