Which country are you playing for?

India lost because you didn't give Codechef October Cookoff today :(

Edited, thanks

You are almost done, you can choose the one which is minimum among those $$$p_i \ne i$$$, and among multiple minimums choose the one whose parent (the one on the side of incoming edge) is maximum and move this element to its correct place. You can prove this construction by looking at separate cases — When the cycle has some vertex with potential 1 (in that case we will always move vertex with $$$V_i=1$$$ to its correct place and it can be proved that potential remains at least $$$2 * (sz - 1)$$$ afterwards) and when no vertex has $$$V_i=1$$$ we can make any swap to move some element to its correct position and we will be having enough potential.

Yes, the winning condition is exactly that.

Let's first decrease some $$$v_i$$$ values so that the condition is strict: $$$\sum{v_i} = 2 \cdot (|cycle| - 1)$$$. Now, as long as the cycle length is more than $$$2$$$, it can be proved by induction that there will always be a cycle member satisfying $$$v_i = 1$$$.

You just have to repeatedly keep finding an element $$$v_i = 1$$$ and deleting it by swapping it with the previous element in the cycle. This can be done with queue to store all candidates + set/linked_list to find a previous element.

Did the English statement say one by one at the start or was it updated in-between? I don't remember one by one being there when I read the statement. However its possible I just missed it since I also missed the word "only" later on in the statement.

1
5
1 2
2 3
3 1
4 5
5 4

For the above testcase, the answer should be "No", your solution gives "Yes".

You have to do the same check for the block in the last row.

Find modulus:

Print any $$$x \geq 10^{18}$$$ in the first query, you will get a remainder $$$r$$$ back.

Clearly $$$x = n \times k + r$$$ for some $$$k \geq 1$$$ since $$$x \geq 10^{18} \geq n$$$.

Subtract $$$r + 1$$$ from both sides of the equation.

We then get $$$x - (r + 1) = n \times k - 1 = n \times (k - 1) + (n - 1)$$$

So querying $$$x - (r + 1)$$$ gets you back the value of $$$n - 1$$$.

Reach the end:

It is unreachable if there is a diagonal that cuts the board into two parts.

This diagonal will either be from the left column to the top row $$$[(1, x), (2, x - 1), \ldots, (x, 1)]$$$ or from the bottom row to the right column $$$[(n, n - x), (n - 1, n - x + 1),\ldots, (n - x, n)]$$$, you can clearly check both by iterating from the first column and last column and checking the rows progress as expected till you reach the first / last row respectively.

You can start by turning off CAPS-LOCK. 3 in next contest guaranteed.

Did anyone receive the Voucher for this contest? I got the confirmation on Jan 5 but have not received the voucher after that.