|
|
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 in russian, "Опытного игрока устраивать любой из них". 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. Time limit was reduced to 1 second also. All ACs will be rejudged soon. 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 Is there any trick in test #5? In test#4 N=20, but it should be less than 20 ("N<20" in both - english and russian - texts). |
|
|