Editorial for DMOPC '17 Contest 3 P4 - Solitaire Logic

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: r3mark

For $30\%$ $30 %$ of the points, brute-forcing over the $\binom{2N}{N}$ $(\binom{2 N}{N})$ possible card configurations passes.

Time Complexity: $\mathcal O(NQ\cdot \binom{2N}{N}+N\cdot 2^{2N})$ $O (N Q \cdot (\binom{2 N}{N}) + N \cdot 2^{2 N})$

Consider a card with value $v$ $v$ placed at the $i^\text{th}$ $i^{th}$ position of the first row. Then it can be seen that the first $i-1$ $i - 1$ cards of the first row and the first $v-i$ $v - i$ cards of the second row must contain all the numbers from $1$ $1$ to $v-1$ $v - 1$ . The situation is similar if the card were in the second row.

For the next $30\%$ $30 %$ of the points, we use the above observation. Let $u$ $u$ be the highest value lower than $v$ $v$ which has been revealed and $w$ $w$ be the lowest value higher than $v$ $v$ which has been revealed. (If $v$ $v$ is already revealed, then the answer is clearly $1$ $1$ .) Since we know the region where all the cards from $1$ $1$ to $u$ $u$ are, and we know the region where all the cards from $1$ $1$ to $w-1$ $w - 1$ are, we can see that any card with value between $u$ $u$ and $w$ $w$ must be in a certain region, specifically the union of two subarrays. Additionally, the positions of the cards with value less than $u$ $u$ and the cards with value greater than $w$ $w$ do not affect $v$ $v$ 's position.

So it is enough to consider these two subarrays containing all cards with value between $u$ $u$ and $w$ $w$ . It is not hard to see that the cards which can have value $v$ $v$ form two subarrays. The boundary points of these subarrays can be found by placing the values in sorted orders and can be directly computed from knowing the positions of $u$ $u$ and $w$ $w$ . Alternatively, use the fact that the region of cards with value from $1$ $1$ to $v$ $v$ must contain the region of cards from value $1$ $1$ to $u$ $u$ and similarly with $w$ $w$ to find the positions where $v$ $v$ can be.

Time Complexity: $\mathcal O(NQ)$ $O (N Q)$

For the final subtask, $u$ $u$ and $w$ $w$ can be found in $\mathcal O(\log N)$ $O (\log N)$ by using a balanced binary search tree.

Time Complexity: $\mathcal O(N \log N)$ $O (N \log N)$

Comments

There are no comments at the moment.