VK Cup 2016 — Раунд 2 (editorial)

Revision en3, by AlexFetisov, 2016-04-26 02:08:07

Problem A (div2):

It is obvious that we need to make sequence of moves like: 1, 2, 1, 2, ...

So the answer is 2 * n / 3. After that we have either 0, 1 or 2 stones left. If we have 0, we are done, otherwise we have 1 or 2 left, so we only can give 1 more stone.

Final formula is: (2 * n) / 3 + (n % 3 != 0 ? 1 : 0);

Problem B (div2):

We can just emulate grasshopper behavior and save all positions it visits. It is obvious that we will have no more than O(n) different positions. If grasshopper appears in the same position twice that means that there is a loop and the answer is INFINITE. Otherwise the answer is FINITE.

Problem A(div1)/C(div2):

Let's have 2 matrices: a, idx. In a we will have NULL for cell if we don't know the value or the value. idx will be initialized with idx[i][j] = {i, j}; Then we need to emulate the process on matrix idx. If we have 3rd query we can set up the value in matrix a, because we know the original position of that cell keeping idx.

Problem B(div1)/D(div2):

The key in this problem is that order of all elements in odd positions and in even positions is the same. Let's say we have 2 arrays: [1, 3, 5, ...] and [2, 4, ...] (odd positions and even positions). Now if we call 2nd commands we just swap these 2 arrays, but order is the same. Obviously 1st command also keeps the order. By order I mean cyclic order (right neighbor is the same in cycle position).

Let's just keep the position of 1st boy and 2nd boy. Now if we apply 1st operation we move it by X or -X. Second type of the query just swaps the positions. In the end we can construct the answer if we know positions of 1st and 2nd boys.

Problem C(div1)

First, let's solve inverse problem: find minimum (maximum) of two distributions. Let's use the following formulas:

P(a = k) = P(a <= k) — P(a <= k-1) P(max(a, b) <= k) = P(a <= k) * P(b <= k)

For minimum:

P(min(a, b) >= k) = P(a >= k) * P(b >= k) = (1 — P(a <= k-1)) *(1 — P(b <= k-1))

Now in our original problem minimum and maximum defines system of square equations for each pair P(a <= k), P(b <= k).

Solving these equations we get P(a<=k), P(b<=k) = (u + v ± sqrt((u + v)^2 — 4u)) / 2, where u = P(max(a,b) <= k), v = P(min(a,b) <= k). Now we can notice that if there exists an answer, then there exists an answer when we chose the signs for each pair equally (check out this comment)

Problem D(div1)/E(div2)

There are many ways to solve this problem. One of the ways was SQRT-decomposition. First let's compress all times. Now for each block in the decomposition we will store for each element the balance in that block. So to answer the query we need to calculate sum of balances from first block to the block before the one where our element is located and then just process all requests in the current block.

Another way was to use data structure from std library, described here. For each element we have two trees: remove times and add times. Then by getting order of the time in remove and add tree we can calculate the answer.

Rest of the editorial is coming soon.


  Rev. Lang. By When Δ Comment
ru5 Russian AlexFetisov 2017-03-12 06:02:56 2 Мелкая правка: 'ый ответ: (2 * n) / 3 + (n ' -> 'ый ответ: 2 * n / 3 + (n '
en6 English AlexFetisov 2016-05-06 10:11:40 1414
ru4 Russian AlexFetisov 2016-05-06 10:01:13 1331
ru3 Russian AlexFetisov 2016-05-04 01:37:39 360
en5 English AlexFetisov 2016-05-04 01:37:10 412 (published)
ru2 Russian AlexFetisov 2016-05-04 01:30:12 51 Мелкая правка: '# Задача A (div2):\n' - (сохранено в черновиках)
ru1 Russian AlexFetisov 2016-05-04 01:22:44 4321 Первая редакция перевода на Русский
en4 English AlexFetisov 2016-04-28 21:06:17 1152
en3 English AlexFetisov 2016-04-26 02:08:07 829
en2 English AlexFetisov 2016-04-25 10:55:52 2 Tiny change: ' 3 + (n % 2 != 0 ? 1 ' -> ' 3 + (n % 3 != 0 ? 1 '
en1 English AlexFetisov 2016-04-25 03:44:24 2468 Initial revision (published)