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

Обсуждение задачи 1777. Племя аниндилъяква

Explanation of the worst case and the idea for solution.
Послано grinrag 1 окт 2019 13:54
We have got 3 distinct number, A < B < C.
Let's imagine that the minimum difference Z = (C - B) goes between numbers A and B, closer to B, so new sequence will be A < Z < B < C. And the next minimum difference Y = (B - Z), goes between A and Z, closer to Z, A < Y < Z < B < C and so on.
You see Y + Z = B, Z + B = C, the next number in the sequence (in order from left to right) is equal to the sum of current and previous members (looks like Fibonacci numbers).
Now try to find the sequence with described property.

Look at the example: 1 4 6 10 16 26 ... We can continue this sequence until the last two members will be 519390993822245170 and 840392281454979346. Their sum is more than 10^18. It takes only 83 iterations to build this sequence.

The test case would be: 1 519390993822245170 840392281454979346

So, in the worst case, the number of iteration N < 100.

The naive algorithm, when we just put the minimum diff to the array and sort it again will work. The time complexity will be O(N^2 log N).

Edited by author 01.10.2019 14:24