By RussianCodeCup, history, 10 days ago, translation, In English,

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 prefL - 1 = prefR, where prefi = a1 + a2 + ... + ai 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 prefL = prefR.

Observation two: prefi are quite small ( - n ≤ prefi ≤ 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 [li, ri] such that i·K ≤ li < (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 li is in [Li, Ri]. Let us consider queries by non-decreasing of ri, and maintain two arrays: mostLeft[p] and mostRight[p] — the first after Ri and the last before r occurrence of the prefix sum p. Using these two values, we can find the answer that is subarray of [Ri + 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, Ri)] using mostRight array, and take maximum of that value and the optimal subarray for [R + 1, r].

So it takes O(K·ci + n) to answer all queries of one group, here ci 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·ci + n)) = O(K·sum(ci) + n2 / K). Setting K = sqrt(n) we get O(n·sqrt(n)) complexity.

Read more »

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

By RussianCodeCup, 13 days ago, translation, In English,

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!

Read more »

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

By RussianCodeCup, history, 3 weeks ago, translation, In English,

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

1 2 3 4 1 2 3 4 1 2

2 3 4 1 2 3 4 1 2 3

3 4 1 2 3 4 1 2 3 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 ci, so ci = ai - bi.

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 bj plus c1 + ... + ci. So the expected time of completing the game is:

b1 + ... + bn + p1·c1 + p2·(c1 + c2) + ... + pn·(c1 + ... + cn).

b1 + ... + bn 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 ci·pk for such i, k that i ≤ k.

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

ci / pi ≤ ci + 1 / pi + 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 ci / pi. Note that if pi = 0, you may consider ci / pi = ∞.

Sorting according to the key ci / pi should be done carefully. If the fractions are compared using floating-point division, the case ci = pi = 0 will lead to error because 0 / 0 = NaN. If the fractions are compared using the comparator ci·pk < ck·pi, the case ci = pi = 0 will also lead to error because the result of that comparison will always be false. That means that levels with ci = pi = 0 should be handled separately. Such levels can be completed at any time because they do not affect the result besides fixed terms bi. 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 ci to get it fast.

D. Memory Manager

First for each query qi let us find goi — the minimal j, such that among qj, qj + 1, ..., qi 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(|qi|)), using, for example, two pointers.

Now let us use dynamic programming, denote as dpi the minimal time needed to perform the first i queries. If goi = 0 then dpi = 0. If the equation is not satisfied, dpi = minj = goi..i(dpj - 1 + sj) — we choose the query j to perform the pointer movement before. Since values goi do not descend, this value can be maintained using either std::set of dpj - 1 + sj, 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.

Read more »

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

By RussianCodeCup, 4 weeks ago, translation, In English,

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

Read more »

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

By RussianCodeCup, 5 weeks ago, translation, In English,

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.

A. Spaceship

Note that if the last enemy to destroy has power equal to x, the sum of powers of all enemies is 2x. Therefore to find the power of the enemy to destroy last, let us find the sum of all powers and divide it by two. After that just pick any enemy with such power and swap it with the last one.

B. Rangers in the Bus

Let us process passengers one by one. Since Pink Ranger could take any seat, any passenger can be Pink Ranger.

For each seat we want to be able to quickly answer if it is free. Let us use std::set that stores the set of occupied seats. To check whether the current passenger can be Red Ranger let us find the seat that Red Ranger would choose. Iterate row from 1 to n, and if there is a free seat in the current row, take the left seat if it is free, or the right seat in the other case. If the current passenger chose that seat, he could be Red Ranger. Similarly we can check whether the current passenger could be Blue, Black or Yellow Ranger. After processing the passenger, add the seat he chose to the set of occupied seats.

The solution described uses O(nk) time and O(k) memory.

To get rid of time limit, let us note that all we need is to store the minimal and the maximal row that have free seats. Use two indices first and last to store them. Initially first = 1, last = n. After each passenger update these values. Increase first by 1, until the row pointed by first is completely occupied, then similarly decreaser last. There are at most k / 2 occupied rows, so both indices will be changed O(k) times.

C. Magic Weapon

Precalculate arrays: R[a][b] — the number of red details that have the first digit of the model number equal to a and the last digit equal to b; G[a] — the number of green details that have the last digit equal to a; и B[b] — the number of blue details that have the first digit equal to b.

It model numbers of different colors were distinct, the answer would be equal to the sum for all a and b of values G[aR[a][bB[b].

To resolve the situation when some pair of details have the same model number, calculate the number of red-blue pairs with the same model number, red-green pairs and green-blue pairs. Note that only model numbers with the same first and last digit need to be considered. You can use std::map to calculate the number of such model numbers. Now use inclusion-exclusion principle to find the answer: subtract the number of pairs of each type and add back twice the number of triples that all three rangers use detail with the same model number.

D. Knights and Knaves

Let us use dynamic programming with mask of the last two columns as a state. Consider for example subtask of calculating the maximal number of knights.

Let dp[i][mask_prev][mask_cur] be the maximal number of knights that can be positined among the first i columns, where mask_cur is the mask of the i-th column, mask_prev is the mask of the (i - 1)-th. Use bit equal to 1 to denote a knight and 0 to denote a knave.

Try all possible masks for the (i + 1)-th column, check whether constraints for the soldiers in the i-th column are satisfied, because now we know all of their neighbors.

The first and the last columns must be considered separately, because soldiers there don't have one of the neighbors.

Initial values: dp[2][mask_prev][mask_cur] the number of ones in mask_prev and mask_cur, if mask_prev can be before mask_cur.

Updating values: relax dp[i + 1][mask_cur][mask_next] with dp[i][mask_prev][mask_cur] + ones(mask_next), where ones(x) is the number of ones in x.

The answer is the maximum among dp[k][mask_prev][mask_cur], such that mask_cur can be after mask_prev.

Finally, we probably need to consider k = 1 separately, because there is no previsous column for any column in this case.

E. Parallelepiped

Let us give a sketch of the main solution idea. First, separately consider all parallelepipeds that have two or three equal sides. This can be done in O(n).

Now let us consider the case where all three sides are different. Let us build the following undirected graph: vertices are side length, connect a and b if there are at least two sheets of size a × b. Now the problem is reduced to considering all triangles in this graph which can be done in O(n2 / w) or O(nsqrt(n)) time (here w is the word size, 32 or 64 which comes up from bit compression).

Read more »

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

By RussianCodeCup, 6 weeks ago, translation, In English,

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.

Read more »

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