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