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


Using the numbers 1, 2, 3, \dots, k, we can make the numbers 1, 2, 3, \dots, 2k-1. For the remainder of this editorial, let [a, b] represent the list of numbers from a to b (inclusive).

Subtask 1

Instead of using [1, k], what happens when we have [2, k+1], [3, k+2], etc.?

Suppose we have the numbers [k, 2k-1]. We can make the numbers [1, k-1] and [2k+1, 4k-3] but we cannot make the numbers [k, 2k]. This is because the largest possible difference is k-1 and the smallest possible sum is 2k+1. We can fill in this gap by extending the array to [k, 3k], which now covers the numbers [1, 6k-1].

Expressing in terms of N, we have an optimal value of k = \left\lceil\dfrac{N+1}{6}\right\rceil. This results in a length of 2k+1 = 2\left\lceil\dfrac{N+1}{6}\right\rceil+1, which approaches \dfrac{1}{3}N for large values of N. To satisfy the length requirement for smaller values of N, we can remove the middle two array elements while still being able to construct all the numbers. This works for k \ge 4, which is always true for N \ge 18.

Time Complexity: \mathcal{O}(N)
Hint for Subtask 2

What could the square root in \sqrt{2N} imply? Also think about multiples.

Subtask 2

Let's reconsider the numbers [1, k]. Notice that if we have some other number p, we can make the numbers [p-k, p+k] except for p itself. Thus, we can try adding numbers so that the range of numbers each can produce covers the range [2k, N]. The intended solution is to use multiples of 2k+1 as this covers all the numbers up to N and the number 2k+1 can be used to make the multiples themselves. This requires an array length of k+\left\lceil\dfrac{N-k}{2k+1}\right\rceil and we can loop through all values of k to find the one that results in the minimum length.

Time Complexity: \mathcal{O}(N)

Using calculus, we can determine the optimal value of k and the minimum length it produces in \mathcal{O}(1) time. It turns out the minimum length is \left\lceil\sqrt{2N+1}\right\rceil-1, which can be proven to never exceed \lfloor\sqrt{2N}\rfloor.


There are no comments at the moment.