Codeforces Round #337 ( Div.2) Editorial

Revision en2, by fcspartakm, 2015-12-27 15:40:22

610A — Pasha and Stick

At first if n is odd the answer is 0, because the perimeter of any rectangle is even number always.

If n is even than the number of the rectangles which can be constructed equals to n / 4. If n is divisible by 4 than we will count the square which is deprecated, so in this case we need to subtract 1 from the answer.

Asymptotic behavior — O(1).

610B — Vika and Squares

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

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

610С — Harmony Analysis

610D — Vika and Segments

610E — Alphabet Permutations

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 Первая редакция (сохранено в черновиках)