First of all, congratulations to jqdai0815 for winning, LHiC and jcvb for coming second and third. The Final Round proved to be quite challenging, and we are happy that the results are tight.

The round was prepared by Aksenov239, GShark, izban, manoprenko, niyaznigmatul, qwerty787788 and SpyCheese, supervisor andrewzta. Special thanks for this round goes to izban who is the author of problems D, E and F, and also gave a lot of important comments for all problems of the round.

Now let us move on to the editorial.

E. Satellites

Any point X can be given by two angles α = XAB and β = XBA.

The point (α₂, β₂) is in coverage area of a satellite at the point (α₁, β₁), if α₂ ≤ α₁ and β₂ ≤ β₁.

Let two satellites that want to create a communication channel are at points (α₁, β₁) and (α₂, β₂). Repeater must be positioned in such point (α₀, β₀), that α₀ ≤ min(α₁, α₂) and β₀ ≤ min(β₁, β₂). To make it harder for it to get to other satellites coverage area, it is reasonable to maximize α₀ and β₀: α₀ = min(α₁, α₂), β₀ = min(β₁, β₂).

Now let us move to a solution. Consider a query of type 3: you are given two satellites at points (α₁, β₁) and (α₂, β₂). You must check whether the point (α₀, β₀) = (min(α₁, α₂), min(β₁, β₂)) is not in the coverage area of any other satellite. That means that among all satellites with α ≥ α₀ the maximum value of β is smaller than β₀.

The solution is offline, it considers all satellites from the test data and just turns them on and off. Sort all satellites by α. Each moment for each satellite we store its β if it exists, or  - ∞ if it doesn't. Let us build a range tree for maximum, and update values as satellites come and go. The query is a range maximum. To avoid considering the satellites from the query, change their values to  - ∞ before the query, and restore them afterwards.

The next thing to do is to get rid of floating point numbers. Instead of calculating the angle values, we will only compare them using cross product. Similarly, instead of storing β values in range tree, we will store indices and compare them by cross product in integers.

The final remark: we need to check that the point (α₀, β₀) is not inside the planet. The point is inside the planet, if the angle AXB is obtuse, that can be checked by a scalar product of XA and XB. The point X can have non-integer coordinates, so we will not look for it, but will use colinear vectors from among those connecting satellite points to A and B.

Hi, everyone!

On September 10, 2017 at 13:00 Moscow time the final round of Russian Code Cup 2017 will take place! The round will be 3 hours long. 55 participants of the final round will compete for prizes and glory, and we are eager to watch their competition at http://russiancodecup.ru.

And we have a nice surprise for the others: if you would like to apply your skills at our finals problems, come to codeforces.com after the Finals is over, at 16:35 Moscow time, the round featuring RCC Finals 2017 problems will take place, open for everybody.

Some notes:

• Round will use ACM rules;
• It will be unrated;
• Problem difficulty will be close to Div 1 round;
• We ask RCC finalists not to publish or discuss problems after the end of the Finals before the CF round ends, of course you shouldn't participate in CF round;
• Judging machines at RCC and CF are different, "my solution passed/failed at CF, and it was different at RCC" is not a valid appeal.

UPD The official contest is over, congratulations to the winners! And good luck to CF Round participants.

UPD2 Editorial

A. Small Numbers

First of all, find prime factorization of numbers a and b.

After that you need to notice that if ab is divisible by p², (where p is a prime number), it is either possible to divide both a and b by p instantly, or you will need to perform one of the latter two operations first to move one of p factors to the other number, and then divide both by p.

Obviously, parity of occurrence of prime numbers in the multiple ab remains unchanged in all operations. Therefore we can either remove p factor completely from ab or leave it occurring only once. After removing all primes, lets say the ones left are p₁, p₂, ..., p_n. Let us call multiple of all these numbers d. Important observation is that n can't exceed 14 because multiple of first 15 prime numbers is more than 10¹⁸, which means it can't be a product of two numbers a, b ≤ 10⁹. Now we simply need to iterate over all possible pairs and chose one with minimum sum that we can obtain from d. This can be done in O(2ⁿ) which fits the time limit.

B. New Keyboard

Let us use dynamic programming. The state is d[i][j][k], where i — is the flag that denotes the previous action (0 for layout switch, and 1 for typing character), j is the number of the current layout, and k is the number of characters typed so far. The value is the minimal time to reach the state.

