2. A nech sú moje hady v suchu vzorové riešenie

12
0 1 0 2 1 0 1 3 2 1 2 1

6

       X
   XOOOXXOX
 XOXXOXXXXXX 
------------

3
1 1 1

0

Hlavná myšlienka

Koľko vody (aký vysoký stĺpec vody) sa na jednom mieste¹ pozemku udrží? Predstavme si najnižšie políčko² nad zemou na nejakom mieste na pozemku. Ak sú niekde na obidve strany od neho políčka so zemou, tak voda, ktorá naprší na toto políčko, neodtečie a toto políčko ostane zatopené. To isté platí aj pre každé ďalšie políčko nad ním. Čo v prípade, ak máme políčko, od ktorého je len na jednu stranu políčko so zemou? V takomto prípade sa tam voda neudrží, ale odtečie druhou stranou.

To znamená, že ak si nájdeme najvyššie miesto napravo a naľavo od nejakého miesta na pozemku, tak na tomto mieste pozemku sa udrží toľko vody, aký je rozdiel medzi výškou terénu nižšieho z týchto miest a miesta, na ktorom sme. Ak toto urobíme pre všetky miesta a sčítame množstvá vody, tak získame odpoveď – koľko vody sa udrží na celom pozemku.

Všetky nasledujúce riešenia počítajú odpoveď takýmto spôsobom, líšia sa len v tom, ako šikovne, a teda ako rýchlo, to robia.

Priamočiare riešenie

Najjednoduchšie riešenie je, že prejdeme všetky miesta na pozemku. Pre každé miesto najprv prejdeme všetky miesta na jednu a potom na druhú stranu. Takto pre obe strany nájdeme miesto s maximálnou výškou. Pre jedno miesto na pozemku má takéto prehľadanie zložitosť \(O(n)\), a kedže to potrebujeme urobiť pre \(n\) miest, tak nám to celkovo zaberie \(O(n^2)\) času. Pamäťová zložitosť je \(O(n)\), lebo okrem vstupného poľa dĺžky \(n\) a niekoľko málo premenných si nič iné nemusíme pamätať. Za takéto riešenie ste mohli získať \(2\) body.

#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
    long long sum=0, n=0, max_zlava=0, max_sprava=0;
    cin>>n;
    long long vysky[n];
    for(long long i=0; i<n; i++)
    {
        cin>>vysky[i];
    }
    
    for(long long i=0; i<n; i++)
    {
        max_sprava=0, max_zlava=0;
        for(long long j=0; j<=i; j++)
        {
            max_zlava=max(max_zlava, vysky[j]);
        }
        for(long long j=i; j<n; j++)
        {
            max_sprava=max(max_sprava, vysky[j]);
        }
        
        sum+=(min(max_sprava, max_zlava)-vysky[i]);
    }

    cout<<sum<<endl;

    return 0;
}

n = int(input())
vysky = list(map(int, input().split()))

suma = 0

for i in range(len(vysky)):

    max_zlava = 0
    for j in range(i+1):
        if max_zlava < vysky[j]:
            max_zlava = vysky[j]

    max_sprava = 0
    for j in range(i, len(vysky)):
        if max_sprava < vysky[j]:
            max_sprava = vysky[j]

    suma += min(max_zlava, max_sprava) - vysky[i]

print(suma)

Lepšie riešenie

Lepšie riešenie, za \(4\) body, ste mohli získať využitím pozorovania, že v riešení hrubou silou robíme jednu veľmi podobnú vec veľakrát. Touto vecou je (ak prechádzame miesta na pozemku zľava doprava) zisťovanie najvyššieho miesta naľavo. Predstavme si, že sme na nejakom mieste \(i\) na pozemku. Najvyššie miesto naľavo je buď také, aké bolo najvyššie miesto naľavo od miesta \(i-1\), alebo je to samotné miesto \(i-1\). Takto pri prechádzaní celého pozemku vieme pre každé miesto získať najvyššie miesto naľavo od neho v konštantom čase (porovnaním dvoch čísel). Najvyššie miesto napravo ale stále zisťujeme v zložitosti priemerne \(O(n/2)\). Celkovo sme teda zložitosť zlepšili na \(O(n(n/2))\), čo síce asymptotickú zložitosť nezlepší (Tá je stále \(O(n^2)\)), ale stačí to na získanie \(4\) bodov. Pamäťová zložitosť tohto riešenia je \(O(n)\), lebo opäť si okrem vstupného poľa dĺžky \(n\) a niekoľko málo premenných nemusíme pamätať nič iné.

