|
|
Show all threads Hide all threads Show all messages Hide all messages | How could I get WA#1... | Hello world! | 1615. Tram Solitaire | 10 Oct 2009 12:57 | 1 | It should be 2, and the answer is 2/3, How could this happen... Edited by author 10.10.2009 13:07 | solution | RAVEman | 1615. Tram Solitaire | 31 Jul 2008 14:55 | 10 | what is the solution for this problem? 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? Re: * 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. | n=3 answer=? | SHY | 1615. Tram Solitaire | 22 Jun 2008 16:38 | 2 | What's the answer for n=3? Is it 8/15 or not? --Checking...--Checked-- It really seems to be 8/15... Edited by author 09.04.2008 23:26 2: 2/3 3: 8/15 4: 13/28 5: 19/45 6: 13/33 I've got this examples after 15-minute execution of program. :-) I can not understand how to solve this problem, but I want to solve it myself. |
|
|
|