By RussianCodeCup, 9 days 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, 13 days 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  
  • +79
  • Vote: I do not like it