#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
    long long sum=0, n=0, max_zlava=0, max_sprava=0;
    cin>>n;
    long long vysky[n];

    for(long long i=0; i<n; i++)
    {
        cin>>vysky[i];
    }
    
    for(long long i=0; i<n; i++)
    {
        max_zlava=max(max_zlava, vysky[i]);
        
        max_sprava=0;
        for(long long j=i; j<n; j++)
        {
            max_sprava=max(max_sprava, vysky[j]);
        }
        
        sum+=(min(max_sprava, max_zlava)-vysky[i]);
    }

    cout<<sum<<endl;

    return 0;
}

n = int(input())
vysky = list(map(int, input().split()))

max_zlava = 0

suma = 0
for i in range(n):
    max_zlava = max(max_zlava, vysky[i])

    max_sprava = 0
    for j in range(i, len(vysky)):
        if max_sprava < vysky[j]:
            max_sprava = vysky[j]

    suma += (min(max_zlava, max_sprava) - vysky[i])

print(suma)

Vzorové riešenie

Vzorové riešenie využíva predchádzajúcu myšlienku. Ak prechádzame pozemok zľava doprava, ľahko (v konštantnom čase) vieme pre každé miesto zistiť najvyššie miesto naľavo od neho. Ak ale prechádzame pozemok sprava doľava, tak vieme pre každé miesto ľahko zistiť najvyššie miesto napravo od neho. Keď prejdeme celý pozemok, raz sprava a raz zľava, tak získame pre každé miesto informáciu o najvyššom mieste naľavo a napravo od neho. Obidva tieto prechody (raz zľava doprava a raz sprava doľava) budú v zložitosti \(O(n)\). Následne musíme prejsť celý pozemok, pre každé miesto porovnať tieto dve hodnoty a vybrať menšiu z nich. To pre \(n\) miest trvá \(O(n)\) času. Celkovo nám teda toto riešenie zaberie \(O(n+n)\) času na predpočítanie najvyšších miest a potom \(O(n)\) času na prejdenie pozemku a sčítanie hodnôt. Spolu je to teda asymptoticky \(O(n)\). Pamäťová zložitosť tohto riešenia je stále \(O(n)\), lebo okrem vstupného poľa dĺžky \(n\) si pamätáme len konštantne veľa (\(2\)) polí dĺžky \(n\) a niekoľko málo premenných.

#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
    long long sum=0, n=0, maxi=0;
    cin>>n;
    long long vysky[n+1], max_zlava[n+1], max_sprava[n+2];
    
    //nacitanie vstupu na indexy 1 az n
    for(long long i=1; i<=n; i++)
    {
        cin>>vysky[i];
    }
    
    //najvyssie miesto nalavo od miesta i
    max_zlava[0]=0;
    for(long long i=1; i<=n; i++)
    {
        max_zlava[i]=max(vysky[i], max_zlava[i-1]);
    }
    
    //najvyssie miesto napravo od miesta i
    max_sprava[n+1]=0;
    for(long long i=n; i>0; i--)
    {
        max_sprava[i]=max(vysky[i], max_sprava[i+1]);
    }
    
    for(long long i=1; i<=n; i++)
    {
        sum+=(min(max_sprava[i], max_zlava[i])-vysky[i]);
    }

    cout<<sum<<endl;

    return 0;
}

n = int(input())

# vstupne pole je na indexoch 1 az n
vysky = [0] + list(map(int, input().split()))
max_zlava = [0]*(n+1)
max_sprava = [0]*(n+2)

for i in range(1, n+1):
    max_zlava[i] = max(max_zlava[i-1], vysky[i])

for i in range(n, 0, -1):
    max_sprava[i] = max(max_sprava[i+1], vysky[i])

suma = 0
for i in range(1, n+1):
    suma += (min(max_zlava[i], max_sprava[i])-vysky[i])

print(suma)