Now iterate over k. For a given k first iterate j from 1 to n twice. Both times relax d[0][j % n + 1][k] = min(d[0][j % n + 1][k], min(d[0][j][k] + b, d[1][j][k] + a)). Two iterations of j from 1 to n are needed to ensure that if the layout switches from n to 1 it is processed correctly.

Now iterate j from 1 to n again and relax values for k + 1. If there is the k-th character of the message in the j-th layout, update d[1][j][k + 1] = min(d[0][j][k], d[1][j][k]) + c.

The answer is min(d[1][j][m]), where m = length(s), for all j from 1 to n.

C. Folding the Figure

Note that there are exactly 4 possible folding lines: two horizontal and two vertical, because the figure must be at one side of the folding line, and must touch it.

Take any square of the folded figure with the minimal x-coordinate. Let it be the cell (x_i, y_i). Take line x = x_i as the folding line. Now we need to find k - n squares of the original figure on the other side of the folding line. So let us find k - n connected squares of the folded figure containing the square (x_i, y_i), for example, using DFS.

D. Acute Triangles

To count the number of acute triangles let us count the total number of triangles and subtract the number of right and obtuse triangles. For the purpose of this problem let us consider three points on a line to be a degenerate obtuse triangle.

The total number of triangles is equal to the number of ways to choose 3 points of n.

Now note the fact: each right or obtuse triangle has exactly one right or obtuse angle. So the number of bad triangles is equal to the number of bad angles.

Now let us count the number of angles not less than 90 degrees with vertices in the given points. Consider the angle vertex and sort other points by their polar angle relative to the chosen point. Now use two pointers: consider the first of the other two points, the matching third points form a continuous segment along the circle, and its ends move in the same direction.

Time complexity is O(n²log(n)).

E. Joining Arrays

Let us consider two solutions for the problem, that take O(k²·log(k)) and O(k²) respectively. The first one brings up core ideas, while the second one being more elusive has simpler implementation.

O(k²·log(k)) solution:

Consider three main steps of the solution

1. For each array X (A or B) and each length 1 ≤ length ≤ |X| find minSubsequence_X[length] — lexicographically smallest subsequence of X that has the given length;
2. Iterate over t such that 1 ≤ t ≤ min(k - 1, |A|) and 1 ≤ k - t ≤ |B|, take minSubsequence_A[t] and minSubsequence_B[k - t], join them;
3. Joining the given sequences, get the optimal sequence of length k, update the answer with that sequence.

1) To find minSubsequence_X[length] for each length, let us do the following:

• Calculate next[i][c] that will store the next occurence of value c after i in X;
• Calculate firstSymbol[length][i] — the first character of lexicographically smallest subsequence of X[i..|X| - 1] that has given length. To calculate it note the following:
  • If j₁ = next[i][1], and it exists, then firstSymbol[1][i], firstSymbol[2][i], ... firstSymbol[|X| - j₁][i] are equal to 1;
  • If, if j₂ = next[i][2], and it exists, then firstSymbol[|X| - j₁ + 1][i], ..., firstSymbol[|X| - j₂][i] are equal to 2;
  • ...
  • If j₃₀₀₀ = next[i][3000], and it exists, then firstSymbol[max(|X| - j₁, |X| - j₂, ..., |X| - j_3000 - 1) + 1][i], ..., firstSymbol[|X| - j_|alphabet|][i] are equal to 3000.
• After that we can use firstSymbol[length][i] to restore lexicographically smallest subsequence of each array, one by one.

This step takes O(|X|²).

3) Given two lexicographically minimal subsequences S_A and S_B, now we need to join them to lexicographically smallest sequence. Let us use two pointers p₁ and p₂. If S_Ap1 ≠ S_Bp2, we move the smaller pointer, appending the value it points at to the answer. If S_Ap1 = S_Bp2, use binary search to find the longest common prefix of S_A[p₁..|S_A|] and S_B[p₂..|S_B|], and compare the following elements. Use hashes to compare subarrays of S_A and S_B.

This step takes O((|S_A| + |S_B|)·log(max(|S_A|, |S_B|))) = O(k·log(k)).

So the total time complexity is O(|A|² + |B|² + k²·log(k)) = O(k²·log(k)).

O(k²) solution:

Let us index arrays, let array A have number 0, and array B have number 1. Let us build the answer one element after another, and maintain the values dp[i][j], where i is the number of the array (0 or 1), j is the index in this array, dp[i][j] is the minimal index in array 1 - i, that can be appended to the answer, if we are at index j in array i.

At the t-th of the k iterations we find the minimum element that can be appended to the answer, and still the answer can be completed by adding another k - t - 1 elements. Also we must note that both subsequences from the two arrays must be non-empty.

After adding the element v, update the dp values in O(|A| + |B|). To do it, use next array, the same as in previous solution.

F. Two Trees

There is a requirement that k-subtree must have a vertex at depth k. Let us temporarily remove this limitation.

Consider all k-subtrees for some value of k. They can be divided to equivalence classes. Let each vertex v have c_k[v] — the label of its equivalence class that its k-subtree belongs to.

If k = 0 all c₀[v] are the same, because 0-subtree of any vertex is this vertex by itself.

If k = 1 then c₁[v] is the number of children of v .

Now let us see how we can convert arrays c_k[v] and c_m[v] to an array c_k + m[v]. First let us assign the array arr_k + m[v] to each vertex v, that will uniquely identify its k-subtree. Let u₁, ..., u_s be its descendants of level k in DFS order. Then arr_k + m[v] = c_k[v], c_m[u₁], ..., c_m[u_s]. So its (k + m)-subtree is identified by its k-subtree and m-subtrees from the bottom vertices of its k-subtree. See the picture below for k = 3 and m = 1.

To get the list of descendants at level k, let us run one DFS from the root, when entering the vertex, put it to its k levels ancestor list.

To transform arr_k + m[v] to integers c_k + m[v] we can either use hashing, or trie, or unordered_map. Each vertex is considered only once in each of these arrays, so the total time is O(n).

Given array c_k[v] it is easy to check whether there are two equal k-subtrees. To do it you must find two vertices with the same c_k, considering only vertices that have descendants of level k (now we need to bring back this requirement).

To find the maximal such k, let us first count c₁[v], c₂[v], ..., c_2^t[v] (2^t is the maximal power of 2 not exceeding n). After that make some kind of binary ascending by k: start with k = 0, and try to add 2^t, 2^t - 1, ..., 2⁰, one by one.

Time complexity: O(nlog(n)).

Ready, steady, go!

It's time to find out who the top 50 participants to compete in the Final Round of Russian Code Cup 2017 are. We invite everyone qualified to take part in the Elimination Round this Sunday, May 14, 2017 at 13-00 Moscow Time. Round length is 2 hours. We invite you to russiancodecup.ru, and wish you good luck!

A. Spreadsheets

Let us subtract 1 from k, now the columns are numbered from 0.

Let us first find out how many characters are there in the name of the column. To do it let us subtract powers of 26 from k, one by one, until the current power is greater than the remaining number k'.

Now the name of the column is k' in 26-based notation where characters A–Z are used as digits, prepended with leading A-s to the required length. You can either convert it using standard library function (in this case you must replace digits 0–9, A–P that will be used by the required digits), or implement a textbook algorithm of conversion to another base.

Final note: a day before the round one of the testers pointed out that CF Beta 1 Round problem B was similar to this one. After a discussion, taking into account that CF1 round was long ago, the problem is actually easier than CF1B problem, and we had no well prepared and easy enough replacement problem, we decided to keep the problem.

B. Mortal Combat

Let us count how many hit points the boss loses if attacked by the i-th hero: p_i = a_i·⌈ h_i / A⌉. Sort heroes by non-increasing of p_i and send them to attack the boss in this order.

C. A Bit Palindromic Numbers

Let us find out how to count a bit palindromic numbers among the first n positive integers. Now to solve the problem for the range from l to r we count the number of a bit palindromic numbers among first r, among the first l - 1, and subtract the latter from the former.

All numbers from 1 to 9 are a bit palindromic, so if n ≤ 9 the answer is n. Otherwise let us add 9 to the answer and count a bit palindromic numbers from 10 to n. Let us consider ten integers from 10k to 10k + 9, where k ≠ 0. Only one of them is a bit palindromic, the one that has the same first digit as k. So there is one a bit palindromic number from 10 to 19, one from 20 to 29, and so on.

