Zadanie

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy.

Stačí, že pôjdeš na stránku Programátorskej Liahni (liahen.ksp.sk). Keď budeš riešiť sadu variables_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Andrejovi na andrejkorman1@gmail.com

Zima sa blíži a Syseľ by sa pomaly chcel pobrať na zimný spánok1. Ručička váhy sa však zastavila na vysokom čísle. Rozhodol sa teda, že bude trénovať, aby si pred tuhou zimou zlepšil kondičku. Rýchlo však zistil, že bezcieľne behanie po lese vôbec nie je efektívne. Nuž obrátil sa na Romana, profesionálneho bežca, ktorý mu ale tajomstvo svojho bežeckého umu nechcel prezradiť. Pri stretnutí s Romanom sa mu však podarilo zapamätať si časť jeho tréningového plánu.

Ten tvorí niekoľko po sebe idúcich čísel, ktoré symbolizujú zmeny v nadmorskej výške. Roman si pri behaní značí každú nezanedbateľnú zmenu v nadmorskej výške ako celé číslo. Kladným číslom ozačuje stúpania a záporným klesania. Pre názornú ukážku môže jeho plán vyzerať napríklad takto: [40, 20, -25, 5]. Vidíme, že ho na trase najskôr čakajú 2 stupáky (40 a 20), kedy dokopy stúpne o 60 výškových metrov, potom nasleduje jedno klesanie o 25 metrov a nakoniec malý kopček.

Syseľ má teraz v hlave nejakú časť Romanovho tréningového plánu, no stále nevie, aký úsek tohto plánu Roman za deň absolvuje. Uvedomil si ale jednu vec – Roman obľubuje bežať okruhy. Rád začína aj končí pri svojom dome, teda v rovnakej nadmorskej výške. Sysľovi preto stačí nájsť postupnosť, ktorej celková zmena v nadmorskej výške je nulová. V príklade vyššie by to bola časť [20, -25, 5].

Takýchto postupností môže samozrejme existovať viac. Ak ale nájde najdlhšiu takúto postupnosť, bude vedieť koľko najmenej musí zabehnúť, aby sa vyrovnal Romanovi. Čísel, ktoré si Syseľ zapamätal, je však veľa a preto vás požiadal o pomoc.

Úloha

Vašou úlohou je napísať program, ktorý na vstupe dostane postupnosť \(n\) čísel, reprezentujúcu časť Romanovho plánu, ktorú si Syseľ stihol zapamätať. Na výstup potom vypíše dĺžku, začiatok a koniec najdlhšej podpostupnosti, ktorej celková zmena nadmorskej výšky je nulová. V danej postupnosti teda hľadáte najdlhší úsek za sebou idúcich čísel, ktoré keď sčítate dokopy, dostanete výsledok 0.

Ak existuje takýchto najdlhších podpostupností viac, vypíšte ľubovoľnú z nich.

Formát vstupu

Na prvom riadku je číslo \(n\) – dĺžka postupnosti zapamätaných čísel. Na druhom riadku je \(n\) medzerou oddelených celých čísel. Každé z týchto čísel reprezentuje nárast alebo pokles nadmorskej výšky v poradí, v akom sa nachádzali v Romanovom pláne.

Formát výstupu

Na prvý riadok vypíšte dĺžku najdlhšej podpostupnosti so súčtom \(0\). Potom vypíšte na ďalší riadok ešte dve čísla oddelené medzerou – poradové číslo prvého a posledného čísla tejto podpostupnosti v pôvodnej postupnosti. Prvý prvok postupnosti má poradové číslo 0.

Ak takáto podpostupnosť neexistuje, vypíšte na jediný riadok výstupu hodnotu \(-1\).

Pri riešení v jazyku C++, Pascal, Java a podobných, si dávajte pozor na maximálne číslo, ktoré sú schopné celočíselné premenné uložiť. Súčet všetkých čísiel v postupnosti môže v poslednej sade tieto limity prekročiť. Odporúčame preto použiť \(64\)-bitové premenné, v jazyku C++ preto namiesto typu int použite typ long long int.

Riešení v Pythone sa takýto typ obmedzení netýka, pretože premenné v ňom majú neobmedzenú veľkosť.

Hodnotenie

Vaše riešenie bude otestované na \(3\) sadách vstupov. Za vyriešenie každej sady získate 5 bodov. Tieto sady sa líšia veľkosťou vstupných údajov. Nech \(n\) je dĺžka postupnosti a \(x\) je prvok tejto postupnosti, teda prevýšenie. Potom v jednotlivých sadách platí:

Číslo sady 1 2 3
maximálne \(n\) \(100\) \(50\,000\) \(100\,000\)
maximálne \(|x|\) \(1\,000\,000\) \(10\) \(1\,000\,000\)

Príklady

Input:

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

Output:

6
3 8

Ak si pozrieme podpostupnosť \([3, -3]\), vidíme, že táto podpostupnosť má nulový súčet. Nie je však najdlhšia možná. Najdlhšia takáto postupnosť je postupnosť \([3, -3, 4, 6, -5, -5]\), ktorá má dĺžku 6. Táto postupnosť začína na pozícii 3 (číslované od 0) a končí na pozícii 8.

Takýto vstup by sa mohol nachádzať v ľubovoľnej sade.

Input:

5
200 30 60 -2 12

Output:

-1

V tomto vstupe neexistuje podpostupnosť so súčtom 0.

Input:

3
7 8 0

Output:

1
2 2

Riešením môže byť aj podpostupnosť dĺžky 1.


  1. To je tá časť roku, kedy je úplne neproduktívny a chce sa mu iba spať a behať za syslicami.

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.

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ť.