By RussianCodeCup, history, 8 years ago, translation, In English

Hi, everyone!

Russian Code Cup 2016 is over, the problems for the Final Round were more difficult than usually, but the participants didn't give up. The champion is Gennady Korotkevich tourist, the second place winner is Vladislav Epifanov vepifanov, the third place winner is Nikolay Kalinin KAN. Congratulations to the winners, the complete results are at the RCC web site http://russiancodecup.ru

Before proceeding to the tutorial, we would like to thank Mail.Ru Group for organizing the tournament and providing the prizes, and the judges from ITMO University for problems. Chief judge Andrew Stankevich andrewzta, judges Vitaly Aksenov Aksenov239, Nikolay Budin budalnik, Dmitry Filippov DimaPhil, Borys Minaiev qwerty787788, Ilya Peresadin pva701, Grigory Shovkoplyas GShark, Artem Vasiliev VArtem, Nikolay Vedernikov Niko, Ilya Zban izban.

And now the short tutorial. To get more details, you can read the programs of the judges solutions, published at the official site http://russiancodecup.ru together with the official tests.

A. Closing ceremony

Probably the easiest way to solve the problem is greedy. Sort people from the first line by increasing of their stamina. Give them tickets in this order, each time using the place which is furthest away from the other line. After that try to assign people from the second line to the remaining seats by sorting people by stamina and seats by the distance.

The time complexity of your solution must not exceed O((nm)2), however using std::set one can get a solution with complexity of O(nmlog(nm)).

B. Cactusophobia

Let us divide the graph to biconnected blocks. Each block is either a bridge, or a cycle. Our goal is to remove one edge from each cycle, so that the number of remaining colors were maximum possible.

Let us build a bipartite graph, one part would be blocks, another one would be colors. For each block put an edge of capacity 1 for each color of an edge in this block (make multiple edges, or bigger capacity if there are several edges of some color). Add two vertices: source and sink, add edges from source to blocks, if the block is a cycle of length l, set its capacity to l - 1, if it is a bridge, set its capacity to 1. Add edges from color vertices to the sink of capacity 1.

It is quite clear that size of the maximum flow in this graph is indeed the answer to the problem.

As a final note, the judges know the solution that runs in O(n) and requires no maximum flow algorithms, challenge yourself to come up with it!

C. Homework

The solution is constructive.

  • First let us use backtracking to find solutions for all n, m < 5, it is also better to precalculate all answers, in order not to mess with non-asymptotic optimizations.
  • Now m ≥ 5.
  • Let us put asterisks from left to right, one row after another. When adding the new asterisk, we add 4 new L-trominoes, except the first asterisk in a row that adds 1 new L-tromino, and the last asterisk in a row adds 3 new L-trominoes. Let us stop when the number of remaining L-trominoes k is less than 4, or there are less than 5 free squares in the table.
  • Now there are two cases
    • there is a free row
    • thee is no free row
  • If there is a free row, we stopped because k is now less then 4. So:
    • k = 0: the solution is found
    • k = 1: if there are already at least 2 asterisks in the current row, put the asterisk in the beginning of the next row, if there is only 1, put it in the end of the current row
    • k = 2, k = 3 — similar, left as an exercise.
  • If there are now free rows left, one can see that you can only add k from the set {0, 1, 2, 3, 4, 5, 6, 8, 9, 12, 15} L-trominoes.
  • And finally there is also the special case where the size of the board is 3 × m, m ≥ 5 and k = 2 * (m - 1) - 8 — in this case the first column should be left empty, and the rest of the board must be completely filled with asterisks.
D. Slalom

First let us consider all paths from the starting square to the finish one. Let us say that two paths are equivalent, if each obstacle is at the same side for both paths. For each class of equivalence let us choose the representative path — the one that tries to go as low as possible, lexicographically minimum.

Let us use dynamic programming. For each square let us count the number of representative paths that go from the starting square to this one. When the obstacle starts, some paths can now separate. The new representatives will pass this obstacle from above (it will be to the right of them). So we add the sum of values for squares below it, but above any other lower obstacle, to the value for the square right above the obstacle.

To overcome the time and memory limits that the naive solution with O(nm) memory and O(nm2) time complexity, we use segment tree for range sum queries with mass update, running scanline and events "start of an obstacle", "end of an obstacle". This leads to the solution with O(m) memory and O(nlogm) time complexity.

E. Cipher