Let n = 10k + d, where 0 ≤ d ≤ 9. So if d is greater or equal to the first digit of k, there are k a bit palindromic numbers from 10 to n, if it is less then the first digit of k, there are k - 1 such numbers.

D. Tree and Polynomials

Let us walk through the key ideas of the solution.

First, notice that6 you can solve problem independently for the two types of the queries. That is because operations don't depend on the values in the vertices.

Second idea is the following. Instead of storing particular values in the vertices, let us store polynomial that must be evaluated from it depth to get the value.

We cannot process queries directly, considering all vertices affected by a query, and adding the query polynomial to the polynomial in the vertex: that would take O(n²·k) which is too slow. Let us use lazy propagation then.

For the queries of the first type we need to add a polynomial q(t) to each vertex in a subtree of v. Let us just store information about that: for each vertex v let us store push1[v] that has the sum of all polynomials that affected the vertex v in queries of the first type.

Simultaneously let us store the sum of all affecting queries of the second type as a polynomial push2[v] for each vertex v.

Now denote as sum1[u] the sum of all polynomials that affect vertex u in queries of the first type.

To calculate sum1[u] let us run DFS from the root, and keep track of a polynomial cur. Entering the vertex v add push1[v] to cur, leaving v subtract it back. When we have entered the vertex u, assign sum1[u] = cur.

Similarly, denote as sum2[u] the sum of all polynomials that affect the vertex u in queries of the second type.

To calculate sum2[u] also use DFS, sum2[u] is equal to the sum of values sum2[v] for all children of u, and the value push2[u].

After we have calculated polynomials sum1[u] and sum2[u] for each vertex, evaluate them on d[u] and add the results, that is the answer for that vertex.

Time and memory are both O(nk).

E. Nice Report

Let's solve one additional problem before proceeding to the main one. You are given a sequence (a₁, a₂, ..., a_n) of some objects and somebody asks you to find out how many different objects are presented in this sequence. However, some restrictions apply to the ways you are allowed to process given data:

1. once the object a_i is read, it's lost forever: the next read will return a_i + 1 and there is no way to obtain a_i again;
2. you can only use O(1) additional memory

To solve this subproblem we will use the fact that expected value of minimum of m value uniformly distributed over segment [0;1] is 1 / (m + 1).

Consider a hash function h: A → [0;1] which transforms objects a_i to some number from [0;1]. Define M as M = min {h(a₁), h(a₂), ..., h(a_n)}. This value can be transformed to the problem solution as 1 / M - 1. However, we could run out of luck and end up in the situation where some h(a_i) is too small and spoils the answer too much. To deal with it, we can average the answer over several runs with different hash functions h₁, h₂, ..., h_k for some fixed k.

First, let's solve the case of acyclic graph. Any acyclic graph has topological sort: vertices order that respects edge directions: only edges from latter vertices to earlier ones exist. Let's label each vertex with some random number uniformly distributed over [0;1]. Topological sort existence allows us to calculate the minimal reachable label M_i for each vertex by some kind of dynamic programming. After this calculation, we can approximate the number of reachable vertices from i as 1 / M_i - 1. Again, we need to average results from several iterations to improve answer precision.

But given graph can contain cycles. To create an acyclic graph we can build the graph condensation by compressing strongly connectivity components. In the condensed graph each vertex i corresponds to w_i vertices in the original graph. To finally solve the problem we'll change vertex labeling phase a bit: a simple random label becames minimal value from w_i random value from [0;1] rolls.

A curious reader can find more information related to this problem by reading an article "Size-Estimation Framework with Applications to Transitive Closure and Reachability" located at http://cohenwang.com/edith/Papers/tcest.pdf.

Hi, everyone!

There are already more than 400 participants who are preparing for the Elimination Round of Russian Code Cup 2017. If you are still among those who has not qualified yet, we invite you to take part in the Third Qualification Round that will take part this Saturday, April 29, at 14-00 Moscow Time. Top 200 participants will also qualify to the Elimination Round and will be able to compete to get to the Final Round of Russian Code Cup 2017.

Good luck and see you at russiancodecup.ru!

A. Very Important Persons

There are two main ways to solve the problem.

The first way is to assign guests to seats by diagonals, starting from the seat (1, 1). You should be careful with considering cases n < m and m < n when implementing traversal.

