Zadanie

Jimi si nedávno kúpil nový herný počítač a jeho štúdium tým značne utrpelo. Je veľmi ťažké učiť sa, keď máte na výber z toľkých dobrých hier. Preto si vytvoril rozvrh, v ktorom má každú hodinu označenú ako pracovnú alebo hernú. Po čase hrania ale Jimiho prestalo baviť zabíjanie príšer a rozhodol sa splniť veľkú úlohu – zachráni princeznú ukrytú na hmlistom ostrove.

Hra však nepodporuje ukladanie počas plnenia misie a preto Jimi nemôže pracovať, kým nezachráni princeznú. Nechce si ale veľmi meniť rozvrh, preto len vyškrtne niektoré pracovné hodiny z rozvrhu tak, aby si vytvoril dostatočne dlhý súvislý úsek herného času na záchranu princeznej. Jeho štúdium je však už teraz riadne zanedbané, a preto chce obetovať čo najmenej zo svojho pracovného času.

Úloha

Jimiho rozvrh vyzerá ako jedna dlhá postupnosť znakov P a H, ktoré označujú pracovné a herné hodiny.

Jimi si vypočítal, že na záchranu princeznej bude potrebovať \(c\) hodín hry.

Vašou úlohou je zistiť, koľko najmenej hodín práce vie vyškrtnúť z rozvrhu tak, aby mal aspoň \(\mathbf{c}\) hodín hry v jednom kuse.

Môžete predpokladať, že herných hodín je v rozvrhu vždy aspoň \(c\).

Formát vstupu

V prvom riadku je číslo \(c\) – počet hodín potrebných na záchranu princeznej. V druhom riadku je rozvrh – reťazec znakov P a H dĺžky \(n\).

Pre vstupy platí \(1 \leq c \leq n \leq 1\,000\,000\).

Formát výstupu

Vypíšte jedno číslo – najmenší počet hodín práce, ktoré treba vyškrtnúť z rozvrhu. Výstup ukončite znakom nového riadku.

Príklad

Input:

3
PPHHPPPHPHPHPPP

Output:

2

Upravený rozvrh vyzerá takto: PPHHPPPHHHPPP.

Input:

4
HHPPPHHPPHHHPH

Output:

1

Input:

2
HHPPHPP

Output:

0

Predstavíme si dve riešenia: riešenie hrubou silou a optimálne riešenie.

Hrubá sila \(O(n^2)\)

Príklad vieme vyriešiť veľmi jednoducho vyskúšaním všetkých možných začiatkov záchrany: Spočítame, koľko hodín práce by musel Jimi preskočiť, keby začal so záchranou práve v \(i\)-tu hodinu. Zo všetkých \(i\) vyberieme také, kedy je počet preskočených hodín práce minimálny.

Počet preskočených hodín spočítame tak, že v cykle prejdeme vstupné pole od \(i\)-tej hodiny, pričom si budeme počítať počet prejdených P a H. Ak dosiahneme počet H rovný \(c\), dosiahli sme potrebný počet hracích hodín a počet P je počet obetovaných pracovných hodín. Stačí teda počet P porovnať s doterajším minimom a ak je menší, našli sme nové minimum.

Keď od hodiny \(i\) po koniec rozvrhu ostáva menej ako \(c\) hodín, vypíšeme najmenší počet vynechaných P.

Keďže pre každý začiatok môžeme prejsť až na koniec poľa, časová zložitosť je \(O(n^2)\).

Optimálne riešenie \(O(n)\)

Môžeme si všimnúť, že v predošlom riešení robíme množstvo práce viackrát. Ak totiž poznáme počet P-čok (označme ho \(p_i\)) v úseku začínajúcom na \(i\), tak vieme, že počet P-čok v úseku začínajúcom na \(i+1\) nemusí byť veľmi odlišný. Mohli by sme teda zvýšiť \(i\) na \(i+1\) a nezačať počítať P a H od \(i+1\) ale rovno od \(i + c + p_i\) (teda odtiaľ, kde sme skončili prechod poľa pre predošlé \(i\)), kým nedosiahneme potrebný počet H-čok.

My budeme postupovať podobne, akurát teraz nebudeme skúšať všetky začiatky, ale prejdeme cez všetky konce.

Budeme sa teda vždy pozerať na časť poľa, ktorá je určená začiatkom a koncom1. Tiež si udržiavame počet P a počet H v tejto časti poľa.

Začneme so začiatkom aj koncom na prvom políčku poľa. V každom kroku cyklu posunieme koniec úseku o jedno políčko ďalej. Kým je počet H v našom úseku väčší alebo rovný \(c\), posúvame začiatok úseku doprava. Tým dosiahneme najkratší úsek s týmto koncom, ktorý má aspoň \(c\) H-čok. Keďže je najkratší, má aj minimálny počet P-čok. Počet P-čok porovnáme s medzivýsledkom a zapamätáme si menší.

Po prechode poľom vypíšeme minimum.

Každé políčko poľa sme navštívili raz koncom a najviac raz začiatkom, teda celková časová zložitosť je \(O(n)\).

#include <iostream>
#include <algorithm>

using namespace std;

int main () {
    int c;
    string vstup;

    cin >> c;
    cin >> vstup;
    int n = vstup.size();

    int zaciatok = 0;
    int H = 0, P = 0;
    int vysledok = n;
    
    for (int koniec = 0; koniec < n; koniec++) {
        if (vstup[koniec] == 'P') {
            P++;
        } else {
            H++;
        }
        
        while (H >= c && zaciatok < koniec) {
            vysledok = min(P, vysledok);
            if (vstup[zaciatok] == 'P') {
                P--;
            } else {
                H--;
            }
            zaciatok++;
        }
    }
    cout << vysledok << endl;
    return 0;
}

  1. Prístup, ktorým vyriešime túto úlohu sa nazýva “dvaja bežci” – jeden ukazuje na začiatok, druhý na koniec a postupne nimi prejdeme pole.↩

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