Zadanie

Určite poznáte krtka Peťka. Celé dni vyspáva v svojej podzemnej nore a zobudí sa iba vtedy, keď sa ide najesť. Našťastie, býva priamo pod jabloňovým sadom, stačí sa mu teda vykopať hore, pojesť čo najviac jabĺk a vrátiť sa do svojho pelechu, aby tam pokračoval vo svojej obľúbenej činnosti.

Jabloňový sad je vlastne rad \(n\) stromov, pod ktorými sú napadané jablká. Peťko si vždy vyberie nejaký súvislý úsek jabloní, vykope sa na jeho začiatku, potom prejde až k jeho koncu a zakope sa späť pod zem. Popritom zje všetky jablká, na ktoré narazí.

Niektoré jablká však padli už veľmi dávno a preto zhnili. Peťko je však takmer úplne slepý a preto nevie rozlíšiť zhnité jablko od toho zdravého. Časom sa už zmieril s tým, že na to, aby sa dobre najedol, musí zjesť aj nejaké hnilé jablká. Snaží sa však, aby rozdiel medzi počtom zdravých a zhnitých jabĺk, ktoré zje, bol čo najväčší.

Po tomto príbehu je vám určite ľúto chudáka Peťka, s jeho ťažkým životným štýlom. Môžete mu však pomôcť. Stačí ak mu poradíte, ktorý úsek jabloní si má vybrať, aby sa čo najlepšie najedol.

Úloha

Na vstupe dostanete popis jabloňového sadu ako postupnosť celých čísel. Pre každý strom budete vedieť, aký je rozdiel počtu zdravých a hnilých jabĺk pod týmto stromom. Keďže Peťko zje pod každým stromom všetky jablká, toto je naozaj jediná informácia, ktorú potrebujete.

Zistite, ktorý zo súvislých úsekov si má Peťko vybrať, aby bol rozdiel medzi počtom zdravých a zhnitých jabĺk, ktoré zje, najväčší možný.

Vstup

Prvý riadok vstupu obsahuje prirodzené číslo \(n\) (\(1 \leq n \leq 1\,000\,000\)) udávajúce počet stromov v sade.

Druhý riadok obsahuje \(n\) celých čísel \(p_i\) (\(-1\,000\,000\,000 \leq p_i \leq 1\,000\,000\,000\)) – rozdiely dobrých a zlých jabĺk pod jednotlivými stromami.

Výstup

Vypíšte jeden riadok a v ňom dve čísla \(a\), \(b\). Nech \(a\) (\(1 \leq a \leq n\)) je strom, pri ktorom sa má Peťko vykopať a \(b\) je počet stromov (vrátane stromu \(a\)), ktoré má prejsť smerom doprava. Ak existuje viacero riešení, vypíše ľubovoľné z nich.

Príklady

Input:

15
-1 -1 -1 1 2 3 4 5 -10 -10 -10 1 2 3 4

Output:

4 5

Krtkovi sa oplatí vykopať pri strome číslo 4 s počtom jabĺk 1, spapať potom 2, 3, 4 a 5 jabĺk pri nasledujúcich stromoch. Neoplatí sa mu ísť ďalej, takže sa zakope pri strome číslo 8.

Input:

5
-2 10 2 -3 4

Output:

2 4

Input:

3
1000000000 1000000000 1000000000

Output:

1 3

Dajte si pozor na veľkosť premennej, v ktorej si budete pamätať súčet!

Input:

5
-47 -42 -17 -13 -12

Output:

3 0

Môžte si všimnút že správnych riešení je 5.

V tejto úlohe sa dalo spraviť celkom priamočiare riešenie, ktoré by potrebovalo čas \(O(n^2)\), jednoducho tak, že vyskúšame súčet čísel v každom súvislom úseku. Napríklad pre každý začiatok úseku skúsime postupne pričítavať prvky sprava a popritom všetkom si budeme udržiavať, aký najvyšší súčet sme doposiaľ videli, kde začínal úsek s týmto súčtom a aký bol dlhý.

Takéto riešenie síce nedostane plný počet bodov, ale je lepšie mať aspoň niečo.

var     i, j, sum, n                    : int64;
        bestsum, bestbegin, bestlen     : int64;
        cisla                           : array [1..1000009] of int64;

begin

    //Nacitame a nastavime vsetko potrebne
    read(n);
    bestsum := 0;
    bestbegin := 1;
    bestlen := 0;
    for i:=1 to n do read(cisla [i]);

    //Vonkajsim cyklom si urcime zaciatok
    for i:=1 to n do begin

        //Novy zaciatok znamena sucet 0
        sum := 0;

        //Vnutornym cyklom prejdeme konce
        for j:=i to n do begin

            //Sucet po tento koniec je rovny predoslemu suctu
            //navysenemu o cislo na aktualnej pozicii
            sum := sum + cisla [j];

            //ak mame lepsi vysledok, poznamename si ho
            if sum > bestsum then begin
                bestsum := sum;
                bestbegin := i;
                bestlen := j - i + 1;
            end;
        end;
    end;

    writeln(bestbegin, ' ', bestlen);
