I've solved 1079,but this problem...Is any trick there?

Edited by author 01.09.2007 22:19

I think, the only trick here - to have creative brains :)

I thihk that unhelpful to wait when creativeness
come to us. That it should try to solve as can.
For exampple, let n to be strong number if
a[n]>max(0<=i<=n-1) a[i]. It is evidence that having strong numbers precalculated and if their number rather small
then the problem will be solved easily.
This is list of strong numbers in 1000:
3 1 1
5 1 0 1
9 1 0 0 1
11 1 0 1 1
19 1 0 0 1 1
21 1 0 1 0 1
35 1 0 0 0 1 1
37 1 0 0 1 0 1
43 1 0 1 0 1 1
69 1 0 0 0 1 0 1
73 1 0 0 1 0 0 1
75 1 0 0 1 0 1 1
83 1 0 1 0 0 1 1
85 1 0 1 0 1 0 1
139 1 0 0 0 1 0 1 1
147 1 0 0 1 0 0 1 1
149 1 0 0 1 0 1 0 1
165 1 0 1 0 0 1 0 1
171 1 0 1 0 1 0 1 1
277 1 0 0 0 1 0 1 0 1
293 1 0 0 1 0 0 1 0 1
299 1 0 0 1 0 1 0 1 1
331 1 0 1 0 0 1 0 1 1
339 1 0 1 0 1 0 0 1 1
341 1 0 1 0 1 0 1 0 1
555 1 0 0 0 1 0 1 0 1 1
587 1 0 0 1 0 0 1 0 1 1
595 1 0 0 1 0 1 0 0 1 1
597 1 0 0 1 0 1 0 1 0 1
661 1 0 1 0 0 1 0 1 0 1
683 1 0 1 0 1 0 1 0 1 1
If you can find algo for their generation you will winner.
Now I can't.
But it,s evident for me that for their binary expansions
fulfil next lows:
1) numbers of  0 and 1 are equal or with difference 1;
2) 1 and 0 alternates exept for last two 1.
I can generate such number sets combinatorically
ang strong numbers will be among them.
By the way, number of strong numbers really very small/
For example, until 200000 thei number is 114.

Edited by author 20.09.2007 12:08

I also noticed this feature (and even some more strong), but it didn't help me to solve the problem...

Thank you for your help!I'll think about it.Now with your help I've idea.Ostalnoe,po-moemu,delo tehniki.

Edited by author 20.09.2007 18:42

It's quite easy to see the pattern. It's a bit different for odd and even number of digits (excluding leading zeroes), but there IS a pattern, and it's quite simple to program. If you still can't find the pattern inside base-2 representation (I could do that), write it base-4 - it's more evident there and easier to code.

Even if you cannot find strict pattern, you may find some weaker pattern which includes all of strong indices and probably some more. Of course, this will lead to O(log^2(N)) solution because you will have to test each of such indexes as you don't know which of them is actually a strong one, but still it should be AC. My algo generates strong indices ONLY, and it does so only for N/2..N interval. The biggest goes to the answer. N<65536 are brute-forced special cases (too few digits).

Yes I found the pattern in binary and got AC (0.078, 140KB) (no precompute), for strong indices only, and only generate them starting with 2^(floor(log2(n))).   The pattern holds lower than 65536 so you can set the brute force threshold lower for faster execution time.    (I have a special case for finding the maximum if it occurs below my starting point).

This has been a fascinating problem to solve, thank you to the authors.


Edited by author 20.09.2012 23:38