The second way is a more common solution which however requires more advanced algorithm. Let us run BFS from (1, 1) and assign seats to guests in order they are popped from the queue, starting from the most important one.

B. Least Common Multiple

Let p / q be divisible by both a / b and c / d, all fractions are irreducible. So the numbers (p / q): (a / b) = (p·b) / (q·a) and (p / q): (c / d) = (p·d) / (q·c) are integers.

Since p·b is divisible by q·a, b and a are relatively prime, then p is divisible by a. p and q are also relatively prime, so b is divisible by q. Similar argument allows to conclude that p is divisible by с, and d is divisible by q.

Therefore p is divisible by lcm(a, c), q is a divisor of gcd(b, d). The fraction lcm(a, c) / gcd(b, d) is divisible by both a / b and c / d, and is therefore the smallest such fraction. So the answer is lcm(a, c) / gcd(b, d).

C. Bad Order

You have to add numbers to the given array to convert it to a permutation that requires maximal number of swaps when being sorted by selection sort.

First suppose that the permutation is fixed. Let us find the number of swaps that selection sort makes. Consider permutation as a set of cycles. Let us consider a cycle that contains the minimal number that occupies wrong position. Length of this cycle is greater than 1. After we make a swap, it is split to two cycles: of length 1, and 1 shorter than its initial length. Therefore the cycle of length L will be split L - 1 times, so the number of swaps required is n - c, where c is the number of cycles.

Therefore we must add numbers to the given array in such way that the number of cycles in the resulting permutation was minimal possible. To do it consider the given array as a directed graph, if a[i] = j, add an edge from i to j. The graph is a union of cycles and paths. All cycles in the graph will remain there after we convert the array to a permutation. All paths can be concatenated to a single long cycle (vertices without both incoming and outgoing edges are considered paths of length 0). To do so, order paths arbitrarily, and add an edge from the end of each path to the beginning of the next path. Finally make them a single cycle by adding an edge from the end of the last path to the beginning of the first one.

D. Red-Black Tree

First you must notice a subtle hint in the first sentence of the statement. It is easy to prove (or find in any data structures textbook) that red-black tree with n vertices has O(log(n)) black vertices on any path from the root to a leaf. Let us use this fact in our solution.

Let us call a tree almost red-black if its coloring satisfies all constraints of the red-black tree, except that its root is red.

We can now use dynamic programming to calculate for each subtree the number of ways to color it to become red-black or almost red-black, and to have the number of black vertices on any path from its root to a leaf equal to h.

Let us denote the described number of ways as d[v][h][t], here v is the vertex, h is the number of black vertices on any path from v to a leaf in its subtree, t is the type of coloring, t equal to 0 would, for example, mean that the subtree is red-black, and t equal 1 would mean that the subtree is almost red-black.

Now d[v][h][0] is the product for all u children of v of values (d[u][h - 1][0] + d[u][h - 1][1]). Similarly, d[v][h][1] is the product for all u children of v of values d[u][h][0].

The answer to the problem is the sum for all h of values d[1][h][0].

Since h for all valid colorings is limited by C = O(log(n)), we can consider the number of colorings be zero if h > C.

So we only need O(nlog(n)) states, and O(1) to calculate the result for each state. The time complexity is O(nlog(n)).

E. Array Study

Since there are the same constrains to n and q, let us use n instead of max(n, q). Let us make some observations.

Observation one: the answer to the query is the maximal length of [L, R], such that pref_L - 1 = pref_R, where pref_i = a₁ + a₂ + ... + a_i is the prefix sum of the given array. Let us move from the initial array to the array of prefix sums and for a query [l, r] look for the longest subarray of [l - 1, r] such that pref_L = pref_R.

Observation two: pref_i are quite small ( - n ≤ pref_i ≤ n).

Let us make use of queries given offline. Our method will be similar to Mo's algorithm. Split all queries to groups, the i-th group will contain queries [l_i, r_i] such that i·K ≤ l_i < (i + 1)·K (here K is approximately sqrt(n)). In each group sort queries by their right end. Let us solve the problem separately for each group.

Consider the i-th group, where l_i is in [L_i, R_i]. Let us consider queries by non-decreasing of r_i, and maintain two arrays: mostLeft[p] and mostRight[p] — the first after R_i and the last before r occurrence of the prefix sum p. Using these two values, we can find the answer that is subarray of [R_i + 1, r]. To get the complete answer to [l, r] query, let us calculate the answer with the beginning of the required subarray at [l, min(r, R_i)] using mostRight array, and take maximum of that value and the optimal subarray for [R + 1, r].

