| ENG RUS | Timus Online Judge |
Обсуждение задачи 1284. Космический покерYu Yuanming How to solve it fast? [7] // Задача 1284. Космический покер 29 дек 2005 12:20 My algo is O(C(n,n/2)*n),where C(n, m)=n!/(m!(n-m)!),it takes 0.375sec,a bit slow:( I just want to know how to solve it less than 0.1sec? Do they use search? Edited by author 29.12.2005 12:40 Yu Yuanming Re: How to solve it fast? [6] // Задача 1284. Космический покер 29 дек 2005 12:34 I have found another two algo: 1.Use full search,O(2^n*n); 2.Use search + greedy,O(((m/2)!*n)^2). But they are not faster than the one above:( ahyangyi_newid Re: How to solve it fast? [5] // Задача 1284. Космический покер 9 янв 2006 13:17 OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOYEEEEEEEEEEEEEAAAAAAAH! I got AC in 0.015 sec after times of submitting~ Using only 134KB memoru~ Note that m (Number of suits) <=10. And we can check how many steps a state can be arrival in O(n^2). Also, you should do some pre-calculating instead of repeat the same thing for many times. Edited by author 09.01.2006 13:21 Yuen Yoon Ming Re: How to solve it fast? [2] // Задача 1284. Космический покер 10 янв 2006 21:14 Thank you for your reply. Yes, we can calculate how many steps a state can be arrival in O(n^2). I think your algo may look like the one that use search + greedy,O(((m/2)!*n)^2). But what is the exact time of your algo,could you tell me? Burunduk1 Re: How to solve it fast? [1] // Задача 1284. Космический покер 27 янв 2006 03:22 My solution also works in O(C(n,n/2)*n) But it gets AC in 0.062 Careful and fast implementation, nothing more. Yu Yuanming I see, thx. // Задача 1284. Космический покер 27 янв 2006 11:07 svr Re: How to solve it fast? [1] // Задача 1284. Космический покер 21 авг 2007 16:25 Friend! You keep in your secret the main tool: O(n^2) calculuce number of steps for arraving to [a1,a2,...,an] from[1,2,....,n]. This is brilliant theorem anf I spent 4 days before created it myself. answer=N-length of most long increasing subsequence. Глащенко Никита Re: How to solve it fast? // Задача 1284. Космический покер 27 авг 2009 13:47 AC in 0.031 with complexity O(X!Y!*N^2) and some optimization O_o OpenGL Mistake in statement [2] // Задача 1284. Космический покер 24 апр 2009 14:47 in russian, "Опытного игрока устраивать любой из них". OpenGL up [1] // Задача 1284. Космический покер 27 апр 2009 13:49 Sandro (USU) Fixed (-) // Задача 1284. Космический покер 27 апр 2009 23:02 Ich(USU) It seems that test #13 is incorrect [2] // Задача 1284. Космический покер 24 авг 2005 10:46 In my program there is such a fragment: Cs:array[1..10][1..100]of byte; ... read(n); fillchar(Cs,sizeof(Cs),0); for i:=1 to n do begin read(k,l); if Cs[l,k]>0 then MakeCrash; Cs[l,k]:=i; end; ... where MakeCrash is procedure which makes some crash(MLE,divide by zero...) And this program got CRASH on test #13. When i'v deleted MakeCrash ,it got WA#18. It may happens only if there is the same cards in input, but it is impossible due to the problem. Vladimir Yakovlev (USU) Some tests were corrected. You have AC now (-) [1] // Задача 1284. Космический покер 26 авг 2005 09:47 Ich(USU) Re: Some tests were corrected. You have AC now (-) // Задача 1284. Космический покер 30 авг 2005 13:57 Thank you :) Vladimir Yakovlev (USU) Problem 1284 "Cosmic Poker". New tests were added to this problem (+) // Задача 1284. Космический покер 27 июл 2005 14:15 Time limit was reduced to 1 second also. All ACs will be rejudged soon. Huang Yuanhe I think 1 second for this problem is quite enough! [3] // Задача 1284. Космический покер 23 апр 2004 09:48 http://acm.timus.ru/status.aspx?space=1&pos=578044 I've got accept in 0.015 second. So 5 seconds is no need!!! Dmitry 'Diman_YES' Kovalioff Mine is 0.03, and I agree with you (-) [1] // Задача 1284. Космический покер 10 авг 2004 11:24 Shteiner Sergei Re: Mine is 0.03, and I agree with you (-) // Задача 1284. Космический покер 18 окт 2004 19:32 How did you do this? My algorithm is (n*2^n); Hard ( DHSP ) Re: I think 1 second for this problem is quite enough! // Задача 1284. Космический покер 2 июл 2005 08:05 I'm a bit faster than you and I used less memory than you ! 870224 Pascal Accepted 0.001 157 KB Edited by author 02.07.2005 08:06 Edited by author 02.07.2005 08:07 Maigo Akisame (maigoakisame@yahoo.com.cn) Why are there 4 yellows but only 1 blue in the example? // Задача 1284. Космический покер 23 сен 2004 20:35 Danica Porobic WA on #5, please help. // Задача 1284. Космический покер 19 авг 2004 14:51 Is there any trick in test #5? Dmitry 'Diman_YES' Kovalioff Test#4 is incorrect! (+) [1] // Задача 1284. Космический покер 10 авг 2004 11:29 In test#4 N=20, but it should be less than 20 ("N<20" in both - english and russian - texts). Vladimir Yakovlev (USU) Now N<=20 in problem text (-) // Задача 1284. Космический покер 10 авг 2004 12:01 Khlyzov Andrew Can anybody hint me how to solve this problem? // Задача 1284. Космический покер 3 авг 2004 14:31
|