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.

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).

last update: