Zadanie

V dedine Kombajnov žije mladý nádejný kombajn Michal Kombajnerle. Kombajnerle obhospodaruje svoje pole, na ktorom rastie množstvo kukurice. Všetka kukurica na jeho poli rastie v jednom dlhom rade. Jedna rastlina kukurice vedľa druhej. Jednotlivé rastliny Kombajnerleho kukurice môžu byť rôzne vysoké.

Pri zbere je dôležité odstrihnúť z rastliny iba klas. Takto ostane v kukurici veľmi málo odpadu. Kombajnerle počas zberu prejde celé pole zľava doprava. Zaujíma ho, ako veľmi bude musieť pohybovať svojim strihačom hore a dole. Na to ešte Kombajnerleho prastarý otec z druhého kolena, Ondrej Kombajnáček, zaviedol prešpekulovanú metriku.

Postupne sa pozrie na každý súvislý úsek poľa kukurice. V úseku sa pozrie, aká vysoká je tam najvyššia a aká vysoká je tam najnižšia rastlina. Rozdiel týchto dvoch výšok prehlási za extremálny extraktor daného úseku. Na konci sčíta všetky extremálne extraktory a výsledok prehlási za supersumarizér daného poľa.

Keďže počítanie supersumarizéru je zdĺhavé, Kombajnerle by tento proces rád automatizoval…

Úloha

Dostanete popis Kombajnerleho poľa kukurice vo forme \(n\) čísiel. Jednotlivé čísla predstavujú výšky jednotlivých rastlín kukurice v poradí, v akom rastú na Kombajnerleho poli.

Definujme extremálny extraktor úseku poľa ako rozdiel maximálnej a minimálnej hodnoty v danom úseku. Ďalej definujme supersumarizér poľa ako súčet extremálnych extraktorov cez všetky neprázdne úseky daného poľa.

Vašou úlohou bude vypočítať supersumarizér Kombajnerleho poľa.

Formát vstupu

Na prvom riadku vstupu sa nachádza celé číslo \(n\) – počet rastlín kukurice na Kombajnerleho poli. Platí \(1 \leq n \leq 10^6\).

Na druhom riadku vstupu je \(n\) medzerou oddelených celých čísiel \(v_1\) až \(v_n\) – výšky rastlín kukurice na Kombajnerleho poli v poradí v akom rastú vedľa seba. Platí \(1 \leq v_i \leq 10^6\).

Je 8 sád vstupov. Pre jednotlivé sady naviac platia nasledovné obmedzenia:

Sada 1 2 3 4-5 6-8
\(1 \leq n \leq\) \(100\) \(1000\) \(5\,000\) \(10^5\) \(10^6\)

Formát výstupu

Na jedinom riadku výstupu vypíšte jedno číslo – supersumarizér poľa zo vstupu.

Príklady

Input:

3
1 3 2

Output:

5

V tomto prípade má pole 6 neprázdnych úsekov: [1], [3], [2], [1, 3], [3, 2] a [1, 3, 2]. Extremálne extraktory týchto úsekov sú postupne 0, 0, 0, 2, 1 a 2.

Input:

7
2 5 2 2 7 1 8

Output:

107

V tejto úlohe sme dostali pole \(n\) čísiel. Našou úlohou bolo vypočítať súčet rozdielov maximálnej a minimálnej hodnoty cez všetky neprázdne úseky tohto poľa.

Priamočiare riešenie

Najjednoduchším spôsobom, ako sa dostať k výsledku, je postupne prejsť všetky neprázdne úseky. V každom úseku nájdeme maximum a minimum, odčítame ich a pripočítame ku výsledku.

Koľko úsekov existuje? Úsek môže mať \(n\) rôznych začiatkov a ku každému začiatku rádovo \(n\) možných koncov. Úsekov je teda \(O(n^2)\). Pre každý úsek musíme nájsť maximum a minimum, čo vieme spraviť jednoduchým prechodom cez celý úsek. Celková časová zložitosť tohto riešenia je teda \(O(n^3)\).

Pamätať si potrebujeme vstupné pole veľkosti \(n\). Pamäťová zložitosť je teda \(O(n)\).

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    ll res = 0;
    for (int left = 0; left < n; left++) {
        for(int right = left; right < n; right++) {
            ll mn = 1000000000, mx = -1;
            for (int i = left; i <= right; i++) {
                mn = min(mn, (ll)v[i]);
                mx = max(mx, (ll)v[i]);
            }
            res += mx - mn;
        }
    }

    cout << res << '\n';

    return 0;
}

def main():
    n = int(input())
    v = list(map(int, input().split()))

    res = 0
    for left in range(n):
        for right in range(left, n):
            mn = float('inf')
            mx = -1
            for i in range(left, right + 1):
                mn = min(mn, v[i])
                mx = max(mx, v[i])
            res += mx - mn

    print(res)


main()

Drobné vylepšenie

