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

Revision en1, by AlexFetisov, 2016-04-25 03:44:24

#### 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 % 2 != 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 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.

#### History

Revisions

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