Codeforces Round #337 (Div.2) Editorial

Правка en10, от fcspartakm, 2015-12-27 16:14:22

610A — Pasha and Stick

If the given n is odd the answer is 0, because the perimeter of any rectangle is always even number.

If n is even the number of rectangles which can be construct equals to n / 4. If n is divisible by 4 we will count the square, which are deprecated, because we need to subtract 1 from the answer.

Asymptotic behavior — O(1).

610B — Vika and Squares

At first let's find the minimum in the given array and store it in the variable minimum. It is easy to understand, that we always can paint n * minimum squares. So we need to find such a minimum in the array before which staying the most number of elements, which more than the minimum. In the other words we need to find 2 minimums in the array which are farthest from each other (do not forget about cyclical of the array). If there is only one minumum we need to start paint from the color which stay in the array exactly after the minimum (do not forget about cyclical of the array too). It can be done with help of iterations from the left to the right. We need to store the position of the nearest minimum in the variable and update her and the answer when we meet the element which equals to minimum.

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

610С — Harmony Analysis

Soon...

610D — Vika and Segments

At first let's unite all segments which are in same verticals or horizontals. Now the answer to the problem is the sum of lengths of all segments subtract the number of intersections. Let's count the number of intersections. For this let's use the horizontal scan-line from the top to the bottom (is can be done with help of events — vertical segment is open, vertical segment is close and hadle horizontal segment) and in some data structure store the set of x-coordinates of the open segments. For example we can use Fenwick tree with precompression of the coordinates. Now for current horizontal segment we need to take the number of the opened vertical segmetns with value x in the range x1, x2, where x — vertical where the vertical segment are locating and x1, x2 — the x-coordinates of the current horizontal segment.

Asymptotic behavior: O(nlogn).

610E — Alphabet Permutations

Soon...

История

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