So it takes O(K·c_i + n) to answer all queries of one group, here c_i is the number of queries in that group. Adding up all O(n / K) groups, we get the total time complexity O(sum(i = 1... n / K: K·c_i + n)) = O(K·sum(c_i) + n² / K). Setting K = sqrt(n) we get O(n·sqrt(n)) complexity.

Hello everyone!

Top 200 from the First Qualification Round have already advanced to the Elimination Round, but the other paricipants still strive to get there. If you haven't qualified yet, we invite you to take part in the Second Qualification Round that will take place this Sunday, April 16, at 12-00 Moscow Time. Best 200 participants will advance to the Elimination Round, other participants can try again in the Third Qualification Round.

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

A. Martian Volleyball

First note that in order to end the game as soon as possible only the currently leading team must get points.

Consider the condition that one of the teams wins. It must score at least k points and have at least 2 points advantage.

So the answer is max(k, min(x, y) + 2) - max(x, y).

B. Painting the Wall

First note that if the maximal length of the continuous segment is L, at least L colors are needed to paint the wall. On the other side L colors is always enough.

Consider a square L × L, fill the first line with integers from 1 to L, fill the following lines with all its possible circular shifts. Use these squares to cover the given wall rectangle like this (L = 4):

Now each vertical and horizontal segment of length L or less has all tiles of different colors. All that is left is to bring back the lamps.

C. Magic Artifact

Let us denote advantage that Maxim gets if he finds artifact as c_i, so c_i = a_i - b_i.

Let Maxim first complete levels in order 1, 2, ..., n. If he finds the artifact at the i-th level, the time he needs to complete the game is equal to b_j plus c₁ + ... + c_i. So the expected time of completing the game is:

b₁ + ... + b_n + p₁·c₁ + p₂·(c₁ + c₂) + ... + p_n·(c₁ + ... + c_n).

b₁ + ... + b_n doesn't depend on level order, so let us try to make the rest as small as possible. Expanding the sums, we get sum of all c_i·p_k for such i, k that i ≤ k.

Let us now swap levels i and i + 1 in our order. For the given i among c_i·p_k terms only the one equal to c_i·p_i + 1 changes — it is replaced with c_i + 1·p_i. If the order was optimal, it must be c_i·p_i + 1 ≤ c_i + 1·p_i, in the other case it was optimal to swap them and get a better answer. Transform this to:

c_i / p_i ≤ c_i + 1 / p_i + 1.

In the optimal answer for all i from 1 to n - 1 this inequality must be satisfied. Therefore it is optimal to sort levels according to the key c_i / p_i. Note that if p_i = 0, you may consider c_i / p_i = ∞.

Sorting according to the key c_i / p_i should be done carefully. If the fractions are compared using floating-point division, the case c_i = p_i = 0 will lead to error because 0 / 0 = NaN. If the fractions are compared using the comparator c_i·p_k < c_k·p_i, the case c_i = p_i = 0 will also lead to error because the result of that comparison will always be false. That means that levels with c_i = p_i = 0 should be handled separately. Such levels can be completed at any time because they do not affect the result besides fixed terms b_i. For example, they can be placed at the end.

After sorting the desired expected value can be found using the formula above, use prefix sums for c_i to get it fast.

D. Memory Manager

First for each query q_i let us find go_i — the minimal j, such that among q_j, q_j + 1, ..., q_i there are at most k different blocks — that would mean that it is possible to place pointers before the j-th query in such way that queries j, j + 1, ..., i are performed immediately. This can be made in O(sum(|q_i|)), using, for example, two pointers.

Now let us use dynamic programming, denote as dp_i the minimal time needed to perform the first i queries. If go_i = 0 then dp_i = 0. If the equation is not satisfied, dp_i = min_{j = goi..i}(dp_j - 1 + s_j) — we choose the query j to perform the pointer movement before. Since values go_i do not descend, this value can be maintained using either std::set of dp_j - 1 + s_j, or queue with minimum query support.

E. LISA

