Разбор Codeforces Round #337 (Div. 2)

Revision ru5, by fcspartakm, 2015-12-27 16:04:36

610A — Паша и палка

Для начала отсечем случай, когда n нечетно. Так как периметр прямоугольника всегда четный, то ответ в таком случае 0.

Если n четно, то количество прямоугольников, которые можно составить, равно n  /  4. Если n кратно 4, то мы посчитаем и квадрат, который составлять нельзя, поэтому в таком случае из ответа нужно вычесть единицу.

Асимптотика решения — O(1).

610B — Вика и квадраты

Для начала найдем минимум в заданном массиве, обозначим его переменной minimum. Понятно, что всегда возможно покрасить n * minimum клеток. Тогда понятно, что нужно найти такой минимум в массиве, перед которым слева стоит как можно больше чисел, больших чем минимум. Другими словами, нужно найти два минимума, расстояние между которыми наибольшее, с учетом цикличности. Если же минимум в массиве один, то понятно, что начинать красить нужно с цвета, который находится сразу после него (опять же с учетом цикличности). Это можно сделать за один проход по массиву, поддерживая в отдельной переменной позицию ближайшего слева минимума. Если текущее число равно минимуму, тогда нужно обновить эту переменную и ответ.

Асимптотика решения — O(n), где n — количество различных цветов.

610С — Гармонический анализ

Давайте строить ответ рекурсивно. При k = 0 в качестве ответа можно взять либо  - 1 или  + 1. Пусть теперь мы строим ответ для некоторого k > 0. Сначала построим ответ для k - 1 теперь как ответ для k возьмем четыре копии ответа для k - 1, инвертировав все значения в последней копии. Получается на самом деле некоторый фрактал с базой размера 2 × 2: 00, 01. Корректность доказать достаточно просто, если оба вектора из верхней (нижней) половины их левые половины дают скалярное произведение равное 0 и правые тоже дают 0. Если же один из векторов из верхней половины, а другой из нижней, то значение в левой половине будет противоположно значению в правой, поэтому сумма будет равна 0.

Можно заметить, что на самом деле ответом также является матрица в которой клетка i, j равна \texttt{+}, если количество битов в числе i|j четно.

Асимптотическая сложность: O((2k)2).

610D — Вика и отрезки

Давайте сначала объединим все отрезки, находящиеся в одной горизонтали или вертикали. Теперь ответ на задачу есть сумма длин всех отрезков минус количество пересечений. Посчитаем количество пересечений. Для этого будем идти горизонтальной сканирующей прямой снизу вверх (это можно делать событиями открылся вертикальный отрезок, закрылся вертикальный и обработать горизонтальный) и в некоторой структуре данных поддерживать множество x-координат открытых отрезков. В качестве структуры данных можно использовать дерево Фенвика с предварительным сжатием координат. Теперь для текущего горизонтального отрезка нужно просто взять количество открытых вертикальных отрезков со значениями x в отрезке x1, x2, где x — вертикаль на которой находится вертикальный отрезок, а x1, x2x-координаты концов текущего горизонтального отрезка.

Асимптотическая сложность: O(nlogn).

610E — Перестановки алфавита

Рассмотрим медленное решение этой задачи: на первый запрос будем просто переприсваивать символы, на запросы второго типа будем идти по строке s и поддерживать указатель на текущую позицию в перестановке алфавита. Будем двигать указатель по циклу пока не найдем совпадение с текущим символом в s. После этого подвинем указатель еще раз. Тогда ответом на задачу будет количество циклических переходов (от последнего к первому символу) в перестановке алфавита. На самом деле это значение равно единице плюс количество пар соседних символов таких, что второй символ находится не правее первого. Таким образом, ответ на задачу зависит лишь от значений cntij —- количество пар соседних символов таких, что первый символ ест i, а второй j. Теперь, чтобы ускорить решение будем поддерживать дерево отрезков в вершине, которого находится матрица cnt для текущего подотрезка и символы с левого и правого концов текущего отрезка. Чтобы слить двух сыновей в дереве отрезков нужно просто попарно сложить значения матриц в левом и правом сыне, и обновить значением правого символа левого отрезка с левым символов правого отрезка.

Асимптотическая сложность: O(nk2 + mk2logn).

Tags editorial, 337, div2, round

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru7 Russian fcspartakm 2015-12-28 13:29:08 2 Мелкая правка: 'k^2 + m k^2 logn)$.' -> 'k^2 + m k^{2} logn)$.'
en14 English fcspartakm 2015-12-28 13:28:56 2 Tiny change: 'k^2 + m k^2 logn)$.' -> 'k^2 + m k^{2} logn)$.'
en13 English fcspartakm 2015-12-27 16:24:40 1123
en12 English fcspartakm 2015-12-27 16:22:15 0 (published)
ru6 Russian fcspartakm 2015-12-27 16:15:37 10 Мелкая правка: 'оличество битов в ч' -> 'оличество единичных битов в ч'
en11 English fcspartakm 2015-12-27 16:15:13 872
en10 English fcspartakm 2015-12-27 16:14:22 2 Tiny change: 'nSoon...\n[610D &m' -> 'nSoon...\n\n[610D &m'
en9 English fcspartakm 2015-12-27 16:13:58 925
ru5 Russian fcspartakm 2015-12-27 16:04:36 3429
en8 English fcspartakm 2015-12-27 15:55:53 1 Tiny change: 'nimum$ squres. So we' -> 'nimum$ squares. So we'
en7 English fcspartakm 2015-12-27 15:55:19 2 Tiny change: 's to $n / 2$. If $n$ ' -> 's to $n / 4$. If $n$ '
en6 English fcspartakm 2015-12-27 15:55:02 1379
en5 English fcspartakm 2015-12-27 15:46:30 1
en4 English fcspartakm 2015-12-27 15:46:19 541
ru4 Russian fcspartakm 2015-12-27 15:46:04 541
en3 English fcspartakm 2015-12-27 15:44:34 568 Reverted to en1
en2 English fcspartakm 2015-12-27 15:40:22 568
ru3 Russian fcspartakm 2015-12-27 15:35:50 644
en1 English fcspartakm 2015-12-27 15:31:45 1661 Initial revision for English translation
ru2 Russian fcspartakm 2015-12-27 15:28:28 6
ru1 Russian fcspartakm 2015-12-27 15:27:04 1649 Первая редакция (сохранено в черновиках)