Predchádzajúce riešenie vieme ľahko zlepšiť tak, aby malo časovú zložitosť \(O(n^2)\). Nebudeme prechádzať každý úsek od začiatku – ak už totiž poznáme minimum a maximum v úseku \([i, j]\), vieme v čase \(O(1)\) zistiť minimum a maximum v úseku \([i, j + 1]\).

Týmto spôsobom dostávame riešenie, ktoré má rovnakú zložitosť ako je počet všetkých úsekov, teda \(O(n^2)\). Ak ale chceme lepšiu časovú zložitosť, nebudeme už môcť prechádzať všetky úseky…

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    ll res = 0;
    for (int left = 0; left < n; left++) {
        ll mn = 1000000000, mx = -1;
        for(int right = left; right < n; right++) {
            mn = min(mn, (ll)v[right]);
            mx = max(mx, (ll)v[right]);
            res += mx - mn;
        }
    }

    cout << res << '\n';

    return 0;
}

def main():
    n = int(input())
    v = list(map(int, input().split()))

    res = 0
    for left in range(n):
        mn = 1000000000
        mx = -1
        for right in range(left, n):
            mn = min(mn, v[right])
            mx = max(mx, v[right])
            res += mx - mn

    print(res)


main()

Vzorové riešenie

Prvým pozorovaním je, že výsledok vieme získať ako súčet maxím cez všetky úseky mínus súčet miním cez všetky úseky. Budeme sa teda ďalej snažiť vypočítať tieto dve hodnoty. Ak vieme počítať súčet maxím, súčet miním budeme vedieť počítať analogicky. Pozrime sa teda na to, ako vieme efektívne vypočítať súčet maxím cez všetky úseky.

Často používanou technikou, ktorá bude užitočná aj pre nás, je technika príspevku k súčtu. Spočíva v tom, že pre každý prvok zistíme, koľko on sám prispeje ku výsledku. V našom prípade by sme pre každý prvok chceli vedieť, v koľkých úsekoch poľa bude práve on maximom. Ak je prvok \(v_i\) maximom v \(k\) rôznych úsekoch, tak ku celkovému súčtu maxím cez všetky úseky prispeje hodnotou \(k \cdot v_i\). Pozrime sa teda na to, ako pre každý prvok zistiť, v koľkých úsekoch je maximom.

Ale ešte predtým sa trochu zamyslime. Prvky poľa sa môžu opakovať. Môže teda nastať situácia, že nejaký úsek bude mať viacero maximálnych prvkov. Nemôže to spôsobiť, že pre daný úsek pripočítame všetky tieto maximá? Skutočne by sa nám to mohlo stať. Potrebujeme teda jednoznačne určiť, ktorý maximálny prvok budeme považovať za správny. Preformulujme teda to, čo hľadáme. Nebudeme pre každý prvok zisťovať, v koľkých úsekoch je maximom, ale v koľkých úsekoch je práve on tým najľavejším maximom.

Na to nám stačí vedieť dve veci:

  • Ako ďaleko od daného prvku môžeme ísť doľava, kým narazíme na väčší, alebo rovnaký prvok.
  • Ako ďaleko od daného prvku môžeme ísť doprava, kým narazíme na ostro väčší prvok.

To už nám stačí na výpočet počtu úsekov. Totiž, ak od prvku \(v_i\) vieme týmto spôsobom ísť doľava o \(l_i\) a doprava o \(r_i\) políčok, tak daný prvok bude najľavejším maximom v každom úseku, ktorý začína niekde na políčkach \(i - l_i\) až \(i\) a končí niekde na políčkach \(i\) až \(i + r_i\). Týchto úsekov je zjavne \((l_i + 1) \cdot (r_i + 1)\). Náš prvok teda k celkovému súčtu maxím prispeje hodnotou \(v_i \cdot (l_i + 1) \cdot (r_i + 1)\).

Zostáva vypočítať hodnoty \(l_i\) a \(r_i\). Keďže ich počítanie je analogické (až na ostrosť nerovnosti), ukážeme si iba ako spočítať hodnoty \(l_i\). Stačí nám na to jeden zásobník. Prvky poľa budeme prechádzať zľava doprava. Pozrime sa, ako spracujeme \(i\)-ty prvok:

Kým je na vrchu zásobníka číslo \(j\) také, že \(v_j < v_i\), tak ho zo zásobníka odstránime. Tým zo zásobníka postupne odstránime niekoľko (možno nula) prvkov. Ak sme zásobník úplne vyprázdnili, znamená to, že všetky prvky naľavo od \(i\)-teho boli menšie ako on. Ak sme zásobník nevyprázdnili, na jeho vrchu zostala najbližšia pozícia naľavo od \(i\), kde sa nachádza prvok väčší alebo rovný \(v_i\). Z tohto vieme odčítať hľadanú hodnotu \(l_i\). Následne na vrch zásobníka pridáme \(i\) a posunieme sa na spracovanie ďalšieho prvku rovnakým spôsobom.