First let us consider the problem for given two strings: to solve it calculate the number of occurrences of each letter in the first string, the number of occurrences of each letter in the second string, not including the first letter of the first string and the last letter of the second string, that must be used any way. Now the answer is the product of string lengths, decreased by the sum of values cnt1[letter] * cnt2[letter] for each letter. Let us leave proof as an exercise, such problem was at Northern Subregional Contest of NEERC 2015 http://neerc.ifmo.ru/archive/2015/northern/north-2015-statements.pdf, Problem C. Unlimited participants could solve this problem at Three Quaterfinals Cup.

For n strings similar ideas can be used. Put all strings to a prefix trie, all strings to a suffix trie, the total number of ways to get a string is the product of the number of vertices in these tries. What we need to subtract is similar product of number of occurrences of letters in tries, first/last letters of each word must not be considered.

Now we need to answer segment queries. Let us make sqrt-decomposition, divide all strings to groups based on sum of their lengths. Let us greedily add strings to a group until their sum of lengths is more than sqrt(total sum of lengths). Note that the last string can have a big length.

Now use Mo's algorithm, sort queries using the block of the left end as a key, move right end only forward between left end block changes. To add/remove a string to a trie one must maintain the number of active vertices in a trie subtree for each vertex, and the number of entries of letters to a trie.

Hi, everyone!

This Sunday, April, 2 at 19-00 Moscow time the First Qualification Round of Russian Code Cup 2017 will take place. 200 top participants will qualify for the Elimination Round, those who wouldn't qualify can still take part in two following qualification rounds.

We have a news for you: we have added Kotlin, Haskell and Free Pascal to our list of programming languages, also you can now submit your Python programs to run in PyPy. Exact versions of compilers and compilation commands are published at the official web site. We are working on adding more programming languages.

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

UPD Editorial is published

Hello, everyone and thank you for participation!

First of all we would like to say sorry for the length of the testing queue during the first hour. We have selected IOIP problems for the Warmup Round — there are many common problemsetters for IOIP and RCC — the round was prepared by Victoria Erokhina (viktoria), Dmitry Filippov (DimaPhil), Stanislav Naumov (josdas), Mikhail Putilin (SpyCheese), Grigory Shovkoplyas (GShark), Andrew Stankevich (andrewzta), Ilya Zban (izban). We wanted to let everyone solve our interesting problems.

But one small glitch lead to a big failure. You might have noticed that we usually make multiple tests in one input data for RCC. That is because the most expensive operation is to run user solution. But IOIP has fewer participants, so the easiest problem had 32 tests. It is not too many for a problem, but during 15 minutes 400 participants submitted the correct solution and our testing machines capacity was not enough.

We decreased the number of tests in the problem, and the situation got better. We will take this into account when preparing problems for future contests.

Now let us proceed to problem analysis.

Hi, everyone!

We are pleased to announce Russian Code Cup 2017! Qualification rounds will start in April, the Final round will be held online in September. Each of the three Qualification rounds will allow 200 participants to qualify for Elimination round, top 50 from Elimination round will proceed to Final round. The problems will be both in Russian and in English.

The full schedule of the tournament can be found at http://russiancodecup.ru, you can also register there. Note that you must register for the new season even if you took part in the previous tournaments.

We still have more than two weeks before the first Qualification, so we would like to invite everyone to the warm up round that will take plance on Sunday, March 19, 14-00 Moscow time. Visit http://russiancodecup.ru to take part in the round, it will be 2 hours long.

Good luck to everyone and see you at Russian Code Cup 2017!

UPD: We remind you that the Warmup Round will start at 14-00 Moscow time. Problems of the Warmup Round are based on IOIP problems (Russian contest for high school students, run today at several cities) that are prepared by the same team of authors. We kindly ask students that take part in IOIP to play fairly and not to try to take part in RCC Warmup. Good luck to everyone!

UPD2: Thanks to all participants that made a real stress testing for our judging machines. Unfortunately we had long queues during the first hour, they were fixed, and from the middle of the contest the waiting time in most cases was limited to 2-3 minutes. We will make sure there would be no queues during further rounds.

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.

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!

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 !

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!

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.

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 M₁, or in M₂. Since it doesn't matter, let it be in M₁. Then a[1] divides gcd(M₁), therefore gcd(M₁) — is the divisor of a[1].

