|
|
back to boardI've got an AC with 0.031sec and 111Kb! 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)? 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)? 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 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 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 :) (-) Re: It is. But result may vary time to time, submit it 5-10 times and get the lowest one :) (-) 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! |
|
|