Contest Duration: - (local time) (120 minutes) Back to Home
Official

E - Sequence of Multiples Editorial by evima

Below, we assume that $$A$$ is an optimal sequence, where $$A_i$$ is the smallest multiple of $$i$$ greater than $$A_{i-1}$$ for $$i\geq 2$$.

[1] A solution in $$O(X^{1/2})$$ time

We first explain an $$O(X^{1/2})$$ solution (which is expected to get TLE).

Let a sequence $$B$$ defined by $$B_i = A_i / i$$. We have $$B_{i+1} = \lfloor\frac{iB_i}{i+1}\rfloor + 1 = B_{i} + 1 - \lceil\frac{B_i}{i+1}\rceil$$.

It is easy to see the following:

• $$B_i$$ is non-increasing
• $$B_{i+1} = B_i$$ if $$B_i < i$$

Since $$B_i$$ is non-increasing, there is $$n$$ such that $$B_n < n$$. Afterward, it is a constant sequence, where the sum can be computed altogether. Thus, the problem can be solved by computing the sequence $$B$$ until $$B_n < n$$ holds.

Let us evaluate the complexity of this solution, that is, the size of $$n$$ such that $$B_n < n$$. If we roughly consider that $$B_{i+1}$$ and $$\frac{iB_i}{i+1}$$ are close enough, that is, $$iB_i$$ is almost a constant, it seems probable that $$B_n < n$$. A more detailed argument can, for example, prove the following:

• $$B_i < \frac{X}{i} + i$$ for every $$i$$.

Specifically, if we let $$m = \lceil \sqrt{X} \rceil$$, we have $$B_m < \frac{X}{m} + m \leq 2m$$, and it follows from $$B_{2m} \leq B_m < 2m$$ that $$B_n < n$$ for $$n = 2m = 2\lceil \sqrt{X} \rceil$$. Especially, the time complexity of the solution above is $$O(X^{1/2})$$.

[2] A solution in $$O(X^{1/3})$$ time

Let us try to put together some computations in [1].

Since $$B_i - B_{i+1} = \lceil \frac{B_i}{i+1}\rceil - 1$$ and $$B$$ is non-increasing, it can be seen that the following holds:

• $$B_1 - B_2 \geq B_2 - B_3\geq \cdots$$

Let us deal with $$B_n, \ldots, B_{m-1}$$ where $$B_n - B_{n+1} = \cdots = B_{m-1} - B_m$$ holds altogether.

For a given $$n$$, the range of $$i$$ where $$B_n - B_{n+1} = B_i - B_{i+1}$$ holds can be found in $$O(1)$$ time. Additionally, $$\sum_{i=n}^{m-1} iB_i$$ can be found in $$O(1)$$ time, too (by using formulae such as $$\sum_{k=0}^{n-1}k^2=\frac{1}{6}(n-1)n(2n-1)$$, or polynomial interpolation, etc).

In the end, if $$B_i - B_{i+1}$$ takes $$n$$ different values, the problem can be solved in $$O(n)$$ time.

Below is a proof that $$B_i - B_{i+1}$$ takes $$O(X^{1/3})$$ different values.

• Let $$n = \lceil X^{1/3}\rceil$$. Then, from the evaluations in [1], we have $$B_n < X^{2/3} + n$$.
• Thus, we have $$B_n - B_{n+1} = \lceil \frac{B_n}{n+1}-1\rceil \leq \lceil \frac{X^{2/3}}{n+1}\rceil\leq n$$.
• There are at most $$n-1$$ different values among $$B_1 - B_2, \ldots, B_{n-1} - B_{n}$$, and at most $$n+1$$ different values after $$B_n - B_{n+1}$$ (because they are among $$0, 1, \ldots, n$$).
• Therefore, $$B_i - B_{i+1}$$ takes at most $$2n = 2 \lceil X^{1/3}\rceil$$ different values.

posted:
last update: