Pyramidal Array#12322

Pyramidal Array (Editorial)

Problem Author:	Ihor Melnykovych (Melnykovych_Ihor)
Prepared by:	Ihor Melnykovych (Melnykovych_Ihor)
Analysis:	Andriy Kholod (Connect)

Solution

Key Idea: Maximum of the Pyramid

Let $m x = max (a)$ mx = \max(a). In any pyramid, the maximum is some value $H$ , and all numbers $1.. H - 1$ 1..H-1 must appear on both sides of the maximum.

Since we can only insert 1 and increase, we cannot decrease elements. Therefore, it is natural to build a pyramid with a height no less than the current maximum, and in the optimal solution (for this implementation), the main case considered is $H = m x$ H = mx.

Let all positions with the maximum value $m x$ in the initial array form a segment $[l, r]$ [l, r] (where $l$ is the first occurrence of $m x$ , and $r$ is the last).

1) Splitting into Left and Right Parts

We build two "half-pyramids" that connect at the maximum:

Left part: elements $a_{0} .. a_{l}$ a_0..a_l (including the first maximum).
Right part: elements $a_{n - 1} .. a_{r}$ a_{n-1}..a_r in reverse order (i.e., looking from right to left, including the last maximum).

In the code, these are arrays $b [0]$ and $b [1]$ .

Next, there is a helper function: $[so l v e (b, m x) \to (an s, r es)]$ [ solve(b, mx) \rightarrow (ans, res) ] which for a given "edge" calculates two quantities:

$an s$ — the total cost to make this part compatible with a pyramid of height $m x$ without using the "free insertion $c$ " as a trick;
$r es$ — the same, but considering the maximum possible "discount" effect (the place where it is beneficial to insert the free $c$ to save 1 operation).

2) What does solve(a, mx) do

Let the input array $a$ be the part that needs to become non-decreasing up to the peak (since we are building an "ascent" to the maximum).

First, we make $a$ non-decreasing: $[a_{i} \leftarrow max (a_{i}, a_{i - 1})]$ [ a_i \leftarrow \max(a_i, a_{i-1}) ] The cost of increases is added to $an s$ .
Next, we go from right to left and "nail down" the values so that we can form a descent $m x, m x - 1, \dots$ mx, mx-1, \dots from the right:
For each element, we take $[n e w_v a l = max (a_{i}, m x)]$ [ new\_val = \max(a_i, mx) ] and pay $n e w_v a l - a_{i}$ new\_val - a_i (since only increases are allowed). If $n e w_v a l = m x$ new\_val = mx, we have "used" this value for the pyramid and decrease the required height: $[m x \leftarrow m x - 1]$ [ mx \leftarrow mx - 1 ] Thus, the algorithm tries to fill levels $m x, m x - 1, \dots, 1$ mx, mx-1, \dots, 1 with real elements (with minimal increases).
If after the pass $m x > 0$ mx > 0 remains, then numbers $1.. m x$ will have to be added with insertions of ones and increases (this actually costs the sum): $[1 + 2 + \dots + m x = \frac{m x ( m x + 1 )}{2}]$ [ 1 + 2 + \dots + mx = \frac{mx(mx+1)}{2} ] This addition is added to $an s$ .
The "discount" is the maximum number of consecutive elements from the right that we increased (i.e., where $n e w_v a l > a_{i}$ new\_val > a_i). The intuition is this: if we insert a free element $c$ into this area, we can save 1 operation (since one of the increases/inserts can be replaced with a free insertion).
It also considers the case when there is still a deficit of levels $m x$ — then inserting $c$ can "cover" one of the required levels.

It returns: $[r es = an s - d i sco u n t]$ [ res = ans - discount ] that is, the best option with "one free insertion" for this half.

3) How to combine left and right

There are two scenarios: the maximum of the pyramid is formed from the left or the right (since the insertion $c$ can be used in different places). Therefore, for the final answer, we combine: $[min (r es L . an s + r es R . r es, r es L . r es + r es R . an s)]$ [ \min(resL.ans + resR.res,\; resL.res + resR.ans) ] that is, in one half we use the "improved" option (with a discount), and in the other — the regular one.

4) Case when the maximum occurs multiple times

If $l \neq = r$ l \ne r, then we have a segment of maxima $[l, r]$ [l,r] in the initial array.

