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

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

Mine is O(C(K,5000))

Yes it's just ~10^50 operations
It's easy for Timus supercomputers:)

But I don't know all details but shortly
It can be said that we haven't an algorithm
but have Ac-prog.

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

This is fine information.
Or the problem is not NP type and therefore
must be understood and solved

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

Also solved ... 0.001 Brute force ...

Very strange problem.
i don't like such problems ...

AC in Java 0.093.

Complexity O(n*m*20).