5. Problematický tréning vzorové riešenie

10
5 2 17 3 -3 4 6 -5 -5 50

6
3 8

5
200 30 60 -2 12

-1

3
7 8 0

1
2 2

V tejto úlohe máme v kope údajov nájsť dve miesta, ktoré majú rovnakú výšku a sú od seba čo najvzdialnejšie. Tie by totiž mohli ukazovať na okruh, ktorý Roman beháva. Problémom však je, že nemáme k dispozícii postupnosť výšok, v ktorých sa Roman nachádzal, ale len zmeny nadmorskej výšky, ktoré pri behu robil.

Mohli by sme teda začať tým, že z tejto postupnosti zmien vypočítame, v akých nadmorských výškach sa Roman kedy nachádzal. Samozrejme nevieme, na akej nadmorskej výške začínal. Budeme však predpokladať, že to bolo vo výške \(0\). Čo sa totiž zmení, ak by skutočná začiatočná výška bola napríklad 10? Len to, že všetky ďalšie výšky budú tiež o 10 vyššie. Ale naším cieľom je hľadať dvojicu rovnakých čísel. A tá bude rovnaká bez ohľadu na to, či bude zväčšená alebo zmenšená o 10.

Budeme si teda udržiavať jednu premennú vyska, v ktorej si budeme zaznačovať, v ktorej nadmorskej výške sa Roman práve nachádza. Na začiatku sa vyska = 0. Následne prechádzame postupnosťou zmien a každú zmenu jednoducho pričítame k aktuálnej výške. Ak Roman stúpol o 10, tak pričítame 10, ak o 10 klesol, tak pričítame \(-10\).

Tento postup, v ktorom postupne nasčítavame vstupné hodnoty je pomerne štandardný a má názov prefixové súčty. Viac si o ňom môžete prečítať v našej kuchárke: ksp.sk/kucharka/prefixove_sumy. Následne vieme z poľa rozdielov spraviť pole výšok takýmto jednoduchým programom:

V takto vytvorenom poli nadmorských výšok teraz chceme hľadať dve pozície, ktoré sú od seba čo najvzdialenejšie a majú rovnakú nadmorskú výšku. Najjednoduchší spôsob ako také niečo spraviť, je vyskúšať všetky možné dvojice.

A hoci je takéto riešenie správne, a na testovači zaň aj dostanete nejaké body, nie je úplne optimálne. Uvedomme si, že ak máme \(n\) výšok, tak všetkých dvojíc je \(n^2\). Náš algoritmus bude mať preto zložitosť \(O(n^2)\), čo je pre \(n=100\,000\) príliš veľa.

#include<iostream>
#include<vector>
using namespace std;

int main()
{
    //musime si pamatat cisla v long longoch lebo mozu byt az do 10^11
    long long   n,   //pocet usekov
                a, b,   //hranice aktualneho intervalu
                max_a, max_b, max_len = -1; //v troch premennych max_len, max_a a max_b si budeme
                                            //pamatat dlzku najdlhsieho doteraz videneho useku
    cin >> n; //nacitame pocet usekov
    
    vector<long long>rozdiely(n);
    for(long long i=0;i<n;++i)
    {
        cin >> rozdiely[i]; //ulozime vyskove rozdiely do pola (vector-u)
    }
    
    //vytvorime si prefixove pole prefix
    vector<long long>prefix(n+1);
    prefix[0] = 0; 
    for(long long i=1;i<=n;++i) 
    {
        prefix[i] = prefix[i-1] + rozdiely[i-1];
    }
  
    for(b=0;b<=n;++b) //prejdeme cez vsetky konce
    {
        for(a=0;a<b;++a)//a pre kazdy pre vsetky zaciatky; a<b
        {
            if((prefix[b]==prefix[a]) && (b-a+1 > max_len))
            //ak je vyhovujuci a dlhsi ako doteraz najdlhsi najdeny, tak si ho zapiseme
            {
                    max_a = a;
                    max_b = b-1;
                    max_len = max_b-max_a+1;
            }
        }
    }
    
    cout<<max_len<<endl; //vypiseme najdlhsi
    if(max_len != -1) //ak vobec existuje
        cout << max_a << " " << max_b << endl;
    return 0;
}