First, all elements inside this segment that are less than $m x$ need to be raised to $m x$ (since the maximum must be the same value on the "plateau" before processing): $[b o n u s = \sum_{i = l}^{r} (m x - a_{i})]$ [ bonus = \sum_{i=l}^{r} (mx - a_i) ] This is simply a mandatory surcharge.

Second, the pyramid requires a single maximum. Therefore, we need to "break" the plateau. This is done by using the insertion $c$ as a new peak or as an element that allows making a peak in the required place. In the code, two subcases are considered:

If $r - l + 1 > 2$ r-l+1 > 2, then 1 additional operation (insertion of 1 or increase) is enough to correctly form a single peak, so we try: $[min (r es L . an s + r es R . r es, r es L . r es + r es R . an s) + 1]$ [ \min(resL.ans + resR.res,\; resL.res + resR.ans) + 1 ] along with the base $r es L . an s + r es R . an s$ resL.ans + resR.ans.
If the plateau is very short ( $2$ ), we need to carefully "check" both options, removing $m x$ from one side (temporarily), recalculating solve, and adding $+ 1$ .

The final answer is printed as: $[an s + b o n u s]$ [ ans + bonus ]

5) Separate edge cases

If $m x = 1$ mx=1:

for $n = 1$ n=1 we need to insert another element to make the maximum unique $\Rightarrow$ the answer is $1$ ;
otherwise, the array can already be made pyramid-like with a free insertion $c$ (inserting $1$ in the right place), so the answer is $0$ .

Asymptotics

The function solve works in $O (k)$ for the length of the array $k$ . In the main program, it is called a constant number of times (up to a few recalculations in the case of a short plateau), so the overall asymptotic complexity is: $O (n)$ Memory: $O (n)$

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<class T>
using vec = vector<T>;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KoRoVa
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = -1, inf = 1000111222;

pair<ll, ll> solve (vector <int> a, int mx) { // [1, mx]
    int n = len(a);
    ll ans = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] < a[i - 1]) {
            ans += a[i - 1] - a[i];
            a[i] = a[i - 1];
        }
    }
    vector <int> b;
    int cnt = 0, discount = 0;
    for (int i = n - 1; i >= 0; i--) {
        int new_val = max(a[i], mx);
        ans += new_val - a[i];
        if (new_val == mx) {
            --mx;
        }
        if (new_val > a[i]) {
            ++cnt;
        }
        else {
            cnt = 0;
        }
        umax(discount, cnt);
    }
    assert(mx >= 0);
    ans += mx * (mx + 1ll) / 2;

    umax(discount, mx + cnt);

    ll res = ans - discount;

    LOG(ans, res, discount);

    return make_pair(ans, res);
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vector <int> a(n);
    for (auto &i : a) cin >> i;
    int mx = *max_element(all(a));
    if (mx == 1) {
        if (n == 1) {
            cout << "1\n";
            return 0;
        }
        cout << "0\n";
        return 0;
    }
    int l = -1, r = -1;
    for (int i = 0; i < n; i++) {
        if (a[i] == mx) {
            r = i;
            if (l == -1) {
                l = i;
            }
        }
    }
    vector <int> b[2];
    for (int i = 0; i <= l; i++) {
        b[0].pb(a[i]);
    }
    for (int i = n - 1; i >= r; i--) {
        b[1].pb(a[i]);
    }
    auto resL = solve(b[0], mx);
    auto resR = solve(b[1], mx);
    if (l != r) {
        ll bonus = 0;
        for (int i = l; i <= r; i++) {
            bonus += mx - a[i];
        }
        ll ans = resL.first + resR.first;
        if (r - l + 1 > 2) {
            umin(ans, min(resL.first + resR.second, resL.second + resR.first) + 1);
        }
        else {
            for (int it = 0; it < 2; it++) {
                assert(b[it].back() == mx);
                b[it].pop_back();
                auto res1 = solve(b[0], mx);
                auto res2 = solve(b[1], mx);
                b[it].pb(mx);
                umin(ans, min(res1.first + res2.second, res1.second + res2.first) + 1);
            }
        }
        cout << ans + bonus << '\n';
        return 0;
    }
    cout << min(resL.first + resR.second, resL.second + resR.first) << '\n';
}

/*
KoRoVa!
*/

C++