A hacky-ish way to solve AtCoder Beginner Contest 395 F

#	User	Rating
1	tourist	3857
2	jiangly	3747
3	orzdevinwang	3706
4	jqdai0815	3682
5	ksun48	3591
6	gamegame	3477
7	Benq	3468
8	Radewoosh	3463
9	ecnerwala	3451
10	heuristica	3431

#	User	Contrib.
1	cry	165
2	-is-this-fft-	161
3	Qingyu	160
4	Dominater069	158
5	atcoder_official	157
6	adamant	155
7	Um_nik	152
8	djm03178	151
9	luogu_official	149
10	awoo	148

Just wanted to share a way to solve https://atcoder.jp/contests/abc395/tasks/abc395_f. Tried 1000 random test cases to make sure it wasn't wrong against some top 10 solutions and they all matched so I think the claims I make and the proofs associated with them work but you're welcome to prove me wrong.

My idea was to:

First satisfy $$$ |U_i - U_{i+1}| \leq X \quad \text{for every integer } i \text{ with } 1 \leq i < N. $$$
Check all the sums $$$ U_i + D_i \text{ with } 1 \leq i < N. $$$ and take the minimum sum.
Iterate through all the indices $$$ 1 \leq i < N $$$ and remove $$$ U_i + D_i - min_{sum} $$$ to the bottom tooth in priority and then the upper tooth if the bottom tooth size goes to 0.

Two things need to be addressed:

How can I satisfy $$$ |U_i - U_{i+1}| \leq X \quad \text{for every integer } i \text{ with } 1 \leq i < N. $$$ in O(N)? If I do something like:

        for i in range(n-1):
            if u[i] - u[i+1] > x:
                cost += (u[i] - u[i+1] - x)
                u[i] -= (u[i] - u[i+1] - x)
            if u[i+1] - u[i] > x:
                cost += (u[i+1] - u[i] - x)
                u[i+1] -= (u[i+1] - u[i] - x)

Then this array $$$U = [10, 8, 6, 4, 2]$$$ with $$$X = 1$$$ is not correctly changed, since it would become $$$ U = [9, 7, 5, 3, 2]$$$. We can obviously do that $$$N$$$ times but then it becomes O(N^2).

The hack here is to do in both directions (for i increasing and for i decreasing). Indeed those "blocks" such as $$$U = [10, 8, 6, 4, 2]$$$ that make our algorithm fail are completely solved if we consider it the other way around. It looks like this:

    for i in range(n-1):
        if u[i] - u[i+1] > x:
            cost += (u[i] - u[i+1] - x)
            u[i] -= (u[i] - u[i+1] - x)
        if u[i+1] - u[i] > x:
            cost += (u[i+1] - u[i] - x)
            u[i+1] -= (u[i+1] - u[i] - x)
    for i in range(n-1, 0, -1):
        if u[i] - u[i-1] > x:
            cost += (u[i] - u[i-1] - x)
            u[i] -= (u[i] - u[i-1] - x)
        if u[i-1] - u[i] > x:
            cost += (u[i-1] - u[i] - x)
            u[i-1] -= (u[i-1] - u[i] - x)

We have to consider both directions because only considering the reverse direction would encounter a similar problem on $$$U = [2, 4, 6, 8, 10]$$$

When I iterate through all the indices $$$ 1 \leq i < N $$$ and remove $$$ U_i + D_i - min_{sum} $$$, how do I know I won't break $$$ |U_i - U_{i+1}| \leq X \quad \text{for every integer } i \text{ with } 1 \leq i < N. $$$

If I need to remove some upper tooth $$$i$$$'s length, it means that $$$D_i = 0$$$ at this point and the minimum sum $$$min_{sum}$$$ is smaller than $$$U_i$$$, so if $$$U_{i+1}$$$ (or $$$U_{i-1}$$$) is bigger than $$$U_i$$$, it will have to decrease as well, and $$$ |U_i - U_{i+1}| \leq X \quad \text{for every integer } i \text{ with } 1 \leq i < N. $$$ won't break. If $$$U_{i+1}$$$ (or $$$U_{i-1}$$$) is smaller than $$$U_i$$$, well I'm bringing $$$U_i$$$ closer to them, so it shouldn't be a problem (and if I'm bringing $$$U_i$$$ below them, we get back to the first point where $$$U_{i+1}$$$ (or $$$U_{i-1}$$$) is bigger than $$$U_i$$$).

And that's it, feels very hacky, but seems to do the job and there's currently no editorial yet so I don't know if it was the intended solution.

Python submission: https://atcoder.jp/contests/abc395/submissions/63338450

C++ submission: https://atcoder.jp/contests/abc395/submissions/63338490

History