Hello. I can't seem to figure out this problem's solution. I've read the editorial and I understand the first part but when the author says:
"To further optimize this solution, another transformation is needed. Ideally, we would like each ai to contribute to the answer independently of other values. And this can almost be achieved. Notice that the maximum returns 0 only if ai<ai−1 for any k, not just for k=1. This may require proof, but it is quite obvious."
I just don't get what this means. I also don't know what he's tryna do with the ci coefficient. I'd really appreciate it if someone here could explain it to me.
In second option (last paragraph of editorial) $$$c_i$$$ is similar to what I did in my solution: https://codeforces.me/blog/entry/128421?#comment-1140048 but from slightly different angle.
dang that's a pretty unique solution
After much deliberation, I finally figured it out. I learned a lot too. I am going to write down what I have learned so that I can reference it if I ever need to. Maybe someone else might find it helpful too.
Let’s set $$$k = 1$$$ just for now to make everything more simple. We know that the answer for $$$k = 1$$$ is given by the expression $$$a_1 + max(a_2 - a_1, 0) + max(a_3 - a_2, 0) … + max(a_n - a_{n-1}, 0).$$$ The editorial does a good job in explaining this in my opinion. Instead of writing the answer in this form, though, what if we tried to make each $$$a_i$$$ independent of one another? In other words, we want to express the answer as $$$c_1 \cdot a_1 + c_2 \cdot a_2 + … + c_n \cdot a_n$$$ where each $$$c_i$$$ is some coefficient. Let’s see how we can do this:
Let’s solve it for an array of length $$$2.$$$
The current expression is $$$a_1 + max(a_2 - a_1, 0).$$$
Let’s define an array coefficients = $$$[0, 0]$$$ where $$$coefficients_i =$$$ the coefficient of $$$a_i.$$$
We know that we have $$$a_1$$$ isolated in the current expression. So we can set $$$coefficients_1 = 1.$$$
But how do we deal with the $$$max(a_2 - a_1, 0)$$$ case?
Let’s assume that $$$a_2 - a_1 > 0.$$$ Well then the $$$max(a_2 - a_1, 0) = a_2 - a_1.$$$ So the expression becomes $$$a_1 + a_2 - a_1.$$$ It can be seen that when $$$a_2 - a_1 > 0,$$$ we add one to $$$coefficients_2$$$ and we subtract one from $$$coefficients_1.$$$ Our coefficients array will then be $$$[0, 1],$$$ and our answer will be $$$c_1 * a_1 + c_2 * a_2,$$$ or just $$$a_2.$$$
What happens when $$$a_2 - a_1 < 0$$$? Well then $$$max(a_2 - a_1, 0) = 0$$$ and our expression will just be $$$a_1 + 0.$$$ Notice that this does not change our original coefficients array at all so we don’t actually have to change any coefficients. The answer is just $$$a_1.$$$
What about when $$$a_2 - a_1 == 0$$$? Well in this case, we can either not change our coefficients or add one to $$$coefficients_2$$$ and subtract one from $$$coefficients_1.$$$ Since $$$a_2 == a_1,$$$ these operations are equivalent.
We can do this for all of the $$$max(a_{i + 1} - a_i, 0)$$$ values, adding and subtracting from coefficients when necessary.
Code might look something like this:
And we have solved the problem independently for each $$$a_i$$$ when $$$k = 1.$$$
What about when $$$k \ne 1$$$? Does it affect our coefficients? $$$k$$$ changes our $$$a_i$$$ to $$$\lceil \frac{a_i}{k} \rceil$$$ so it must affect $$$max(a_{i + 1} - a_i, 0)$$$ and thus coefficients, right?
No. There are two cases
Case 1: changing all $$$a_i$$$ to $$$\lceil \frac{a_i}{k} \rceil$$$ does not change the relative size of all $$$a_i.$$$ In other words, for all $$$i < n,$$$ if $$$a_{i + 1} > a_i,$$$ then $$$\lceil \frac{a_{i + 1}}{k} \rceil > \lceil \frac{a_i}{k} \rceil,$$$ and if $$$a_{i + 1} < a_i,$$$ then $$$\lceil \frac{a_{i + 1}}{k} \rceil < \lceil \frac{a_i}{k} \rceil.$$$ This doesn’t affect the answer because the coefficients are made based on the relative size of each $$$a_i,$$$ not the absolute size. Like if $$$a_{i + 1} > a_i,$$$ then we are adding $$$1$$$ to $$$c_{i + 1}$$$ and subtracting $$$1$$$ from $$$c_i$$$ no matter the size of $$$a_{i + 1}$$$ and $$$a_i.$$$
Case 2: Changing all $$$a_i$$$ to $$$\lceil \frac{a_i}{k} \rceil$$$ changes the relative size of some $$$a_i.$$$ In other words, for some $$$i,$$$ if $$$a_{i + 1} > a_i,$$$ then $$$\lceil \frac{a_{i + 1}}{k} \rceil = \lceil \frac{a_i}{k} \rceil$$$ or if $$$a_{i + 1} < a_i$$$ then $$$\lceil \frac{a_{i + 1}}{k} \rceil = \lceil \frac{a_i}{k} \rceil$$$ (notice that if $$$a_{i + 1} > a_i,$$$ we can never have $$$\lceil \frac{a_{i + 1}}{k} \rceil < \lceil \frac{a_i}{k} \rceil.$$$ But we see that, in either of these cases, when we originally processed the $$$max(a_{i + 1} - a_i, 0), coefficients_{i + 1}$$$ got the same number of $$$1$$$ additions as $$$coefficients_i$$$ got $$$1$$$ subtractions (that is, either $$$coefficients_{i + 1} += 1$$$ and $$$coefficients_i -= 1,$$$ or they remained unchanged). Since $$$\lceil \frac{a_{i + 1}}{k} \rceil = \lceil \frac{a_i}{k} \rceil,$$$ the coefficients do not matter since they “balance” each other out.
So coefficients doesn’t just work for $$$k = 1,$$$ it works for all $$$k.$$$
The editorial makes it clear why there are only up to $$$2\sqrt{a_i}$$$ possible $$$\lceil \frac{a_i}{k} \rceil$$$ values for every $$$a_i.$$$ So, using this fact, for each $$$a_i,$$$ we can find the ranges of $$$k$$$ that make $$$\lceil \frac{a_i}{k} \rceil$$$ equal to the same value. For a specific value $$$x,$$$ say $$$L$$$ is the lower bound of the $$$k$$$ range and $$$R$$$ is one above the upper bound. We can just use a difference array called $$$ans$$$ and do $$$ans_L += c_i \cdot x$$$ and $$$ans_R -= c_i \cdot x.$$$ Let’s say we start at $$$k = 1$$$ and this will be our first $$$L$$$ for some $$$x.$$$ How can we efficiently find $$$R$$$?
We know that:
$$$\lceil \frac{a_i}{L} \rceil = x.$$$
Since $$$R > L,$$$ we know that $$$\lceil \frac{a_i}{R} \rceil < x.$$$
$$$\lceil \frac{a_i}{R} \rceil \le x - 1$$$
So $$$\frac{a_i}{R} \le x - 1$$$
$$$\frac{a_i}{x - 1} \le R$$$
$$$R = \lceil \frac{a_i}{x - 1} \rceil$$$
We can set $$$L = R$$$ and then do the same steps for the new $$$L$$$ until we have covered all of the ranges. This solution is too slow for python so I had to convert it to c++
I believe that the editorial does a good job in explaining this one. Here is my implementation anyway (I finally got AC with python).
OMG, cp is hard, i'm giving up
Wow, thanks for reminding me about this comment. I just figured out how to use latex so imma prettify it.
edit: well... I tried my best. At least now I know why authors only use 1 letter to name arrays.