Simple recursive algo get AC. Good Luck!

Re: Simple recursive algo get AC. Good Luck!

Yes, my stupid bruteforce algo got AC within 0.2 secs. Funny!

Re: Simple recursive algo get AC. Good Luck!

Posted by

svr 6 Mar 2007 11:16

In this situaton great interst has

a proven right algorithm with garantee result

on all posiible tests in described ranges

For me it much more valuable than fact of AC

P.S. What comlexity of brute force?

~(100000)^K*K?

*Edited by author 06.03.2007 11:46*

*Edited by author 06.03.2007 11:46*

*Edited by author 06.03.2007 11:47*

Re: Simple recursive algo get AC. Good Luck!

Mine is O(C(K,5000))

Re: Simple recursive algo get AC. Good Luck!

Mine is O(C(K,5000))

Yes it's just ~10^50 operations

It's easy for Timus supercomputers:)

Re: Simple recursive algo get AC. Good Luck!

Posted by

svr 6 Mar 2007 20:38

But I don't know all details but shortly

It can be said that we haven't an algorithm

but have Ac-prog.

Re: Simple recursive algo get AC. Good Luck!

Yes it's just ~10^50 operations

It's easy for Timus supercomputers:)

Quicksort time estimate is also O(N^2), but really - O(NlogN). My algo with asympthotic time O(C(K,5000)) in worst case makes about 10^7 operations, that is acceptable.

*Edited by author 07.03.2007 09:30*Re: Simple recursive algo get AC. Good Luck!

Posted by

svr 7 Mar 2007 09:39

This is fine information.

Or the problem is not NP type and therefore

must be understood and solved

Re: Simple recursive algo get AC. Good Luck!

Posted by

svr 8 Jul 2007 15:48

Also solved now.

I used double for fractions ,eps=1e-11 for comparisons(1e-10 gives WA),prepocessing for numbers 1/i and it's sums,

stac instead of recursion in full search,

NN=5000 as upper bound for Vi(value NN=350 couldn't verify because of TLE) and finally had 0,593c. AC.

I think that times 0.001 adjust to tests list only.

*Edited by author 08.07.2007 15:51*

Re: Simple recursive algo get AC. Good Luck!

Also solved ... 0.001 Brute force ...

Very strange problem.

i don't like such problems ...

Re: Simple recursive algo get AC. Good Luck!

AC in Java 0.093.

Complexity O(n*m*20).