what is the solution for this problem?

A formula.

I understood that after seeing that AC solutions used 100Kb memory and about 0.001-0.015 sec.

Give me some hints Ostap. :) I've spent many hours on it but still no luck :)

My solution was "half guessing / half interpolation" :)
I just bruteforced few answers. Guessed the denominator of the formula and then counted it's numerator assuming that it is a polynomial of degree 2.
Later after the contest Vasya told me, that he produced that formula on paper theoretically. So, the strict theoretical approach is also possible. But guessing is much faster :)

It's amaizing!!! Yours solution is just great (much better than Vasya's math solution), it took about 5-10mins to get AC!

Thanks Ostap!

Edited by author 31.03.2008 14:16

Do you need to find GCD in your solution ? Or GCD(denom, num) = 1 in your formula ?

Is it so important?

But - yes, i used GCD in my solution.

Well, formula is simpler than expected. No factorials and big numbers. Probably I incorrectly computed answers for small n-s during contest :(

Cool problem!
But does anybody know the mathematical proof?

I think it can be proven by induction. Though, it most probably won't give you "sense of the things", you'll have that proof :)

So far my thoughts are the following:

1. Since we remove the leftmost pair, we can lay down the whole deck at once and then perform sifting. This simplifies further thoughts a bit.

2. It might be more convenient to count amount of unsiftable final positions multiplied by number of original permutations converging to them. Unsiftable positions will be of the form ABBAABBAABB.. or AABBAABBAABB.. due to suits restriction.

I think that multiplier erradicates most of (2n)! in denominator, and since history effect is 2-cards wide, the answer will be 2-polynomial.