ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1541. Chase

Simple recursive algo get AC. Good Luck!
Posted by Victor Barinov (TNU) 4 Mar 2007 19:41
Re: Simple recursive algo get AC. Good Luck!
Posted by Vedernikoff Sergey 6 Mar 2007 11:03
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!
Posted by Vedernikoff Sergey 6 Mar 2007 19:54
Mine is O(C(K,5000))
Re: Simple recursive algo get AC. Good Luck!
Posted by KIRILL(ArcSTU) 6 Mar 2007 20:25
Vedernikoff Sergey wrote 6 March 2007 19:54
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!
Posted by Vedernikoff Sergey 7 Mar 2007 09:30
KIRILL(ArcSTU) wrote 6 March 2007 20:25
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!
Posted by Chmel_Tolstiy 2 Mar 2008 03:15
Also solved ... 0.001 Brute force ...

Very strange problem.
i don't like such problems ...
Re: Simple recursive algo get AC. Good Luck!
Posted by Alex Tolstov (Vologda STU) 11 May 2009 17:29
AC in Java 0.093.

Complexity O(n*m*20).