end.

Jeden prístup

Jedna spásonosná myšlienka, ktorá vám mohla napadnúť, je pozrieť sa na úlohu ako na úseky kladných1 a záporných čísel. Správny úsek bude začínať na začiatku nejakého kladného úseku a končiť na konci nejakého kladného úseku.

Ďalšie úvahy teda mohli sledovať, kedy sa nám oplatí prepojiť dva kladné úseky, aj keď sú oddelené úsekom záporným. Netreba však vymýšľať ťažké podmienky, môžme si napríklad pre každé číslo zistiť, aký najlepší výsledok vieme dosiahnuť, keď ním budeme končiť, s tým, že povolíme, aby tento výsledok bol nula, pokiaľ každý, ktorý končí našim číslom, bude záporný 2.

Tak sa nám úloha totiž zjednoduší, ak chceme výsledok končiaci nejakým číslom, bude to buď nula, alebo súčet tohto čísla s výsledkom pre predošlé číslo. Nakoniec si už stačí len všimnúť, že nepotrebujeme všetky medzivýsledky ukladať, ale stačí nám udržiavať si akési lokálne a akési globálne najlepšie riešenie.

Dostali sme sa teda k optimálnemu riešeniu s časovou zložitosťou \(O(n)\) a pamäťou \(O(1)\).

var i, n, locsum, globsum, locbegin, globbegin, globnum, curr   : int64;

begin
    //nacitame n a poinicializujeme vsetky premenne
    //na rozumne hodnoty, znamenajuce prazdny usek
    read(n);
    globsum := 0;
    globbegin := 1;
    globnum := 0;
    locbegin := 1;
    locsum := 0;

    //tu spracujeme vsetky cisla
    for i:=1 to n do begin
        read(curr);

        //k lokalnemu najlepsiemu vysledku priratame aktualne cislo
        locsum := locsum + curr;

        //ak sme dostali doteraz najlepsi vysledok
        if (locsum > globsum) then begin
            globsum := locsum;
            globbegin := locbegin;
            globnum := i - globbegin + 1;
        end

        //a ak mame zaporny lokalny vysledok, oplati sa nam namiesto
        //neho zacinat usek na nasledujucom cisle
        else if locsum < 0 then begin
            locsum := 0;
            locbegin := i+1;
        end;
    end;

    writeln(globbegin, ' ', globnum);
end.

Druhý prístup

Napriek tomu si ešte rozoberieme druhé, možno menej intuitívne, ale za to lepšie zovšeobecniteľné riešenie. Pozrieme sa, čo nám pomôže, ak si pre každú pozíciu vyrátame súčet čísel od začiatku po túto pozíciu. Takéto čísla budeme volať prefixové súčty. Keď sa nad tým zamyslíme poriadnejšie, súčet každého súvislého úseku vieme popísať rozdielom dvoch prefixových súčtov.

Ak by sme takto chceli spočítať najväčší súčet, ktorý končí na nejakej nami určenej pozícii, stačí nám zistiť, aký najmenší prefixový súčet sme videli naľavo od seba, lebo najväčší výsledok dostaneme samozrejme, pokiaľ od nášho nemenného čísla odčítame čo najmenšie číslo.

Čo teda spravíme: Prejdeme pole zľava doprava, budeme si počítať prefixové súčty a pamätať si doteraz najmenší videný prefixový súčet a doteraz najlepší videný výsledok. Ten prípadne upravíme, ak je rozdiel nášho aktuálneho prefixového súčtu a najmenšieho videného súčtu lepší, ako najlepší doterajší výsledok. Zložitosti budú rovnaké ako v predošlom prístupe.

var i, n, minprefix, minend, bestsum, bestbegin, bestnum    : int64;
    curr, currprefix                                        : int64;

begin
    read(n);
    bestsum := 0;       //najlepsi doteraz videny sucet useku
    bestbegin := 1;     //jeho zaciatok
    bestnum := 0;       //a pocet cisel v nom
    minprefix := 0;     //najmensi prefixovy sucet
    minend := 0;        //a kde konci
    currprefix := 0;    //aktualny prefixovy sucet

    //tu si spracujeme vsetky cisla
    for i:= 1 to n do begin
        read(curr);

        //upravime aktualny prefixovy sucet
        currprefix := currprefix + curr;
        
        //ak sme nasli novy najlepsi vysledok
        if (currprefix - minprefix) > bestsum then begin
            bestsum := currprefix - minprefix;
            bestbegin := minend + 1;
            bestnum := i - minend;
        end;

        //aktualizujeme najlepsi (najmensi) prefixovy sucet
        //rozmyslite si, ze ak by tato podmienka isla prva, vysledok
        //by bol stale spravny
        if currprefix < minprefix then begin
            minprefix := currprefix;
            minend := i;
        end;
    end;

    writeln(bestbegin, ' ', bestnum);
end.

  1. resp. nezáporných

  2. Vtedy predsa môžme zobrať prázdny úsek.

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