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

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

posted:
last update: