ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1079. Maximum

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!