Contest Duration: - (local time) (180 minutes) Back to Home

C - Random Card Game Editorial by evima

First, let us find the minimum score for a fixed pair of two piles. Let $$A_1, \ldots, A_N$$ be the ID numbers of one pile (call it Pile $$A$$) from top to bottom, and $$B_1, \ldots, B_N$$ be the ID numbers of another pile (call it Pile $$B$$) from top to bottom.

Assume that Card $$2N$$ is in Pile $$B$$. Then, for each $$1 \leq i \leq N$$, we can take the minimum $$j$$ such that $$A_i < B_j$$. Let $$d$$ be the maximum value of $$j - i$$. Then, it turns out that the minimum score is $$N+d$$. We do need at least $$N+d$$ operations, since if we take $$i$$ such that $$j-i=d$$, we have to remove $$d$$ or more cards from Pile $$B$$ to remove Card $$A_i$$. On the other hand, we can always remove one card from Pile $$A$$ or decrease $$d$$ by $$1$$, by choosing the minimum $$i$$ such that $$j-i>0$$ if $$d>0$$ and choosing the maximum $$i$$ such that $$j-i=0$$ if $$d=0$$ and doing the operation with $$k=i$$. Now, we have shown that the minimum score is $$N+d$$.

Next, let us find the expected value of this. For each $$0 \leq d \leq N-1$$, let $$p(d)$$ be the probability that the minimum score is at most $$N+d$$. Then, the expected value we seek is $$2N - \sum_{d=0}^{N-1} p(d)$$, so we just have to $$p(d)$$.

Again, let us fix the pair of two piles and assume that $$A_1,\ldots,A_N,B_1,\ldots,B_N$$ are constant. If $$2N$$ is among $$B_1, \ldots, B_N$$, the minimum score is less than $$N+d$$ if and only if:

• for each $$1 \leq i \leq N$$, there is a value greater than $$A_i$$ among $$B_1, \ldots, B_{\min\{N,i+d\}}$$.

The probability that $$A_1,\ldots,A_N,B_1,\ldots,B_N$$ satisfy this condition is:

$$\prod_{1 \leq i \leq N-d} \frac{2i+d-1}{2i+d} \times \prod_{N-d < i \leq N} \frac{N+i-1}{N+i}$$.

$$p(d)$$ is the above value multiplied by $$2$$, so we can find $$p(1), \ldots, p(N)$$ in linear time. Thus, we can solve the whole problem in linear time, too.

posted:
last update: