\begin{yl}{3}{Kummalised kapivargad}{kapp}{1 sek / 3 sek}{40 punkti}
\emph{Idee: Rocco Liiva, teostus ja lahenduse selgitus: Sandra Schumann}

\begin{quote}
  Antud on numbritest $0$ kuni $9$ koosnev jada pikkusega $M$ ja arv $N$. Kui palju osa\-jadasid pikkusega $N$ saab koostada esialgsest jadast, kui igast järjestikuste võrdsete numbrite plokist peab osajadas olema vähemalt üks number? Vastuse võib anda mooduli $2^31$ järgi.
\end{quote}

Sellele ülesandele on võimalik läheneda järk-järgult. Vaatame esimest alamülesannet:

\begin{quote}
  Vastus on alati $0$ või $1$.
\end{quote}

See tähendab, et peame leidma, kas osajada pikkusega $N$ on võimalik antud tingimustel moodustada. See on võimatu kahel juhul. Üks on see, et $N$ on suurem kui $M$. Teine on see, et jadas on numbriplokke rohkem kui $N$. Ehk siis esimese alamülesande jaos piisab lahendusest, mis kontrolib, et $N$ pole suurem kui jada pikkus ega väiksem kui numbriplokkide arvu.

Jätkame teise alamülesandega:

\begin{quote}
  Jada koosneb ainult numbritest $0$ ja $1$, kusjuures nullid on enne ühtesid.
\end{quote}

Nüüd peame mõtlema, kui palju erinevaid osajadasid on võimalik moodustada jadast kujul \verb'0'\ldots\verb'01'\ldots\verb'1'. Kindlasti peab lõplikus jadas olema \verb'0', kui algses on vähemalt üks \verb'0', ja \verb'1', kui algses on vähemalt üks \verb'1'. Võime seda võtta nii, et kummastki plokist on vaja võtta vähemalt üks number. Ülejäänud osajadas olevad numbrid saab võtta nullide ja ühtede seast vastavalt nende olemasolule. Võime alustuseks võtta osajadasse kõikideks ülejäänud numbriteks \verb'0' (kui nulle piisavalt palju on) ja hakata nullide arvu järjest vähendama, kuniks neid jääb alles vaid üks või algsest jadast number \verb'1' otsa saab.

Mõtleme nüüd kolmanda alamülesande peale:

\begin{quote}
  $N, M \le 20$
\end{quote}

Siin alamülesandes on arvud $N$ ja $M$ piisavalt väikesed, et oleks võimalik kõik juhud läbi proovida. Üks võimalus seda teha on nii: igast numbriplokist on osajadasse vaja võtta vähemalt üks number. Võime luua rekursiivse funktsiooni, mis igast plokist võtab osajadasse esimese numbri ja iga järgmise numbri puhul vaatab rekursiivselt kaht varianti: sellist, kus number on osajadasse võetud, ja sellist, kus ei ole. Seejuures tuleb jälgida, et ka viimasest plokist jõuaks osajadasse vähemalt üks number. Niimoodi saadud osajadad võime duplikaatide eemaldamiseks kõik lisada ühte hulka (nt Pythoni \verb'set' või C++ \verb'unordered_set') ja lõpuks vaadata selle hulga suurust. Nii toimib näiteks lahendus \verb'sol_brute.py'.

Järgmine alamülesanne enam naiivse lähenemisega läbi ei lähe:

\begin{quote}
  Vastus on väiksem kui $2^{31}$.
\end{quote}

See alamülesanne on lisatud puhtalt selleks, et kui lahendajale on võõras sageli raskemates ülesannetes kasutatav idee, et arve võiks väljastada mingi mooduli järgi, siis oleks võimalik ikka märkimisväärne osa punkte kätte saada. Muus osas on tegemist sisuliselt täislahendust nõudva alamülesandega. Kuidas seda lahendada?

Eelmise alamülesande lahenduse suurim viga on see, et paljusid võimalikke osajadasid vaadatakse mitu korda. Lisaks ei ole meil mingit vajadust kõiki võimalikke jadasid meeles pidada: võime selle asemel lugeda kohe erinevate jadade arvu. Siinkohal tuleb appi dünaamiline plaanimine (DP).

