## Editorial for Cheerio Contest 3 P3 - Everything Array

**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:

## Observation

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

## Subtask 1

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:**

## Hint for Subtask 2

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

## Subtask 2

Let's reconsider the numbers . Notice that if we have some other number , we can make the numbers except for itself. Thus, we can try adding numbers so that the range of numbers each can produce covers the range . The intended solution is to use multiples of as this covers all the numbers up to and the number can be used to make the multiples themselves. This requires an array length of and we can loop through all values of to find the one that results in the minimum length.

**Time Complexity:**

## Bonus

Using calculus, we can determine the optimal value of and the minimum length it produces in time. It turns out the minimum length is , which can be proven to never exceed .

## Comments