ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1396. Максимум. Версия 2

Yeah! Some hints
Послано Blum 21 авг 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
Послано OZone3 5 июл 2009 21:07
How did you invent it?

Edited by author 05.07.2009 22:51
Re: Yeah! Some hints
Послано riteme 15 окт 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
Послано alexwangxiang 18 сен 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.