Esimese asjana võime ignoreerida seda, mis konkreetsed sümbolid esinevad kogu jadas. Meid huvitab ainult see, kui mitu korda on sama numbrit järjest igas plokis. Kuna eri plokkides on eri numbrid ja igast plokist on lõplikus osajadas vähemalt üks number, siis pole vahet, kas vahelduvad plokid nullidest ja ühtedest või mingitest muudest numbritest --- lõplike osajadade arv sellest ei muutu. Seega loeme kokku lihtsalt plokkides olevate numbrite arvud.

Selle käigus saame ka kohe kontrollida, ega plokke pole rohkem kui $N$.

Mõned elemendid jadas on kohustuslikud: igast plokist vähemalt üks number. See jätab meile $N$ miinus plokkide arv vabu kohti, mida täita eri viisidel.

Edasi teeme järgmist: vaatame $i$-ndat plokki ja tahame teada, kui mitmel viisil saame me osajada alustada nii, et $j$ vaba kohta algusest loetuna oleks täidetud selles ja eelmistes plokkides olevate numbritega. $i$-ndast plokist on meil võimalik vabadele kohtadele panna minimaalselt $0$ numbrit (lisaks siis ühele kohustuslikule). Maksimaalselt võime aga täita kõik $j$ vaba kohta või siis nii palju, kui palju selles plokis (lisaks ühele kohustuslikule) veel numbreid on --- oleneb, kumb piir enne ette tuleb.

Tähistame võimalikku osajadade arvu, kus on täidetud esimesed $j$ kohta ning selleks kasutatud kuni $i$-ndat plokki kui $DP(j,i)$.
Siis: $$\begin{array}{lll}
DP(j,   & i) = \\
DP(j,   & i-1) + & \text{(st $i$-ndast plokist on lisatud $0$ numbrit)} \\
DP(j-1, & i-1) + & \text{(st $i$-ndast plokist on lisatud $1$ number)}  \\
DP(j-2, & i-1) + & \text{(st $i$-ndast plokist on lisatud $2$ numbrit)} \\
\ldots
\end{array}$$

Nii saame jätkata, kuni täidame kõik $j$ vaba kohta $i$-nda ploki numbritega või plokis olevad numbrid otsa saavad.

Valemist on näha, et DP tabeli iga veeru elemendid sõltuvad ainult eelmise veeru elementidest. Seega saame DP tabeli veergude kaupa täita ja siis väljastada vastusena tabeli viimase veeru viimases reas oleva elemendi. Nõnda toimib näiteks lahendus \verb'sol_dp.py', mis lahendab tegelikult ära ka viimase alamülesande.

Mõnes muus keeles võib aga komistada täisarvude ületäitumise otsa ning sellest ka viimane alamülesanne:

\begin{quote}
  Lisapiirangud puuduvad.
\end{quote}

Järjestikuste liitmiste tulemusena võivad meie tabelis olevad arvud minna väga suureks ning seetõttu ei pruugi nad enam ära mahtuda C++ ja teise sarnaste keelte andmetüüpide \verb'int', \verb'unsigned int', \verb'long long int' ega ka \verb'unsigned long long int' piiresse. Seetõttu tuleks iga kord kaht arvu kokku liites tulemus leida mooduli $2^{31}$ järgi. Paneme tähele, et selleks, et liitmise tulemus juba kohe ületäitumist ei tekitaks, võiks tabeli arvude andmetüübiks olla vähemalt \verb'unsigned int'.
Sellist lahendust võib lugeda näiteks failist \verb'sol_dp.cpp'.

Märkus. Tähelepanelik vaatleja avastab, et $2^{31}$ ei ole valitud juhuslikult --- kuna tegemist peaks olema lihtsama ülesandega, siis on antud moodul ja ülesande paljusid eri väljundeid lubav sõnastus valitud selliselt, et nii 32-bitise märgiga täisarvu kui ka suuremate 2-süsteemil põhinevate arvutüüpide loomuliku ületäitumise korral loetaks väljastatud vastus siiski õigeks. Kui moodul oleks midagi muud (näiteks rahvusvahelistel võistlustel populaarne $10^9+7$), oleks \verb'sol_dp.cpp' lahenduse ilmutatud kujul jääkide arvutamine hädavajalik.

\end{yl}
