Editorial of Educational Codeforces Round 3

Revision en7, by Edvard, 2015-12-20 03:58:40

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 - Флеш-карты

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 - Книга - лучший подарок

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).

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

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).

It's very strange but I can't find any articles with Tarjan criterion on English (although there are articles on Russian), so here it is:

Some spanning tree is minimal if and only if the weight of any other edge (x, y) (not from spanning tree) is not less than the weight of the heaviest edge on the path from x to y in spanning tree.

Let's maintain the set of not eaten mosquitoes (for example with set in C++ or with TreeSet in Java) and process mosquitoes in order of their landing. Also we will maintain the set of segments (ai, bi), where ai is the position of the i-th frog and bi = ai + li, where li is the current length of the tongue of the i-th frog. Let the current mosquito landed in the position x. Let's choose segment (ai, bi) with minimal ai such that bi ≥ x. If the value ai ≤ x we found the frog that will eat mosquito. Otherwise the current mosquito will not be eaten and we should add it to our set. If the i-th frog will eat mosquito then it's tongue length will be increased by the size of mosquito and we should update segment (ai, bi). After that we should choose the nearest mosquito to the right the from frog and if it's possible eat that mosquito by the i-th frog (this can be done with lower_bound in C++). Possibly we should eat several mosquitoes, so we should repeat this process several times.

Segments (ai, bi) we can store in segment tree by position ai and value bi. Now to find segment we need we can do binary search by the value of ai and check the maximum bi value on the prefix to be at least x. This will work in O(nlog2n) time. We can improve this solution. Let's go down in segment tree in the following manner: if the maximum value bi in the left subtree of segment tree is at least x then we will go to the left, otherwise we will go to the right.

Complexity: O((n + m)log(n + m)).

#### History

Revisions

Rev. Lang. By When Δ Comment
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$ &mdash; ' -> 'Пусть $lf=0$ &mdash; '
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 Первая редакция (сохранено в черновиках)