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 1396. Maximum. Version 2

Yeah! Some hints
Posted by Blum 21 Aug 2008 00:54
With help of my friend that was just looking at maximums index sequense and found an idea, finally, I got AC.
Some hints:
1) Find an idea to calculate next maximum indices from previous ones: all the maximum's indices can be obtained from previous ones in such ways:
i = s*2 + 1; or
i = s*2 - 1; or
i = s*4 + 1; or
i = s*4 - 1;

for example f(21)=8 is maximum for 21<=n<=34
so 21 = 2*11-1, where 11 is one of previous maximums indices. And so on using all the formulas above.
but 2*11+1 = 23 is not a maximum index. so we have to cancel  this number (23).
2) Learn to calculate f(n) in O(logn)
3) Generate all maximums indices (about 1500). You can store them in heap to get an access to the smallest maximum index.
4) than read n and just search for it in maximums index array.
P.S. who can prove the first and the main idea? If you can, please post here you proof.
Why
Posted by OZone3 5 Jul 2009 21:07
How did you invent it?

Edited by author 05.07.2009 22:51
Re: Yeah! Some hints
Posted by riteme 15 Oct 2016 08:23
It seems that only test s*2 - 1 and s*4 - 1 is OK.
I've tested by bruteforce program in range [0, 20000000].
I will try it.

Edited by author 15.10.2016 08:24
Re: Yeah! Some hints
Posted by alexwangxiang 18 Sep 2022 06:08
This is exactly how my accepted program runs. Suppose i is a maximum index, i = 2*i1+1, i2 = i1+1, then either 1) i1 is even, at least one of i1/2, i2 is a maximum index; or 2) i2 is even, at least one of i2/2, i1 is a maximum index. But I don't know how to prove it. Thus candidate indices from 2^n to 2^{n+1} can be generated from calculated maximum indices from 2^{n-2} to 2^n.