By RussianCodeCup, 5 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).

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

5 days ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve E in ?

  • »
    5 days ago, # ^ |
    Rev. 2   Vote: I like it +28 Vote: I do not like it

    There is one trick to search all cycles of length 3.


    It seems that this code is slow but it works in O(n*sqrt) where n is number of vertexes in our graph (i don't remember proof of that). so use compression for numbers to make n = 400'000 not 1'000'000 in worth case

    so as you see this part solves when sides look like (x,y)(x,y) (x,z)(x,z) (y,z)(y,z). other cases, when answer looks like (x,x)(x,x)(x,x)(x,x)(x,x)(x,x) or (x,y)(x,y)(x,y)(x,y) (x,x)(x,x) can be solved in O(n*log) with map

5 days ago, # |
  Vote: I like it +13 Vote: I do not like it

D can be solved in O(1) by case-studying.

During contest, I coded a brute-force method to check all the possible assignment of knights and knaves for k ≤ 10. And, find out the pattern for each pair of