| ENG RUS | Timus Online Judge |
Обсуждение задачи 1615. Трамвайный пасьянсHello world! How could I get WA#1... // Задача 1615. Трамвайный пасьянс 10 окт 2009 12:57 It should be 2, and the answer is 2/3, How could this happen... Edited by author 10.10.2009 13:07 RAVEman solution [9] // Задача 1615. Трамвайный пасьянс 30 мар 2008 17:30 what is the solution for this problem? Ostap Korkuna (Lviv NU) Re: solution [8] // Задача 1615. Трамвайный пасьянс 30 мар 2008 22:39 A formula. RAVEman Re: solution [7] // Задача 1615. Трамвайный пасьянс 30 мар 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] // Задача 1615. Трамвайный пасьянс 31 мар 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 // Задача 1615. Трамвайный пасьянс 31 мар 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] // Задача 1615. Трамвайный пасьянс 31 мар 2008 16:04 Do you need to find GCD in your solution ? Or GCD(denom, num) = 1 in your formula ? RAVEman Re: solution [3] // Задача 1615. Трамвайный пасьянс 31 мар 2008 17:41 Is it so important? But - yes, i used GCD in my solution. Nick J Re: solution [2] // Задача 1615. Трамвайный пасьянс 2 апр 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] // Задача 1615. Трамвайный пасьянс 3 апр 2008 19:41 Cool problem! But does anybody know the mathematical proof? Denis Koshman Re: * // Задача 1615. Трамвайный пасьянс 31 июл 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] // Задача 1615. Трамвайный пасьянс 9 апр 2008 22:45 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 ilovesky 5 examples // Задача 1615. Трамвайный пасьянс 22 июн 2008 16:38 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.
|