Editorial of Educational Codeforces Round 2

Revision en7, by Edvard, 2015-12-20 01:06:01

600A - Extract Numbers

This is a technical problem. You should do exactly what is written in problem statement.

600B - Queries about less or equal elements

Let's sort all numbers in a. Now let's iterate over elements of b and for element bj find the index of lowest number that is greater than bj. We can do that using binary search. That index will be the answer for value bj.

Complexity: O(nlogn).

600C - Make Palindrome

Let's denote cntc — the number of occurences of symbol c. Let's consider odd values cntc. Palindrome can not contain more than one symbol c with odd cntc. Let's denote symbols with odd cntc as a1, a2...ak (in alphabetical order). Let's replace any one of symbols ak with symbol a1, ak - 1 with a2 and so on until the middle of a. Now we have no more than one odd symbol. If we have some let's place it in the middle of the answer. First half of answer will contain occurences of symbol c in alphabetical order. The second half will contain the same symbols in reverse order. For example for string s = aabcd at first we will replace d by

Unable to parse markup [type=CF_TEX]

in the middle and after permuting the symbols we got abcba. Easy to see that it's the optimal solution.

Compexity: O(n).

600D - Area of Two Circles' Intersection

If the circles don't intersect than the answer is 0. We can check that case with only integer calculations (simply by comparing the square of distance between centers with square of the sum of radiuses). If one of the circles is fully in other then the answer is the square of the smaller one. We can check this case also with only integer calculations (simply by comparing the square of distance between centers with square of the difference of radiuses).

So now let's consider the general case. The answer will be equal to the sum of two circular segments. Let's consider the triangle with apexes in centers if circles and in some intersecting point of the circles. In that triangle we know all three sides so we can compute the angle of the circular segment. So we can compute the square of circular sector. And the only thing that we should do now is to subtract the square of triangle with apexes in the center of circle and in the intersecting points of circles. We can do that by computing the half of absolute value of cross product. So we have the following formulas:

,

where d is the distance between centers of the circles. And also we should do the same thing with second circle by replacing of indices 1 ≤ ftrightarrow2.

Complexity: O(1).

600E - Lomsat gelral

The name of this problem is anagram for ''Small to large''. There is a reason for that :-) The author solution for this problem uses the classic technique for computing sets in tree. The simple solution is the following: let's find for each vertex v the ''map<int, int>'' — the number of occurences for each colour, ''set<pair<int, int>>'' — pairs the number of occurences and the colour, and the number sum — the sum of most frequent colours in subtree of v. To find that firstly we should find the same thing for all childs of v and then merge them to one. These solution is correct but too slow (it works in O(n2logn) time). Let's improve that solution: every time when we want to merge two map-s a and b let's merge the smaller one to larger simply by iterating over all elements of the smaller one (this is the ``Small to large''). Let's consider some vertex v: every time when vertex v will be moved from one map to another the size of the new map will be at least two times larger. So each vertex can be moved not over than logn times. Each moving can be done in O(logn) time. If we accumulate that values by all vertices then we get the complexity O(nlog2n).

I saw the solutions that differs from author's but this technique can be used in a lot of other problems.

600F - Edge coloring of bipartite graph

Let's denote d is the maximum degree of vertex in graph. Let's prove that the answer is d. We will build the constructive algorithm for that (it will be the solution to problem). Let's colour the edges one by one in some order. Let (x, y) be the current edge. If there exist colour c that is free in vertex x and in vertex y then we can simply colour (x, y) with c. If there is no such colour then there are a couple of colours c1, c2 so that c1 is in x and not in y and c2 is in y but not in x. Let's make vertex y free from colour c2. Denote z the other end of edge from y with colour c2. If z is free from colour c1 then we can colour x, y with c2 and recolour y, z with c1. So me make alternation. If z is not free from colour c1 let's denote w the other end of the edge from z with colour c1. If w is free from colour c2 then again we can do alternation. And so on. We will find an alternating chain because the graph is bipartite. To find the chain we can use depth first search. Each chain contains no more than O(n) vertices. So we have:

Сложность решения: O(nm).

Tags education round 2, editorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English Edvard 2015-12-20 01:06:01 7190 Reverted to en5
en6 English Edvard 2015-12-20 01:04:40 7190 Tiny change: 'oks of $i$th genre. ' -
ru12 Russian Edvard 2015-11-28 02:56:22 58
en5 English Edvard 2015-11-28 02:55:31 1179
en4 English Edvard 2015-11-28 01:56:48 12 Tiny change: 'l to large``. There is' -> 'l to large''. There is'
en3 English Edvard 2015-11-28 01:56:19 14 Tiny change: 'l to large``. There is' -> 'l to large''. There is'
en2 English Edvard 2015-11-28 01:33:31 1343
en1 English Edvard 2015-11-28 00:38:09 2786 Initial revision for English translation
ru11 Russian Edvard 2015-11-27 23:53:58 9
ru10 Russian Edvard 2015-11-27 23:50:23 9 Мелкая правка: 'чение $d$ —- наибольш' -> 'чение $d$ --- наибольш'
ru9 Russian Edvard 2015-11-27 23:29:29 1188
ru8 Russian Edvard 2015-11-27 20:04:30 63
ru7 Russian Edvard 2015-11-27 20:03:57 104 (опубликовано)
ru6 Russian Edvard 2015-11-27 19:54:54 51
ru5 Russian Edvard 2015-11-27 19:53:17 24
ru4 Russian Edvard 2015-11-27 19:52:37 197 Мелкая правка: ' to large`). Давайт' -
ru3 Russian Edvard 2015-11-27 19:48:36 1406
ru2 Russian Edvard 2015-11-27 19:25:41 1280
ru1 Russian Edvard 2015-11-27 19:05:18 1827 Первая редакция (сохранено в черновиках)