## Editorial for Cheerio Contest 3 P3 - Everything Array

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: rickyqin005

Observation

Using the numbers , we can make the numbers . For the remainder of this editorial, let represent the list of numbers from to (inclusive).

Instead of using , what happens when we have , , etc.?

Suppose we have the numbers . We can make the numbers and but we cannot make the numbers . This is because the largest possible difference is and the smallest possible sum is . We can fill in this gap by extending the array to , which now covers the numbers .

Expressing in terms of , we have an optimal value of . This results in a length of , which approaches for large values of . To satisfy the length requirement for smaller values of , we can remove the middle two array elements while still being able to construct all the numbers. This works for , which is always true for .

Time Complexity:

What could the square root in imply? Also think about multiples.