A - Floor, Ceil - Decomposition Editorial by evima
We use the following notations in this editorial.
For a positive integer \(X\), let \(f(x)\) be the maximum possible final product when starting with one \(X\) written on the blackboard. - Let \(X_- = \lfloor X/2\rfloor\) and \(X_+ = \lceil X/2\rceil\).
[1] Recurrence relation for \(f(X)\)
We have the following:
- \(f(1) = 1\)
- \(f(X) = \max\{X, f(X_-)f(X_+)\}\) (for \(X\geq 2\))
Actually, the sought value is the greater of the following two.
- When doing zero operations: the final product is \(X\).
- When doing one or more operations: the first operation changes the state of the blackboard to \((X_-, X_+)\). Then, it is optimal to individually handle \(X_-\) and \(X_+\) for the maximum product, after which the final product is \(f(X_-)f(X_+)\).
Additionally, by considering which is larger in \(f(X) = \max\{X, f(X_-)f(X_+)\}\), we can see that the following holds:
- \(f(X) = X\) (for \(X\leq 4\))
- \(f(X) = f(X_-)f(X_+)\) (for \(5\leq X\))
For \(X\leq 4\), this can be seen by actually calculating the values of \(f(X)\) using the reccurrence relation \(f(X) = \max\{X, f(X_-)f(X_+)\}\). For \(5\leq X\), it follows from
\[f(X_-)f(X_+) \geq X_-X_+ \geq \frac{X-1}{2}\cdot \frac{X}{2} = \frac{X-1}{4}\cdot X\geq X\]
that \(f(X_-)f(X_+)\geq X\).
[2] Algorithm and complexity analysis
We use the recurrence relation in [1] to compute the values \(f(X)\) recursively. This can be done efficiently by memoized recursion, reusing the values of \(f(X)\) computed once.
- Sample Code (Python):https://atcoder.jp/contests/arc135/submissions/29019824
- Sample Code (C++):https://atcoder.jp/contests/arc135/submissions/29019934
During the computation of \(f(X)\), we have to compute \(f(x)\) for several smaller values of \(x\). Here, only the values that can be represented as \(\lfloor X/2^k\rfloor\) or \(\lceil X/2^k\rceil\) for some \(k\) appear as \(x\). (We can prove in the order \(k = 0, 1, 2, \ldots\) that this is true for the \(k\)-th recursion.)
Thus, if we choose \(K\) so that \(2^{K-1}\leq X < 2^{K}\), there are at most \(2K\) values of \(f(x)\) to compute, allowing us to solve the problem in \(\Theta(\log X)\) time (or \(\Theta(\log X \log\log X)\) time, depending on the method of memoization).
posted:
last update: