Discussion @ 1615. Tram Solitaire @ Timus Online Judge

Hello world! How could I get WA#1... // Problem 1615. Tram Solitaire 10 Oct 2009 12:57

RAVEman solution [9] // Problem 1615. Tram Solitaire 30 Mar 2008 17:30

what is the solution for this problem?

Ostap Korkuna (Lviv NU) Re: solution [8] // Problem 1615. Tram Solitaire 30 Mar 2008 22:39

A formula.

RAVEman Re: solution [7] // Problem 1615. Tram Solitaire 30 Mar 2008 23:52

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

Ostap Korkuna (Lviv NU) Re: solution [6] // Problem 1615. Tram Solitaire 31 Mar 2008 03:24

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

RAVEman Re: solution // Problem 1615. Tram Solitaire 31 Mar 2008 14:04

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

Nick J Re: solution [4] // Problem 1615. Tram Solitaire 31 Mar 2008 16:04

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

RAVEman Re: solution [3] // Problem 1615. Tram Solitaire 31 Mar 2008 17:41

Is it so important?

But - yes, i used GCD in my solution.

Nick J Re: solution [2] // Problem 1615. Tram Solitaire 2 Apr 2008 18:11

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

Брэнд * [1] // Problem 1615. Tram Solitaire 3 Apr 2008 19:41

Cool problem!
But does anybody know the mathematical proof?

Denis Koshman Re: * // Problem 1615. Tram Solitaire 31 Jul 2008 14:55

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.

SHY n=3 answer=? [1] // Problem 1615. Tram Solitaire 9 Apr 2008 22:45

Discussion of Problem 1615. Tram Solitaire