ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1615. Tram Solitaire

solution
Posted by RAVEman 30 Mar 2008 17:30
what is the solution for this problem?
Re: solution
Posted by Ostap Korkuna (Lviv NU) 30 Mar 2008 22:39
A formula.
Re: solution
Posted by RAVEman 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 :)
Re: solution
Posted by Ostap Korkuna (Lviv NU) 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 :)
Re: solution
Posted by RAVEman 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
Re: solution
Posted by Nick J 31 Mar 2008 16:04
Do you need to find GCD in your solution ? Or GCD(denom, num) = 1 in your formula ?
Re: solution
Posted by RAVEman 31 Mar 2008 17:41
Is it so important?

But - yes, i used GCD in my solution.
Re: solution
Posted by Nick J 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 :(
*
Posted by Брэнд 3 Apr 2008 19:41
Cool problem!
But does anybody know the mathematical proof?
Re: *
Posted by Denis Koshman 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.