Codeforces Round #322 (Div.2) Editorial

Revision en3, by fcspartakm, 2015-09-25 13:17:49

581A — ???

The first number in answer (number of days which Vasya can dress fashionably) is min(a, b) because every from this day he will dress one red sock and one blue sock.

After this Vasya will have either only red socks or only blue socks or socks do not remain at all. Because of that the second number in answer is max((a - min(a, b)) / 2, (b - min(a, b)) / 2).

Asymptotic behavior of this solution — O(1).

581B — ???

This problem can be solved in the following way. Let's iterate on given array from the right to the left and will store in variable maxH the maximal height if house which we have already considered.Then the answer to house number i is number max(0, maxH + 1 - hi), where hi number of floors in house number i.

Asymptotic behavior of this solution — O(n), where n — number of houses.

581C — ???

Данная задача решается несколькими способами, рассмотрим один из них.

Для начала подсчитаем суммарную площадь s данных нам прямоугольников. Тогда сторона ответного квадрата это sqrt(s). Если sqrt(s) не целое число, выводим -1. Иначе сделаем следующее.

Переберем порядок, в котором будем добавлять заданные прямоугольники в квадрат (это можно сделать с помощью next_permutation()), а также для каждого порядка переберем будем ли мы переворачивать текущий прямоугольник на 90 градусов или нет (это можно сделать с помощью двоичных масок). Изначально на каждой итерации квадрат c, в который мы добавляем прямоугольники ничем не заполнен (пустой).

Для каждого из добавляемых прямоугольников сделаем следующее — найдем самую верхнюю левую свободную клетку free в квадрате c (напомним, что мы также перебираем, поворачиваем ли мы прямоугольник на 90 градусов или нет). Попытаемся наложить текущий прямоугольник в квадрат c, причем его левый верхний угол должен совпадать с клеткой free. Если текущий прямоугольник полностью помещается в квадрат c и не накладывается на уже занятую каким-то другим прямоугольником клетку, заполним соответствующие клетки в квадрате c нужной буквой.

Если после добавления всех трех прямоугольников не нарушилось ни одно из условий и весь квадрат c оказался заполненным мы нашли ответ — выводим квадрат c.

Если ответ не нашелся ни для одной перестановки прямоугольников — выводим -1.

Для произвольного количества прямоугольников k асимптотика решения — O(k! * 2k * s), где s — суммарная площадь заданных прямоугольников.

Также данная задача для 3 прямоугольников имеет решение с разбором случаев с асимптотикой O(s), где s — суммарная площадь заданных прямоугольников.

581D — ???

This problem can be solved in many ways. Let's consider the most intuitive way that fits in the given time.

In the beginning we need to sort given array in the following way — from two numbers to the left should be the number to which must be added fewer units of improvements to make it a multiple of 10. For example, if given array is {45, 30, 87, 26} after the sort the array must be equal to {87, 26, 45, 30}.

Now we iterate on the sorted array for i from 1 to n. Теперь проитерируемся по отсортированному массиву слева направо по i от 1 до n. Пусть cur = 10 - (aimod10). Если cur ≤ k, присвоим ai = ai + cur, а из k вычтем cur, иначе, если cur > k выйдем из цикла.

Следующим шагом проитерируемся по массиву аналогичным образом.

Осталось посчитать ответ ans — проитерируемся по массиву по i от 1 до n и присвоим ans = ans + (ai / 10).

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

581E — ???

581F — ???

Tags editorial, round, 322, div2

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru20 Russian fcspartakm 2015-09-28 14:02:11 0 (опубликовано)
en24 English fcspartakm 2015-09-28 12:09:42 67
ru19 Russian fcspartakm 2015-09-28 12:09:09 52
en23 English fcspartakm 2015-09-28 11:44:25 1251
en22 English fcspartakm 2015-09-28 11:26:03 19 Tiny change: ' $nv$.\n\nВторой с' -> ' $nv$.\n\nThe second case: \nВторой с'
en21 English fcspartakm 2015-09-28 11:24:50 1646
en20 English fcspartakm 2015-09-28 11:07:13 424
en19 English fcspartakm 2015-09-28 11:02:23 462
en18 English fcspartakm 2015-09-28 10:49:04 718
en17 English fcspartakm 2015-09-28 10:40:17 223
en16 English fcspartakm 2015-09-28 10:33:11 3122
en15 English fcspartakm 2015-09-28 10:31:30 664
en14 English fcspartakm 2015-09-28 10:18:15 563
en13 English fcspartakm 2015-09-28 10:07:03 123
en12 English fcspartakm 2015-09-28 09:57:25 477
en11 English fcspartakm 2015-09-28 09:50:45 2047
ru18 Russian fcspartakm 2015-09-28 09:44:09 5082
ru17 Russian fcspartakm 2015-09-28 09:28:09 53
en10 English fcspartakm 2015-09-28 09:26:00 2114
ru16 Russian fcspartakm 2015-09-28 09:24:06 2118
ru15 Russian fcspartakm 2015-09-25 16:10:45 56
en9 English fcspartakm 2015-09-25 14:10:24 1 Tiny change: 'e followin — w' -> 'e following — w'
en8 English fcspartakm 2015-09-25 14:08:26 0 Tiny change: ' degrees ot not (we c' -> ' degrees or not (we c'
en7 English fcspartakm 2015-09-25 14:08:26 2 Tiny change: ' degrees ot not (we c' -> ' degrees or not (we c'
en6 English fcspartakm 2015-09-25 14:07:35 2756
en5 English fcspartakm 2015-09-25 13:51:07 2 Tiny change: ' to iterato on array ' -> ' to iterate on array '
en4 English fcspartakm 2015-09-25 13:50:34 532
en3 English fcspartakm 2015-09-25 13:17:49 703
en2 English fcspartakm 2015-09-25 13:08:32 530
en1 English fcspartakm 2015-09-25 13:04:29 4088 Initial revision for English translation
ru14 Russian fcspartakm 2015-09-25 12:36:42 8
ru13 Russian fcspartakm 2015-09-25 12:36:00 941
ru12 Russian fcspartakm 2015-09-25 11:51:25 4
ru11 Russian fcspartakm 2015-09-25 11:51:12 1 Мелкая правка: 'вадрате $c (напомним' -> 'вадрате $c$ (напомним'
ru10 Russian fcspartakm 2015-09-25 11:50:57 47
ru9 Russian fcspartakm 2015-09-25 11:49:20 1 Мелкая правка: 'mutation()$, а такж' -> 'mutation())$, а такж'
ru8 Russian fcspartakm 2015-09-25 11:48:50 2 Мелкая правка: 'ощью $next/_permutati' -> 'ощью $next\_permutati'
ru7 Russian fcspartakm 2015-09-25 11:48:37 1
ru6 Russian fcspartakm 2015-09-25 11:48:16 1510
ru5 Russian fcspartakm 2015-09-24 17:35:56 319
ru4 Russian fcspartakm 2015-09-24 17:26:14 2 Мелкая правка: '------\n\n[581D ' -> '------\n\n\n[581D '
ru3 Russian fcspartakm 2015-09-24 17:25:35 337
ru2 Russian fcspartakm 2015-09-24 17:23:17 53
ru1 Russian fcspartakm 2015-09-24 17:22:02 996 Первая редакция (сохранено в черновиках)