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
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
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
This can be done using the identities:
and
Applying these two identities, and reducing terms a bit, it can be seem that the sum L_1 + \ldots + L_K reduces to
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)