Discussion @ 1079. Maximum @ Timus Online Judge

I've got an AC with 0.031sec and 111Kb!

Posted by Anton Chupin 19 Feb 2005 17:51

Who can better? My solution has O(logn*logn). Fairly it wasn't my solution. I read about one property of that function. And I know that exist more efficient solution.

If your solution is O(logN*logN) than why it works slower than O(N)?

Posted by Vlad Veselov [PMG17,Vinnitsa - KNU,Kiev] 21 Feb 2005 17:13

764867 17:11:45
21 фев 2005 TECTOBOP 1079 Pascal Accepted
0.015 959 КБ

764865 17:10:33
21 фев 2005 TECTOBOP 1079 Pascal Accepted
959 КБ

If your solution is O(logN*logN) than why it works slower than O(N)?

Posted by Hard ( DHSP ) 22 Jun 2005 21:32

I think you have lowered your complexity !
You can check your algorithm ! Is it exactly O(LogN*LogN) ?
See: 866045 Hard (DHSP) 1079 Pascal Accepted 0.001 505 KB

Edited by author 22.06.2005 21:33

Edited by author 22.06.2005 21:33

Idea

Posted by Anton Chupin 5 Apr 2007 21:34

Assume g(n,i,j)=i*f(n)+j*f(n+1).
Then
g(2n,i,j)=g(n,i+j,j)
g(2n+1,i,j)=g(n,i,i+j)
We must find f(n)=g(n,1,0), so...

Answer

Posted by Anton Chupin 5 Apr 2007 21:37

If your solution is O(logN*logN) than why it works slower than O(N)?

Are you sure that accuracy of time measuring is higher than centisecond?

It is. But result may vary time to time, submit it 5-10 times and get the lowest one :) (-)

Posted by Orlangur [KievNU] 5 Apr 2007 23:45

Re: It is. But result may vary time to time, submit it 5-10 times and get the lowest one :) (-)

Posted by Alias (Alexander Prudaev) 6 Apr 2007 10:21

try to solve 1396
it is the same problem, but 0 < N < 10^18

Re: It is. But result may vary time to time, submit it 5-10 times and get the lowest one :) (-)

Posted by timur 28 Jul 2007 01:56

I jave O(log n) solution! 0.015s 331k!

Re: It is. But result may vary time to time, submit it 5-10 times and get the lowest one :) (-)

Posted by timur 28 Jul 2007 04:07

now I have 0.001s!

Discussion of Problem 1079. Maximum