Codeforces Round #322 (Div.2) Editorial

Правка en17, от fcspartakm, 2015-09-28 10:40:17

581A — Vasya the Hipster

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 — Luxurious Houses

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 — Developing Skills

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. Let's cur = 10 - (aimod10). If cur ≤ k assign ai = ai + cur and from k subtract cur else if cur > k break from cycle.

The next step is to iterate on array in the same way.

Now we need only to calculate answer ans — we iterate on array for i from 1 to n and assign ans = ans + (ai / 10).

Asymptotic behavior of this solution — O(n * log(n)) where n is the number of hero skills.

581D — Three Logos

This problem can be solved in many ways, let's consider one of them.

The first step is to calculate sum of squares s of given rectangles. Then the side of a answer square is sqrt(s). If sqrt(s) is not integer print -1. Else we need to make the following.

We brute the order in which we will add given rectangles in the answer square (we can do it with help of next_permutation()) and for every order we brute will we rotate current rectangle on 90 degrees or not (we can do it with help of bit masks). In the beginning on every iteration the answer square c in which we add the rectangles is empty.

For every rectangle, which we add to the answer square we make the following — we need to find the uppermost and leftmost empty cell free in answer square c (recall that we also brute will we rotate the current rectangle on 90 degrees or not). Now we try to impose current rectangle in the answer square c and the top left corner must coinside with the cell free. If current rectangle fully placed in the answer square c and does not intersect with the some rectangle which has already been added, we need to fill by the required letter appropriate cells in the answer square c.

If no one of the conditions did not disrupted after we added all three rectangles and all answer square c is fully filled by letters we found answer and we neeed only to print the answer square c.

Else if we did not find answer after all iterations on the rectangles — print -1.

For random number of the rectangles k asymptotic behavior — O(k! * 2k * s) where s — the sum of squares of the given rectangles.

Also this problem with 3 rectangles can be solved with the analysis of the cases with asymptotic O(s) where s — the sum of squares of given rectangles.

581E — Kojiro and Furrari

Let's f — the position of start, and e — the position of finish. For convenience of implementation we add the gas-station in point e with type equals to 3.

Первое замечание: никогда нет смысла идти налево из стартовой точки ведь мы в ней уже стоит с полным баком лучшего бензина. Замечание верно и для любой заправки, в которой мы можем оказаться (если в оптимальном ответе мы должны пойти налево до некоторой заправки pv, то почему бы не выкинуть весь путь из pv в текущую заправку v и обратно и от этого ответ станет только лучше). Теперь поймем как нам следует действовать если мы находимся в некоторой заправке v.

Первый случай: на расстоянии не более чем s находится заправка в качеством бензина не хуже, чем в нашей (можно считать, что в момент старта мы находимся на заправке типа 3, но добавлять такую заправку нельзя). Зафиксируем ближайшую из них nv (ближайшую справа, так как мы уже поняли, что идти влево нет смысла). В этом случае дозаправимся так, чтобы возможно было доехать до nv. И поедем в nv.

Второй случай: из нас достижимы только заправки с худшим качеством. Заметим, что это возможно лишь в случае, если мы находимся в заправке типа 2 или 3. В случае заправки второго типа у нас нет никакого выбора кроме как заправиться на полную и поехать в самую последнюю достижимую вершину (то есть вершину на расстоянии не более чем s). Если же мы находимся в вершине типа 3, то нужно идти по возможности в самую дальнюю вершину типа 2, если же такой нет то идти в самую дальнюю типа 1. Эти рассуждения верны в силу того, что нам в первую очередь необходимо минимзировать бензин типа 1, а при равенстве типа — 2. Как можно дальше нужно идти потому, что бензин в нашей вершине строго лучше достижимых, а тип 2 нужно выбирать, поскольку если мы можем доехать до типа 1 и он находится правее заправки типа 2, то мы можем это сделать, проехав через заправку типа 2, возможно улучшив ответ.

Это основные рассуждения необходимые для решения задачи. Далее будем считать диманику на всех суффиксах i заправок — ответ на задачу если мы стартуем из заправки i с пустым баком. Переходы мы должны сделать, рассматривая описанные выше случаи. Для пересчета динамики в v нам нужно взять значение динамики в nv и сделать пересчет в зависимости от случая. Если случай 1, то нужно просто к соответствующему значению прибавить расстояние d от v к nv. Если это случай 2 и мы в заправке типа 2 нужно ко второму значению ответа прибавить s, а из первого вычесть sd. Если это случай 2 и мы в заправке типа 3, то нужно из значения, определяемого типом заправки nv вычесть sd.

Теперь, чтобы ответить на конкретный запрос стартовой позиции нужно найти первую завправку правее стартовой позиции, сделать один переход и взять уже посчитанное значение динамики (конечно, пересчитав это значение в соответствии с вышеописанным).

Сложность решения по времени: O(n logn) или O(n) в зависимости от того как искать позицию в списке заправок (первое в случае бинпоиска, второе в случае двух указателей). Сложность решения по памяти: O(n).

581F — Zublicanes and Mumocrates

Let the number of leavs in tree (vertices with degree 1) is equal to c. It said in statement that c is even. If in given graph only 2 vertices the answer is equal to 1. Else we have vertex in graph which do not a leaf — we hang the three on this vertex.

Now we need to count 2 dynamics. The first z1[v][cnt][col] — the least amount of colored edges in the subtree rooted at the vertex v, if vertex v already painted in color col (col equals to 0 or to 1), and among the top of the leaves of the subtree v must be exactly cnt vertices with color 0. If we are in the leaf, it is easy to count this value. If we are not in the leaf — we count value with help of dynamic z1[v][cnt][col]:  = z2[s][cnt][col], where s — the first child int the adjacency list of vertex v.

We need the second dynamic z2[s][cnt][col] to spread cnt leaves with color 0 among subtrees of childs of vertex v. To calc z2[s][cnt][col] we brute the color of child sncol and the number of childs i with color 0, which will be locate in subtree of vertex s and calc the value in the following way — z2[s][cnt][col] = min(z2[s][cnt][col], z2[ns][cnta][col] + z1[s][a][ncol] + (ncol! = col)), where ns — the next child of vertex v after the child s. Note, that it is senselessly to take a more than the number of leaves in the subtree s and to take more than the number of vertices in subtree — sizes (because in that case it will not be enough leaves for painting).

The upper bound of asymptotic for such dynamics O(n3). We show that in fact it works with asymptotic O(n2). Let's count the number of updates: . Note, that every pair of vertices (x, y) appears in the last sum (x, y) exactly once when v = lca(x, y). So we have no more than O(n2) updates.

Asymptotic behavior of this solution: O(n2).

Теги editorial, round, 322, div2

История

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