n = int(input()) #nacitame pocet usekov

rozdiely = [int(x) for x in input().split(' ')] #ulozime vyskove rozdiely do pola (list-u)

#vytvorime si prefixove pole prefix
vyska=0
prefix = [0]
for i in range(n):
    vyska+=rozdiely[i]
    prefix.append(vyska)

# v troch premennych max_len, max_a a max_b si budeme
# pamatat dlzku najdlhsieho doteraz videneho useku
max_len=-1
max_a=0
max_b=0

for b in range(n+1): #prejdeme cez vsetky konce
    for a in range(b): #a pre kazdy pre vsetky zaciatky; a<b
        #a, b su hranice aktualneho intervalu
        if prefix[b] == prefix[a] and b-a+1 > max_len:
            #ak je vyhovujuci a dlhsi ako doteraz najdlhsi najdeny, tak si ho zapiseme
            max_a = a;
            max_b = b-1;
            max_len = max_b-max_a+1;

print(max_len) #vypiseme najdlhsi
if max_len != -1: #ak vobec existuje
    print(max_a, max_b)

Vzorové riešenie

V predchádzajúcom riešení sme skúšali všetky možné dvojice čísel. Je to však nutné? Nerobili sme niečo zbytočne? Robili, napríklad sme porovnávali aj pozície, ktoré obsahovali rôzne čísla a teda okruh vôbec nemohli vytvoriť. Naše riešenie by sme preto vedeli zlepšiť, ak by sme výšku \(x\) porovnávali iba s výškami \(x\). Môže sa nám však stať, že Roman bežal celý čas po rovine a zmeny nadmorskej výšky boli celý čas \(0\). V takom prípade by naše pole nadmorských výšok obsahovalo samé 0 a my by sme opäť skúšali všetky dvojice.

Ak by sme sa pozreli iba na pozície, na ktorých sa nachádza výška \(x\), je nutné skúšať všetky dvojice týchto pozícií? Uvedomme si, že hľadáme dvojicu, ktorá je najvzdialenejšia. A ak hľadáme dva najvzdialenejšie výskyty čísla \(x\), tak to znamená, že chceme zobrať prvý a posledný výskyt čísla \(x\) v poli. Ľubovoľná iná dvojica bude totiž k sebe bližšia.

Naše riešenie by preto mohlo vyzerať nasledovne. Po vypočítaní nadmorských výšok, v ktorých sa Roman nachádzal ich budeme prechádzať zľava doprava. Nech sa nachádzame vo výške \(x\). Keďže nevieme, či toto \(x\) nie je posledné \(x\) v našom poli, musíme vyskúšať jeho vzdialenosť od prvého výskytu čísla \(x\) v našom poli. Ak je táto vzdialenosť najväčšia, akú sme zatiaľ videli, tak si ju zapamätáme.

Takéto riešenie znie sľubne, pretože vyskúšame iba \(n\) rôznych dvojíc – pre každú výšku sa pozrieme iba na najľavejšiu takú výšku v našom poli. Ešte sme však nevyriešili to, ako (čo najrýchlejšie) zistiť, na ktorej pozícii sa nachádza najľavšie číslo \(x\) v našom poli.

Najjednoduchšie riešenie by bolo zobrať pole prve_vyskyty[], do ktorého by sme si tieto pozície značili. Na začiatku by boli v poli iba čísla \(-1\). Vždy keď by sme spracovávali číslo \(x\), najskôr by sme sa pozreli na pozíciu \(x\) v tomto poli. Ak by sa prve_vyskyty[x] rovnalo \(-1\), tak by to znamenalo, že aktuálna pozícia je prvou pozíciou, na ktorej sa nachádza číslo \(x\). Číslo tejto pozície by sme si preto zapísali do prve_vyskyty[x]. Naopak, ak by na tejto pozícii nebolo číslo \(-1\), tak toto číslo by bola pozícia prvého výskytu čísla \(x\) a preto by sme rovno zistili ich vzájomnú vzdialenosť.

