Editorial for DMOPC '22 Contest 1 P4 - Card Game

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: zhouzixiang2004

Subtask 1

Hint 1

Look for a card that we know must have a value of $2$ .

Hint 2

The position of the first $2$ card tells us how many $1$ cards we have inserted at this point.

Solution

First, look for the first $i$ where $b_i > 0$ . We know that card $i$ must have a value of $2$ . Furthermore, we know there are $b_i$ $1$ 's in the hand so far, and the remaining cards are all $2$ 's. From this point on, any card $j$ with $b_j = 0$ must be a $1$ and any card $j$ with $b_j > 0$ must be a $2$ , and we can recover the card counts. This algorithm only fails when $b_i = 0$ for all $i$ , which can only happen if all the $2$ 's are inserted before all the $1$ 's. The probability of this happening is $\frac{N+1}{2^N}$ , which is extremely small when $N = 100$ . There are no such cases in the generated test data, so this algorithm passes subtask 1.

Time Complexity: $\mathcal{O}(TN)$

Subtask 2

Hint

Use a more general brute force approach.

Solution

Throughout the process, we can express a current state by an array of size $K$ , representing the number of occurrences of each card so far. From this, we can use various brute force techniques, such as recursive backtracking or dynamic programming, to brute force all sequences of drawn cards that are consistent with the information we know. These algorithms may appear to take roughly $\mathcal{O}(N^K)$ time or worse, but they turn out to be surprisingly fast on random cases when $K = 5, N = 100$ as many possibilities get pruned out rapidly. Finally, we make a random guess out of the possible card counts.

It turns out that for $K = 5, N = 100$ , the probability of generating a case that is not uniquely solvable is very low. All cases in the generated test data have a unique sequence of card counts consistent with the information, and this algorithm passes subtask 2.

Subtask 3

Hint 1

Let's suppose for simplicity that each of the values $1,2,\dots,K$ appear at least once among the first $B$ cards and among the last $N-B$ cards (intuitively, we might set $B \approx \frac{1}{2}N$ here). What do we know about cards among the last $N-B$ cards that have $b_i = 0$ ?

Hint 2

These cards all have a value of $1$ . Now consider what happens if we were to have inserted these cards before all the other cards are inserted. How would this change the $b_i$ array?

Hint 3

Every $b_i$ would get incremented by the number of $1$ 's inserted after card $i$ . Now ignoring the $1$ cards, what does the new minimum $b_i$ in the last $N-B$ cards represent?

Hint 4

The new minimum $b_i$ gives us a count of how many $1$ 's were inserted in total, and indices $i$ that achieve this minimum all have a value of $2$ .

Hint 5

Repeat this process for values $2,3,\dots,K$ to get counts of how many of the values $1,2,\dots,K-1$ are inserted. We can then determine the number of $K$ 's inserted. This should achieve an approximately $94.7\%$ success rate and get most of the points.

Hint 6

If implemented well, this algorithm surprisingly still works if we set $B = 0$ and achieves a $99.7\%$ success rate. For example, instead of finding all cards with value $1$ in the first phase, we will find all cards that were the smallest in the hand when it was inserted. It turns out that this information is enough.

Solution

Let $c_i$ be the number of cards of value $i$ in the final hand. Consider the following algorithm:

Repeat K times:
    let m be the minimum element in b
    for i = size(b) to 1:
        if b[i] equals m, delete b[i] from b
        else increment b[i] by the number of deletions so far

In this algorithm, we can visualize deleting a card as moving it to a large group of cards that will be picked up all at once and sorted before inserting the remaining cards one by one, as usual. After $k$ iterations, all the cards with values $1,2,\dots,k$ will have been moved to this group. Most of the time (i.e. with $> 99.7\%$ probability on the generated test data), there will always be an undeleted card with value $k+1$ remaining after $k$ iterations. This card will define the value $m$ , causing $m$ to be $0, c_1, c_1+c_2, \dots, c_1+c_2+\dots+c_{K-1}$ in each of the $K$ iterations. We can then take adjacent differences to recover $c_i$ .

It turns out that this algorithm only fails when there exists some $1 \le i < K$ such that all occurrences of card $i+1$ are before all occurrences of card $i$ . In that situation, it is impossible to tell how many of these cards are $i$ or $i+1$ , so the test case is not uniquely solvable. Such cases are quite rare, and every test file in the generated test data contains less than $0.3\%$ such cases. The number $99.7\%$ in the problem was chosen so that just slightly over $99.7\%$ of the cases have a unique answer consistent with the given information.

Any algorithm that is guaranteed to guess correctly when there is a unique answer can fully solve the problem, and there are many other approaches possible.

Time Complexity: $\mathcal{O}(TKN)$ or $\mathcal{O}(TN^2)$

Comments

There are no comments at the moment.