## 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

Hint 1 Look for a card that we know must have a value of .
Hint 2 The position of the first card tells us how many cards we have inserted at this point.
Solution First, look for the first where . We know that card must have a value of . Furthermore, we know there are  's in the hand so far, and the remaining cards are all 's. From this point on, any card with must be a and any card with must be a , and we can recover the card counts. This algorithm only fails when for all , which can only happen if all the 's are inserted before all the 's. The probability of this happening is , which is extremely small when . There are no such cases in the generated test data, so this algorithm passes subtask 1.

Time Complexity: Hint Use a more general brute force approach.
Solution Throughout the process, we can express a current state by an array of size , 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 time or worse, but they turn out to be surprisingly fast on random cases when as many possibilities get pruned out rapidly. Finally, we make a random guess out of the possible card counts.

It turns out that for , 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.

Hint 1 Let's suppose for simplicity that each of the values appear at least once among the first cards and among the last cards (intuitively, we might set here). What do we know about cards among the last cards that have ?
Hint 2 These cards all have a value of . Now consider what happens if we were to have inserted these cards before all the other cards are inserted. How would this change the array?
Hint 3 Every would get incremented by the number of 's inserted after card . Now ignoring the cards, what does the new minimum in the last cards represent?
Hint 4 The new minimum gives us a count of how many 's were inserted in total, and indices that achieve this minimum all have a value of .
Hint 5 Repeat this process for values to get counts of how many of the values are inserted. We can then determine the number of 's inserted. This should achieve an approximately success rate and get most of the points.
Hint 6 If implemented well, this algorithm surprisingly still works if we set and achieves a success rate. For example, instead of finding all cards with value 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 be the number of cards of value 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 iterations, all the cards with values will have been moved to this group. Most of the time (i.e. with probability on the generated test data), there will always be an undeleted card with value remaining after iterations. This card will define the value , causing to be in each of the iterations. We can then take adjacent differences to recover .

It turns out that this algorithm only fails when there exists some such that all occurrences of card are before all occurrences of card . In that situation, it is impossible to tell how many of these cards are or , 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 such cases. The number in the problem was chosen so that just slightly over 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: or 