Nemôže byť problematické, že sme zo zásobníka niektoré prvky odstránili? Nie! Na zásobník sme totiž po spracovaní \(i\)-teho prvku pridali číslo \(i\). Ak pri spracovaní nejakého ďalšieho prvku zo zásobníka odstránime \(i\), tak odstraňujeme aj všetky prvky s menšími hodnotami, než \(v_i\). Takže všetky čísla, ktoré sme odstránili pri spracovaní \(i\)-teho prvku, by sme odstránili tak či tak. Problematické to teda byť nemôže.

Celý algoritmus na vypočítanie \(l_i\) potrebuje iba jeden prechod cez pole. Každý prvok bude najviac raz pridaný na zásobník a najviac raz zo zásobníka odstránený. Časová zložitosť tohto prechodu je teda \(O(n)\). My potrebujeme vypočítať hodnoty \(l_i\) aj \(r_i\) pre zistenie súčtu maxím a následne pre zistenie súčtu miním. To sú 4 takéto prechody cez pole. Celková časová zložitosť tohto riešenia je teda \(O(n)\).

Pamätať si potrebujeme iba vstupné pole a zásobník. Pamäťová zložitosť riešenia je preto tiež \(O(n)\).

#include <bits/stdc++.h>

using namespace std;

// Pre prvok chceme zratat, pokial dolava a doprava mozeme od neho ist, aby on bol NAJLAVEJSIM minimom (resp. maximom)
// Preto ak ideme zlava, chceme pouzit ostru rovnost, ale ked ideme sprava, tak neostru.
bool should_pop(const string& side, const string& function, int a, int b) {
    if (side == "left") {
        if (function == "min") {
            return a > b;
        } else {
            return a < b;
        }
    } else {
        if (function == "min") {
            return a >= b;
        } else {
            return a <= b;
        }
    }
}

vector<int> calc_boundaries(vector<int> v, const string& side, const string& function) {
    int n = v.size();
    vector<int> boundary(n);

    // Ak chceme prave hranice, tak si otocime vstupne pole a zratame lave hranice
    // Toto je maly trik, aby sme neprogramovali takmer to iste dvakrat
    if (side == "right") {
        reverse(v.begin(), v.end());
    }

    // Prechadzajme polom zlava doprava
    // Pouzime stack na zratanie toho, po ktory index nalavo bude najmensim (resp. najvacsim) prvkom
    stack<int> s;
    for(int i = 0; i < v.size(); i++) {
        while(!s.empty() && should_pop(side, function, v[s.top()], v[i])) {
            s.pop();
        }
        if(s.empty()) {
            boundary[i] = -1;
        } else {
            boundary[i] = s.top();
        }
        s.push(i);
    }

    // Ak sme pocitali prave hranice, tak sme na zaciatku otocili pole
    // Musime teda "zrkadlovo" otocit aj vysledok
    if (side == "right") {
        for (int i = 0; i < n; i++) {
            boundary[i] = n - 1 - boundary[i];
        }
        reverse(boundary.begin(), boundary.end());
    }

    return boundary;
}

int main() {
    int n;
    cin >> n;
    vector<int> v(n);

    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    vector<string> functions = {"min", "max"};
    long long result = 0;
    for (auto &function: functions) {
        vector<int> left = calc_boundaries(v, "left", function);
        vector<int> right = calc_boundaries(v, "right", function);
        for (int i = 0; i < n; i++) {
            long long elems_to_the_left = i - left[i] - 1;
            long long elems_to_the_right = right[i] - i - 1;
            long long this_elem_subsegments = (elems_to_the_left + 1) * (elems_to_the_right + 1);
            long long sum_values_for_segments = v[i] * this_elem_subsegments;
            if (function == "max") {
                result += sum_values_for_segments;
            } else {
                result -= sum_values_for_segments;
            }
        }
    }

    cout << result << '\n';

    return 0;
}

from typing import List


def should_pop(side: str, function: str, a: int, b: int) -> bool:
    if side == "left":
        if function == "min":
            return a > b
        else:
            return a < b
    else:
        if function == "min":
            return a >= b
        else:
            return a <= b


def calc_boundaries(v: List[int], side: str, function: str) -> List[int]:
    n = len(v)
    boundary = [0] * n

    if side == "right":
        v = v[::-1]

    s = []
    for i in range(n):
        while s and should_pop(side, function, v[s[-1]], v[i]):
            s.pop()
        if not s:
            boundary[i] = -1
        else:
            boundary[i] = s[-1]
        s.append(i)

    if side == "right":
        boundary = [n - 1 - x for x in boundary]
        boundary = boundary[::-1]

    return boundary


def main() -> None:
    n = int(input())
    v = list(map(int, input().split()))

    functions = ["min", "max"]
    result = 0

    for function in functions:
        left = calc_boundaries(v, "left", function)
        right = calc_boundaries(v, "right", function)
        for i in range(n):
            elems_to_the_left = i - left[i] - 1
            elems_to_the_right = right[i] - i - 1
            this_elem_subsegments = (elems_to_the_left + 1) * (elems_to_the_right + 1)
            sum_values_for_segments = v[i] * this_elem_subsegments
            if function == "max":
                result += sum_values_for_segments
            else:
                result -= sum_values_for_segments

    print(result)


main()

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.