|
|
| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | How to solve it fast? | Yu Yuanming | 1284. Космический покер | 27 авг 2009 13:47 | 8 | 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 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:( 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 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? My solution also works in O(C(n,n/2)*n)
But it gets AC in 0.062
Careful and fast implementation, nothing more. 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. AC in 0.031 with complexity O(X!Y!*N^2) and some optimization O_o | | Mistake in statement | OpenGL | 1284. Космический покер | 27 апр 2009 23:02 | 3 | in russian, "Опытного игрока устраивать любой из них". up OpenGL 27 апр 2009 13:49 | | It seems that test #13 is incorrect | Ich(USU) | 1284. Космический покер | 30 авг 2005 13:57 | 3 | 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. | | Problem 1284 "Cosmic Poker". New tests were added to this problem (+) | Vladimir Yakovlev (USU) | 1284. Космический покер | 27 июл 2005 14:15 | 1 | Time limit was reduced to 1 second also.
All ACs will be rejudged soon. | | I think 1 second for this problem is quite enough! | Huang Yuanhe | 1284. Космический покер | 2 июл 2005 08:05 | 4 | How did you do this?
My algorithm is (n*2^n); 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 | | Why are there 4 yellows but only 1 blue in the example? | Maigo Akisame (maigoakisame@yahoo.com.cn) | 1284. Космический покер | 23 сен 2004 20:35 | 1 | | | WA on #5, please help. | Danica Porobic | 1284. Космический покер | 19 авг 2004 14:51 | 1 | Is there any trick in test #5? | | Test#4 is incorrect! (+) | Dmitry 'Diman_YES' Kovalioff | 1284. Космический покер | 10 авг 2004 12:01 | 2 | In test#4 N=20, but it should be less than 20 ("N<20" in both - english and russian - texts). | | Can anybody hint me how to solve this problem? | Khlyzov Andrew | 1284. Космический покер | 3 авг 2004 14:31 | 1 | |
|
|
|
