emorgan's blog

By emorgan, history, 4 years ago, In English

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.

  • Vote: I like it
  • +18
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

tl; dr: I don't know, why you get exactly this numbers, but I know, why a lot of them are same.

Let $$$cnt(m, x)$$$ be the number of boxes needed to get exactly $$$m$$$ where we can use only boxes of size at most $$$x$$$. Let $$$cnt(m) = cnt(m, \infty)$$$. So, $$$f(m, x) = \max\limits_{1 \leqslant n \leqslant m} cnt(n, x)$$$. Now, $$$cnt(m, x) = cnt(m)$$$ for $$$m < x^3$$$ and $$$cnt(m, x) = cnt(m - x^3, x) + 1$$$ for $$$m \geqslant x^3$$$.

If $$$f(m,x) = cnt(m,x)$$$ then it means that we can use $$$m$$$ to get the optimal answer. (Notice, that you can replace can with must and it will result in a bit different numbers, but I will use can, because these numbers are your numbers. In other words, it is a difference between strict and non-strict comparison). From equations above it can be seen that there exists $$$m \in [x^3, 2x^3)$$$ such that $$$f(m,x) > f(m-1,x)$$$. For that $$$m$$$ it is obvious, that $$$f(m,x) = cnt(m,x)$$$. So, there always exists at least one $$$m \in [x^2, 2x^3)$$$ such that $$$f(m,x) = cnt(m,x)$$$. And the smallest of these is $$$p_x$$$.

$$$p_x > x^3$$$ (at least for $$$x>1$$$), because $$$cnt(x^3,x) = 1$$$ (can't be the maximum).

Take any $$$n \in [x^3, p_x-1]$$$. Now, there are two options. If $$$f(p_x, x) > f(n, x)$$$, then

\begin{gather*} cnt(p_x, x) > f(n, x) = \max\limits_{1 \leqslant i \leqslant n}cnt(i, x) \geqslant cnt(n, x) \end{gather*}

So, $$$cnt(p_x, x) > cnt(n, x)$$$ or $$$cnt(p_x - x^3) > cnt(n - x^3)$$$.

The second option is that $$$f(p_x, x) = f(n, x)$$$. If $$$cnt(p_x, x) \leqslant cnt(n, x)$$$, then

\begin{gather*} f(n, x) = f(p_x, x) = cnt(p_x, x) \leqslant cnt(n, x) \Rightarrow f(n, x) = cnt(n, x) \end{gather*}

That means that $$$p_x$$$ is not the smallest with needed conditions, and it is condradiction.

Now we have that for any $$$n \in [x^3, p_x - 1]$$$: $$$cnt(p_x - x^3) > cnt(n - x^3)$$$. That is, for every $$$n < p_x - x^3$$$: $$$cnt(p_x - x^3) > cnt(n)$$$.

Now, what about maximum possible value for $$$cnt(m)$$$ if $$$m \leqslant 10^{15}$$$? You can cheat and look in the testcases and get that it is $$$18$$$ (the answer for maximum $$$m$$$). Without cheating, you can see that for numbers up to $$$x^3$$$ the biggest difference between cubes is $$$x^3 - (x-1)^3 \approx 3x^2$$$, so you will get no more than $$$\sim 3m^{2/3}$$$ after first subtraction from $$$m$$$. And after applying $$$20$$$ of these operations to $$$10^{15}$$$ you will get something around $$$27$$$, and the answer for that is no more than $$$10$$$.

Anyway, the biggest possible value for $$$cnt$$$ is $$$18$$$, so there are at most $$$18$$$ values of $$$t$$$, for which $$$cnt(t) > cnt(n)$$$ $$$\forall n < t$$$. And $$$t = p_x - x^3$$$. You got 12 values, not 18, but it's not much of a difference. I suppose.