First let us consider a slow solution. Let us find a condition for each number k after what number of seconds Borya can distinguish it from the given number. Let us look at their initial encoding. Increase both numbers by 1 until the encodings are different (or one of the numbers needs more than n digits to represent in which case the beep allows Borya to distinguish the numbers as well).

Now there are two main ideas that allow us to get a better solution. First, we don't have to check all numbers. We only need to check numbers that differ from the given number in exactly one digit.

Second: to get the time when the numbers can be distinguished we don't need to iterate over all possible values. We just need to try all digit positions and all values for that position, and check only moments when the digit at the position will first have this value in one of the numbers.

So the complexity is now polynomial in n and since n ≤ 18, it easily fits into the time limit.

F. Array Covering

We give the outline of the solution, leaving technical details as an excercise.

First note that the answer will always use min(k - n, 0) subarrays with maximal sums. Sof let us find the sum of min(k - n, 0) maximal subarrays, elements that are used in them, and the following min(k, n) subarrays. We can do it using binary search for the border sum, and a data structure similar to Fenwick tree. For the given value of the sum this tree must provide the number of subarrays with greater or equal sum, sum of their sums, and the set of the elements of these subarrays. It should also allow to list all these subarrays in linear time complexity. This part has time complexity O(nlog2n).

Let us now describe how to solve the problem in O(n2logn). Let us try all values of x — the number of subarrays with maximum sums that we will use in our solution (there are O(n) variants, because top min(k - n, 0) subarrays will definitely be used). Let elements with indices i1, ..., im be the ones that are not used in these subarrays. Now we must add k - x segments that would contain all of these elements. Note that each of these k - x segments must contain at least one of these elements, and no two segments can have a common element among them (in the other case the solution is not optimal). These observations let us greedily choose these k - x segments in O(nlogn) and the final solution complexity is O(n2logn)

To optimize this solution, we keep segments [ij + 1; ij + 1 - 1] in the ordered set. When we iterate over x and increase its value, we remove some of the ij-s, and recalculate the required values for the affected segments. After that we must take k - x maximal values from the set, so since there are O(n) changes in total, this part now works in O(nlogn).

Full text and comments »

  • Vote: I like it
  • +67
  • Vote: I do not like it

By RussianCodeCup, history, 8 years ago, translation, In English

Hi, everyone!

Tomorrow, on September 18, 2016, at 12-00 the Final Round of Russian Code Cup 2016 will take place. Top 50 participants of the Elimination Round will take part in the contest and have a chance to win great prizes. The length of the Final Round this year is 2 hours, the Final Round participants will compete online. You can watch the Final Round at http://russiancodecup.ru

Meanwile we are pleased to announce that the Russian Code Cup team together with Codeforces project have prepared a small surprise to all those who didn't manage to get to the Final Round of RCC-2016. After the Final Round ends, at 14-05 Codeforces will host online-contest with RCC-2016 Final Round problems.

The contest will use ACM ICPC rules and will not be rated. Problems will be in English and in Russian. Problems were prepared for Russian Code Cup Final Round, so they are quite difficult, the contest is mostly suitable for Div1 participants. Of course, we would like to ask the Final Round participants do not use the contest for testing their upsolved solutions, please wait until the end of the online contest and use the problem archive.

So, everyone is welcome to watch the Final Round and then to take part in the online-contest! Good luck to everybody!

Full text and comments »

  • Vote: I like it
  • +90
  • Vote: I do not like it

By RussianCodeCup, history, 8 years ago, translation, In English

Hello!

Let us remind you that Russian Code Cup 2016 Elimination Round will take place on June 19, 2016 at 14-00 Moscow time. Top 200 from each qualification round can take part in Elimination round, 200 best coders in Elimination round will get branded championship t-shirt, and top 50 will advance to the Final Round that will take place in September. There are money prizes to grab in the Final Round.

Good luck everyone and see you at http://russiancodecup.ru !

Full text and comments »

  • Vote: I like it
  • +62
  • Vote: I do not like it

By RussianCodeCup, history, 8 years ago, translation, In English
A. Rectangle and Squares

To solve this problem, notice that the sides of the Elijah's rectangle don't matter, only the area is considered. So he can use any number of squares to create a rectangle of size C × nC for any positive integer n.

The optimal n is the result of the division AB / C2 rounded either up or down. So we just check two variants and choose the better one. Additionally, it is important to remember that n > 0, so sometimes it is impossible to round down.

B. Zeroes and Ones

First notice, that we can make inversions only in one string. Also notice that the order of inversions doesn't matter.

So the solution is greedy: consider characters of the first string from left to right. If the corresponding character s1[i] ≠ s2[i], we inverse characters i, i + 1 of the first string. In the end check that s1[n] = s2[n], if it's not, there is no solution, in the other case we have found the only, and therefore optimal, solution.

C. New Track

The solution is using special construction.

First, let us show how to create the track with maximal possible k. Starting with the horizontal segment, each vertical segment would cross all previous horizontal segments except the adjacent one. The example with 14 segments is shown in the picture.

To get exactly k segments first draw 2l segments such that l(l - 1) / 2 ≥ k > (l - 1)(l - 2) / 2, make a small track with k intersections. To do so, start creating the maximal example, but terminate the last segment after required number of intersections. The remaining n - 2l segments can be added in the beginning of the track to form the spiral around the smaller track. See picture below for example, where n = 17 and k = 9.

The constraint on k is really the maximal bound on the number of intersections of n segments. We omit the proof, but the hint is: look at the number of intersections of the pair of segments n and n - 1 with pairs n - 3 and n - 4, n - 5 and n - 6, ..., 2 and 1 (or only the segment 1, if n is even).

D. Tree

Let us add weights to tree edges, and set edge weight equal to 1 initially for all edges. Now instead of removing the vertex we would change the weight of the edge from it to its parent to 0. The distance between any pair of vertices would be equal to the distance that would be should we had actually removed the vertex.

We can solve the new problem as follows. For each vertex in the initial vertex find the distance from the root to the vertex, and put the distances to the array in DFS order. After changing some edge weight, we must change the distances in the continuous segment of the array. This can be implemented using, for example, range tree.

Now the distance between vertices can be found, using : dab = da + db - 2·dlca, where lca — is the least common ancestor of a and b, dv — is the distance from the root to v.

E. Barbarians

Notice that the angriness of all people in one connected component is equal to their initial angriness multiplied by some value, the same for all islands in this component.

Let us process edge removal in time proportional to the size of the smaller components that appears after its removal. In this case the time complexity of the algorithm would be . To prove the complexity notice that for each vertex when it is in the smaller component, the size of the component at least halves. So it can only happen times.

If removing the edge we could know which component is smaller, we could traverse it and move its vertices to a new component, leaving the vertices from the larger one in the old one. But we don't know which component is smaller. So let us run two BFS-s simultaneously in both components, and when one of them terminates, terminate the other one as well. This way the time for such BFS would be proportional to the size of the smaller component.

Full text and comments »

  • Vote: I like it
  • +12
  • Vote: I do not like it

By RussianCodeCup, history, 8 years ago, translation, In English

Hi, all!

The last possibility to get to the Elimination Round of Russian Code Cup this year is the Third Qualification Round, that will take place on Sunday, June 5, 16:00. Everyone who has not yet qualified is welcome to participate. Good luck, and see you at Russian Code Cup 2016!

Full text and comments »

  • Vote: I like it
  • +54
  • Vote: I do not like it

By RussianCodeCup, history, 8 years ago, translation, In English

Hi all!

The second qualification round of Russian Code Cup 2016 will take place on Sunday, May 29, 2016, at 12-00! We invite everyone who has not qualified yet to take part. Those who would not qualify in the second round are invited to take part in the third round on June 5. Good luck to everyone and see you at the round, don't forget to register for the championship at http://russiancodecup.ru if you haven't done so already.

Full text and comments »

  • Vote: I like it
  • +36
  • Vote: I do not like it

By RussianCodeCup, 8 years ago, translation, In English

A. Binary String

First notice that there is no solution in one of the following two cases:

  • Either |b - c| > 1
  • Or b = 0, c = 0, and both a ≠ 0 and d ≠ 0

For other cases there are two steps in the solution. First, construct the minimal string that satisfies conditions for 01 and 10 pairs. After that add a - 1 zeroes after the first zero, and d - 1 ones after the first one.

B. Train in a Tunnel

The solution is greedy.

First let's turn the light on in the first and in the last car. Then divide the train to one or more segments of continuous cars with light off. Сonsider one such segment. Iterate over cars and when you the sum of lengths of such cars would exceed h if we didn't turn the light on in the current car. Then turn the light in that car on, and continue from the next car.

C. Beautiful Partition

Consider a[1], it is either in M1, or in M2. Since it doesn't matter, let it be in M1. Then a[1] divides gcd(M1), therefore gcd(M1) — is the divisor of a[1].

