The easy subtask can easily be solved by a straightforward simulation of the game.
In the worst possible case, the simulation will take Θ(n2) steps. The worst possible case is actually pretty simple: a sequence of cards of the same suit, sorted in descending order. In each pass through the deck you will only be able to place one of the cards onto their slot. A straightforward simulation for n = 250 000 would take hours. Given enough computational power, and considering the length of our practice session, it was possible to solve the hard subproblem in time – but there clearly has to be a better way!
One thing that should be obvious is that we can consider each suit separately. That is, we can separately compute the number of rounds we need to play each suit, and then compute the final answer as the maximum of those four numbers.
Hence, we just need to come up with a good way to solve the problem for a single suit. Let’s discover it on an example. Assume that the spades in our deck are ordered as follows:
S10 S8 S1 S4 S7 S6 S5 S11 S2 S13 S9 S3 S12
What will happen in the first pass through the deck? We discard the 10, discard the 8, put the 1 onto the slot for spades, discard a bunch of other cards, put the 2 onto the 1, discard the 13, discard the 9, put the 3 onto the 2, and discard the 12. That’s it for the first pass.
You may now note that we managed to remove the first three cards from our deck: first the 1, then the 2, and then the 3. We were able to remove the 2 in the same pass as the 1 because the 2 appeared later in the deck. We were able to remove the 3 in the same pass as the 2 because the 3 appeared later in the deck as the 2. And we were unable to remove the 4 in the same pass, because by the time we got to the 3 we already discarded the 4.
But that’s precisely the observation we needed! For each i, a new round will begin between cards i and i + 1 are played if and only if card i + 1 appears before card i in the deck.
Using this observation, we can easily compute the number of rounds in linear time: First, we go through the deck and for each value we note its index in the deck. Then, we go through all values and for each value we compare its index to the index of the next value.