Editorial of Educational Codeforces Round 3

Правка en3, от Edvard, 2015-12-20 03:22:44

This round was unusual: some of problems was prepared by students and employees of Saratov State U for some of past olympiads and one of problems was prepared by dalex for Codeforces regular round but was not used there.

609A - USB Flash Drives

Let's sort the array in nonincreasing order. Now the answer is some of the first flash-drives. Let's iterate over array from left to right until the moment when we will have the sum at least m. The number of elements we took is the answer to the problem.

Complexity: O(nlogn).

609B - The Best Gift

Let's denote cnti — the number of books of i th genre. The answer to problem is equals to . In first sum we are calculating the number of good pairs, while in second we are subtracting the number of bad pairs from the number of all pairs.

Complexity: O(n + m2) or O(n + m).

609C - Load Balancing

Denote s — the sum of elements in array. If s is divisible by n then the balanced array consists of n elements . In this case the difference between maximal and minimal elements is 0. Easy to see that in any other case the answer is greater than 0. On the other hand the array consists of numbers and numbers is balanced with the difference equals to 1. Let's denote this balanced array b. To get array b let's sort array a in nonincreasing order and match element ai to element bi. Now we should increase some elements and decrease others. In one operation we can increase some element and decrease another, so the answer is .

Complexity: O(nlogn).

609D - Gadgets for dollars and pounds

If Nura can buy k gadgets in x days then she can do that in x + 1 days. So the function of answer is monotonic. So we can find the minimal day with binary search. Denote lf = 0 — the left bound of binary search and rg = n + 1 — the right one. We will maintain the invariant that in left bound we can't buy k gadgets and in right bound we can do that. Denote function f(d) equals to 1 if we can buy k gadgets in d days and 0 otherwise. As usual in binary search we will choose . If f(d) = 1 then we should move the right bound rg = d and the left bound lf = d in other case. If binary search found the value lf = n + 1 then the answer is  - 1, otherwise the answer is lf. Before binary search we can create two arrays of gadgets which are selling for dollars and pounds, and sort them. Easy to see that we should buy gadgets for dollars on day i ≤ d when dollar costs as small as possible and j ≤ d when pounds costs as small as possible. Let now we want to buy x gadgets for dollars and k - x gadgets for pounds. Of course we will buy the least cheap of them (we already sort the arrays for that). Let's iterate over x from 0 to k and maintain the sum of gadgets for dollars s1 and the sum of gadgets for pounds s2. For x = 0 we can calculate the sums in O(k). For other x's we can recalculate the sums in O(1) time from the sums for x - 1 by adding gadget for dollars and removing gadget for pounds.

Complexity: O(klogn).

609E - Minimum spanning tree for each edge

This problem was prepared by dalex.

Let's build any MST with any fast algorithm (for example with Kruskal's algorithm). For all edges in MST the answer is the weight of the MST. Let's consider any other edge (x, y). There is exactly one path between x and y in the MST. Let's remove mostly heavy edge on this path and add edge (x, y). Resulting tree is the MST contaning edge (x, y) (this can be proven by Tarjan criterion).

Let's fix some root in the MST (for example the vertex 1). To find the most heavy edge on the path from x to y we can firstly find the heaviest edge on the path from x to l = lca(x, y) and then on the path from y to l, where l is the lowest common ancestor of vertices x and y. To find l we can use binary lifting method. During calculation of l we also can maintain the weight of the heaviest edge.

Of course this problem also can be solved with difficult data structures, for example with Heavy-light decomposition method or with Linkcut trees.

Complexity: O(mlogn).

609F - Frogs and mosquitoes

TODO

Теги education round 3, editorial

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский Edvard 2015-12-20 03:58:40 33
ru9 Русский Edvard 2015-12-20 03:57:21 32
en6 Английский Edvard 2015-12-20 03:54:38 1619
en5 Английский Edvard 2015-12-20 03:41:51 2 Tiny change: 'e it is:\nSome spa' -> 'e it is:\n\nSome spa'
en4 Английский Edvard 2015-12-20 03:41:23 345
ru8 Русский Edvard 2015-12-20 03:39:45 9 Мелкая правка: 'ер метода lower_bound в C++). В' -> 'ер метода \texttt{lower_bound} в C++). В'
en3 Английский Edvard 2015-12-20 03:22:44 1225
en2 Английский Edvard 2015-12-20 01:45:23 1503
ru7 Русский Edvard 2015-12-20 01:23:37 8
ru6 Русский Edvard 2015-12-20 01:21:21 2 Мелкая правка: 'ведем функицю $f(d)$, ' -> 'ведем функцию $f(d)$, '
ru5 Русский Edvard 2015-12-20 01:19:46 2 Мелкая правка: 'Пусть $lf=1$ — ' -> 'Пусть $lf=0$ — '
en1 Английский Edvard 2015-12-20 01:07:43 1959 Initial revision for English translation
ru4 Русский Edvard 2015-12-19 22:47:25 40 Мелкая правка: ' + m))$.\n' -> ' + m))$.\n\n[Code](http://pastebin.com/MTWxiD1s)\n'
ru3 Русский Edvard 2015-12-19 22:20:38 1049 Мелкая правка: ' $O(n log^2n)$. Но эт' -
ru2 Русский Edvard 2015-12-19 20:08:22 12575 Мелкая правка: 'шения: $O(k logn)$.\n\n[pr' - (опубликовано)
ru1 Русский Edvard 2015-12-19 17:50:23 5836 Первая редакция (сохранено в черновиках)