Consider all divisors of a[1] (there are at most 1344 for numbers not exceeding 109). For each each divisor d all elements of the array that are divisible by dcan be put to M1 (in this case gcd(M1) would not be less then d, and the fewer elements are there in M2 — the greater gcd(M2) is), all the other elements can be put to M2. The answer can be relaxed with the value min(gcd(M1), gcd(M2)). For the purpose of relaxation we can ignore that M2 is empty and consider gcd for an empty set be equal to infinity. If we put any element to M2 the value of gcd(M2) will not be less then d in this case since all elements are divisible by d.

The time estimation is O(sqrt(a[1] + d(a[1])·n) where d(a[1]) ≤ 1344.

D. Problem Preparation

First let us solve the problem if there are no changes in ti. Let us generate new array cnt[j] equal to the count of i such that ti = j. Also calculate the array of prefix sums for cnt. Then for each k we can find the time for each friend in O(MAX / k) where MAX is the maximal time needed for one problem. We just iterate over all j and find the number of problems that require exactly j minutes for each friend using prefix sums array. The sum for all valid k of O(MAX / k) is O(MAXlogMAX).

Now let us see what happens if we change the time needed for the problem from t to t + 1. Note that only values for k which are divisors of t change. Since the number of divisors is small, we can just iterate over all divisors and change the answer just for them.

Similar idea works when t changes to t - 1, the answer changes only for such k that are divisors of t - 1.

E. Similar Subways

You have to find isomorphic connected subtrees of the two given trees with maximal number of vertices. Let us use dynamic programming to solve the problem.

Consider two directed edges (u1, v1) in the first tree and (u2, v2) in the second tree. Let the value dp[u1][v1][u2][v2] be equal to the maximal size of isomorphic subtrees, such that u1 is corresponding to u2 and vertices v1 and v2 are not included into the corresponding subtrees. Additionally, let us also calculate such value for v1 =  - 1 or v2 =  - 1, which means that any vertex from the first/second tree can be in a subtree. Then the answer to the problem is maximum over all u1, u2 of the values dp[u1][-1][u2][-1].

To calculate dp[u1][v1][u2][v2] we have to make correspondence between subtrees of u1 in the first tree and u2 in the second tree. Let us note that if e1 is the child of u1 not equal to v1, subtree of e1 contains fewer vertices then subtree of u1. So if we find the values in increasing order of sizes of subtrees, we can use values for all child subtrees. The value dp[e1][u1][e2][u2] gives us the maximal number we can get if we put correspondence between e1 and e2. So we can get the matrix a[e1][e2] which contains maximal values for each pair of adjacent vertices to u1 and u2, correspondingly. Now we have to find the maximal weight matching in this matrix which can be done by mincost flow, or Hungarian algorithm.

The complexity is O(n5).

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it

By RussianCodeCup, history, 8 years ago, translation, In English

Hello, all!

We are glad to announce the final version of Russian Code Cup 2016 rules! The most important news of this year is that Russian Code Cup goes international, now the problems are available in both Russian and English. Anybody can participate, to enter the competition, please register at http://russiancodecup.ru, participants of previous championships need to confirm their participation in their profile.

This year the prize pool is again 750 000 rub. We have changed the structure of the prizes to give more money prizes away, so top 25 now get cash. The winner gets 150 000 rub, the second place gets 100 000 rub, the third place gets 65 000 rub. Those who take places from 4 to 10 get 30 000 rub, and places from 11 to 25 can account for 15 000 rub. Top 200 in elimination round get branded Russian Code Cup t-shirts.

There are three levels of the championship. First you must qualify in one of the three Qualification Rounds (May 8, May 29 and June 5). Top 200 from each round proceed to Elimination Round (June 19), top 50 from it proceed to Final Round (September 18). If you fail to qualify in a Qualification Round you can still try in the following Qualification Rounds.

We invite you to the Qualification Round 1 on Sunday, May 8, 19-00 Moscow Time, and wish everyone good luck!

Full text and comments »

  • Vote: I like it
  • +74
  • Vote: I do not like it

By RussianCodeCup, history, 8 years ago, translation, In English

Hi!

We are pleased to announce that in 2016 Russian Code Cup goes international! Problems will be available in two languages: Russian and English, everyone is welcome to participate!

Championship rules and time table will be announced next week, meanwhile we would like to invite you to take part in Warm Up round on Saturday, April 23, 18-00 Moscow Time (UTC+3). Register at http://russiancodecup.ru and participate!

Good luck and see you at Russian Code Cup 2016!

Full text and comments »

  • Vote: I like it
  • +260
  • Vote: I do not like it