Why does this solution work?

Revision en1, by emorgan, 2020-06-23 21:15:27

This concerns the following problem: 680D - Bear and Tower of Cubes. Here's a rough outline of my thoughts while solving this problem.

Let $$$f(m, x)$$$ be the optimal number of boxes (we can ignore the part about maximizing $$$X$$$, it's trivial to extend the solution to also accomplish this) for input $$$m$$$, where we are only allowed to use boxes of length at most $$$x$$$. The answer to the original problem is $$$f(m, 10^5)$$$, we have the base case $$$f(m, 0)=0$$$, and $$$f$$$ satisfies the recurrence

$$$ f(m, x) = \max\begin{cases} f(m-x^3, x)+1 & \text{if we take a cube of length $$$x$$$} \\ f(\min(m, x^3-1), x-1) & \text{if we don't} \\ \end{cases} $$$

Evaluating $$$f(m, x)$$$ with DP is too slow for large $$$m$$$, but we can make the observation that for each pair $$$(m, x)$$$, it is either optimal to take a cube or not to take a cube, and that if it is optimal to take for $$$(m, x)$$$, then it must also be optimal to take for $$$(m+1, x)$$$. I don't have a rigorous proof for this, but it is intuitively true and AC submission confirms this. So, we can binary search on the "turning point" $$$p_x$$$ such that it is optimal to take for all $$$m\geq p_x$$$, and optimal not to take for all $$$m<p_x$$$. This yields a correct solution, but still gets TLE for large $$$m$$$.

The next observation is that since we only care about $$$x\leq 10^5$$$, we could theoretically precompute all $$$10^5$$$ values of $$$p_x$$$, which would yield a fast greedy solution. $$$10^5$$$ is a little too large for a precomputed table of long longs so this isn't really feasible. However, while computing these values, I noticed some patterns in the values of $$$p_x$$$, and began investigating various properties of the sequence, and I eventually decided to look at the sequence of $$$p_x-x^3$$$, which displayed some really weird behavior. Basically, for $$$x$$$ from $$$1$$$ to $$$10^5$$$ it only took on $$$12$$$ distinct values, which were non-decreasing. The sequence looked like

$$$ 0, 6, 15, 23, 50, 50, 114, 114, 114, 114, 330, ..., 1330, ..., 10591, ..., 215970, ..., 19464802, ..., 16542386125 $$$

Where the later values were repeated many times. And so, I managed to use these values to encode all of the values of $$$p_x$$$, in order to get an AC submission for the problem: 84824995.

So, the obvious question here is, why does this work? I have no idea where this pattern is coming from.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English emorgan 2020-06-23 21:15:27 2345 Initial revision (published)