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

Правка ru4, от fcspartakm, 2015-12-27 15:46:04

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

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

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

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

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

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

Asymptotic behavior — O(n), where n — the nimber of different colors.

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

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

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

Теги editorial, 337, div2, round

История

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