EXPRIZE - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: am_aadvik
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Binary search

PROBLEM:

Given N, find the largest integer K such that there exists a sequence (a_1, \ldots, a_K) satisfying:

  • 1 \le a_1 \lt a_2 \lt\ldots\lt a_K
  • a_1 + \ldots + a_K = N
  • a_{i+1} - a_{i} \ge i for each 1 \le i \lt K

EXPLANATION:

Let’s fix a length K and see what a valid sequence might look like.

First, every element needs to be positive. So, we definitely need a_1 to be at least 1.
Let’s fix a_1 = 1 for now.

Next, a_2 must satisfy a_2 - a_1 \ge 1, so a_2 \ge 1+1 = 2.
The minimal valid value for a_2 is hence 2.

Similarly, a_3 - a_2 \ge 2 \implies a_2 \ge a_2 + 2, so the minimal valid value for a_3 is 2+2 = 4.

In general, it can be observed that for any i \gt 1, a_i must be at least

1 + 1 + 2 + \ldots + i-1 = 1 + \frac{i\cdot (i-1)}{2}

because the first value is 1 and then all the adjacent difference lower bounds so far add up.

Let’s define L_i = 1 + \frac{i\cdot (i-1)}{2}.


Now, suppose we’ve found an arbitrary valid sequence (a_1, \ldots, a_K) whose sum is N.
We’ll attempt to reduce this to a “canonical” sequence that’s easier to reason about.

First, note that if a_1 \gt 1, then we can always reduce a_1 to 1 and increase a_K by the same amount.
This keeps the sum the same, and only increases adjacent differences; so difference conditions still hold.

After doing this, if a_2 \gt a_1+1 = 2, we can again reduce a_2 to 2 and increase a_K by the same amount.
Then, if a_3 \gt a_2 + 2 = 4, we can reduce it to 4 and increase a_K, and so on.

In general, for every 1 \le i \lt K, if a_i is larger than L_i we can then reduce it to L_i and increment a_K by the corresponding amount instead.

Thus, if a valid sequence of length K exists, we’ll also have a sequence of the form

L_1, L_2, \ldots, L_{K-1}, (L_K + x)

where x \ge 0

This is nice, because L_1, \ldots, L_{K} are constants and hence easy to reason about.


In particular, observe that if we fix the length K, it’s possible to find the sum L_1 + \ldots + L_{K} in constant time using some algebra.

This is because we’re looking to compute

\sum_{i=1}^K\left(1 + \frac{i\cdot (i-1)}{2}\right) = K + \sum_{i=1}^K \left(\frac{i^2 - i}{2}\right)

This can be done using the identities:

1 + 2 + \ldots + i = \frac{i\cdot (i-1)}{2}

and

1^2 + 2^2 + \ldots + i^2 = \frac{i\cdot (i+1) \cdot (2i+1)}{6}

Applying these two identities, and reducing terms a bit, it can be seem that the sum L_1 + \ldots + L_K reduces to

\frac{K^3 + 5K}{6}

Now, if this value is \le N then we can simply add any extra to the last element to obtain a sum of exactly N, whereas if it’s already larger than N then nothing can be done.

Our aim is hence to find the largest K such that \frac{K^3 + 5K}{6} \le N.

Since the function of K is monotonically increasing with K, the largest valid value of K can be computed in \mathcal{O}(\log N) using binary search.

When choosing limits, be careful that K^3 + 5K doesn’t exceed the limits of whatever data type you’re using.
This applies particularly to languages like C++, where the limit of a 64-bit signed integer is just a bit less than 10^{19}.

TIME COMPLEXITY:

\mathcal{O}(\log N) per testcase.

CODE:

Editorialist's code (PyPy3)
for _ in range(int(input())):
    n = int(input())
    
    lo, hi = 1, 10**7
    while lo < hi:
        mid = (lo + hi + 1)//2
        if mid**3 + 5*mid <= 6*n: lo = mid
        else: hi = mid-1
    print(lo)