ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1777. Anindilyakwa

Explanation of the worst case and the idea for solution.
Posted by grinrag 1 Oct 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