Consider all divisors of a[1] (there are at most 1344 for numbers not exceeding 10⁹). For each each divisor d all elements of the array that are divisible by dcan be put to M₁ (in this case gcd(M₁) would not be less then d, and the fewer elements are there in M₂ — the greater gcd(M₂) is), all the other elements can be put to M₂. The answer can be relaxed with the value min(gcd(M₁), gcd(M₂)). For the purpose of relaxation we can ignore that M₂ is empty and consider gcd for an empty set be equal to infinity. If we put any element to M₂ the value of gcd(M₂) 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 t_i. Let us generate new array cnt[j] equal to the count of i such that t_i = 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 (u₁, v₁) in the first tree and (u₂, v₂) in the second tree. Let the value dp[u₁][v₁][u₂][v₂] be equal to the maximal size of isomorphic subtrees, such that u₁ is corresponding to u₂ and vertices v₁ and v₂ are not included into the corresponding subtrees. Additionally, let us also calculate such value for v₁ =  - 1 or v₂ =  - 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 u₁, u₂ of the values dp[u₁][-1][u₂][-1].

To calculate dp[u₁][v₁][u₂][v₂] we have to make correspondence between subtrees of u₁ in the first tree and u₂ in the second tree. Let us note that if e₁ is the child of u₁ not equal to v₁, subtree of e₁ contains fewer vertices then subtree of u₁. So if we find the values in increasing order of sizes of subtrees, we can use values for all child subtrees. The value dp[e₁][u₁][e₂][u₂] gives us the maximal number we can get if we put correspondence between e₁ and e₂. So we can get the matrix a[e1][e2] which contains maximal values for each pair of adjacent vertices to u₁ and u₂, 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(n⁵).

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!

A. Secret Code

All you have to do is just implement the required counting. Identifying correct characters at correct positions is absolutely straightforward. Identifying correct characters at incorrect positions can be, for example, implemented using used[c] array with true values for characters in the secret code and false for other characters.

B. Chaos

Consider two maximal numbers of the initial array. The maximal possible value that can be obtained is their average value.

To prove this, you can see Doc's moves as removing one number from the board and replacing two other numbers with two copies of their average value. So the average value of two maximal numbers never increases.

The following strategy allows to get such value in the end: each move remove the minimal number and replace two maximal numbers with two copies of their average values. Starting from the second move the two maximal numbers will be the same and equal to the answer.

C. New Adventure of Marty and Doc

You have to minimize the sum Sum(i = 1..n, j = 1..m, 2·a_i, j·(|i - x| + |j - y| + 1)). First notice that no term depends on both coordinates, so the sum can be divided to three sums: Sum(2·a_i, j), Sum(2·a_i, j·|i - x|) and Sum(2·a_i, j·|j - y|).

The first sum is constant for the given input, so we need to minimize the second and the third sum which can be done independently by choosing the row and the column. Consider the second sum, it can be proved that the optimal value is achieved if we take r equal to the median of Sum(j = 1..m, a_1, j) times 1, Sum(j = 1..m, a_2, j) times 2, ..., Sum(j = 1..m, a_n, j) times n.

Column can be found using the same idea.

D. Teams Creation

Let's use dynamic programming.

Sort all skill levels, and for each value find the number of students with such skill level. Note that if the team contains students with skill levels l and r, all students with skill levels m such that l < m < r will also be in the same team. So let us calculate the value dp[i][j][f] — the number of ways to create j teams of students with skill levels up to i, the last team can (f = true) or cannot (f = false) have more students. To make a transition we need additional value f[k][g] counts the number of ways to create g teams of k students that have the same skill level. Let there be k students with skill level i + 1, we iterate over g from 1 to k and relax dp[i + 1][j'][f'] using f[k][g]. Note that this takes O(nk) because the total number of g attempted for each j is equal to n.

To find f[k][g] we consider the k-th student. He is either in the team on his own (f[k - 1][g - 1]) or in one of the other teams (f[k - 1][g]·g).

Both arrays are calculated in time O(nk), so the time complexity is O(nk).

E. Maximal Sum

Let us sort b_j in decreasing order. Add values to array a in decreasing order as well until all numbers greater or equal to the current b_j is added. Now the array contains only numbers a_i ≥ b_j. After adding the new a_i use interval tree to find the maximal sum subsegment at the segment (see discussion here, for example, to learn how to do this using interval tree: http://mirror.codeforces.com/blog/entry/17780).

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!