Takéto riešenie je síce veľmi pekné a jednoduché, má však malý háčik. Romanových záznamov je \(100\,000\) a najväčšia zmena nadmorskej výšky, ktorú spravil môže byť až \(1\,000\,000\). To znamená, že keď počítame ako vysoko mohol vybehnúť, môžeme sa dostať až k číslam veľkým \(10^5 \cdot 10^6 = 10^{11}\). Naše pole by teda muselo mať \(10^{11}\) pozícií, na každej z nich by si pamätalo jedno 4 bajtové číslo, preto veľkosť takéhoto poľa by bola rádovo 400 GB. Takú veľkú operačnú pamäť (RAM) však na testovači nemáme (a asi ani vy doma).

Problémom takéhoto ukladania do poľa je, že v tomto poli je zbytočne veľa priestoru. Napriek tomu, že doň uložíme najviac \(100\,000\) čísel, vytvoríme si \(10^{11}\) políčok. Našťastie boli vymyslené dátové štruktúry, ktoré sa nazývajú asociatívne polia. Fungujú podobne ako klasické polia, akurát vytvárajú iba políčka, ktoré potrebujeme. Preto ak použijeme asociativne_pole[1000], tak sa nevytvorí \(1\,000\) políčok, ale iba jedno. Naviac v asociatívnych poliach vieme indexovať nielen celými číslami, ale takmer všetkým, čo sa dá navzájom porovnávať, napríkald stringom (text) alebo floatom (desatinné číslo).

V C++ sa asociatívne pole volá map. Základy jeho používania si môžete pozrieť v nasledujucom zdrojovom kóde:

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main ()
{
  map<string,float> mapa; // deklaracia pod stringami(text) budeme mat ulozene rozne desatinne cislo

  mapa["cislo"]=11.5; //ulozenie cisla pod text
  mapa["dolezite cislo"]=42.47;
  mapa["nula"]=0;
  
  mapa["cislo"]=mapa["dolezite cislo"]; //zmena cisla za ine
  cout<<"mapa[\"cislo\"]="<<mapa["cislo"]<<endl; //pristup k  cislu pod textom
  cout << "v mape su " << mapa.size() << " prvky."<<endl; //pocet prvkov pola
  cout<<"nula je v mape "<<mapa.count("nula")<<" krat!"<<endl;
  //mapa.count vracia 0 alebo 1 podla toho, ci uz bolo k danemu klucu priradene desatinne cislo alebo nie
  
  return 0;
}
//vystup:
//  mapa["cislo"]=42.47
//  v mape su 3 prvky.
//  nula je v mape 1 krat!

Viac o map v C++ sa môžete dočítať online, napríklad http://www.cplusplus.com/reference/map/map/.

V Pythone sa asociatívne pole volá dict. Základy jeho používania si môžete pozrieť v nasledujucom zdrojovom kóde:

D=dict() #nazov pre asociativne pole v Phytone
D["cislo"]=11.5 #ulozenie desatinneho cisla pod text
D["dolezite cislo"]=42.47
D["nula"]=0

D["cislo"]=D["dolezite cislo"] #zmena cisla za ine
print("D[\"cislo\"]=", D["cislo"]) 
print("V D su",len(D), "prvky.") #pocet prvkov v dict
print("Je nula v D?", "nula" in D) #zistovanie ci uz prvok je v dict

# Vystup po spusteni:
#  D["cislo"]= 42.47
#  V D su 3 prvky.
#  Je nula v D? True

Viac o dict v Python sa môžete dočítať online, napríklad https://www.tutorialspoint.com/python/python_dictionary.htm.

Keďže v asociatívnom poli si pamämáme iba prvky, ktoré skutočne potrebujeme, tak ak doňho vložíme \(n\) prvkov, jeho pamäťová zložitosť bude \(O(n)\). Samozrejme, má to aj nevýhodu a tou je časová zložitosť. Každá operácia s asociatívnym poľom nám trvá logaritmicky dlho od počtu jeho prvku. V našom prípade teda \(O(\log n)\), čo vedie k celkovej časovej zložitosti \(O(n \log n)\), pretože pre každý prvok našich prefixových súčtov sa raz pozrieme do asociatívneho poľa.

Napriek tomu je však asociátívne pole pomerne užitočné, ak však môžete použiť klasické pole, tak to spravte, predsa len to bude rýchlejšie.