3. Kapustnica Trojstenu vzorové riešenie

3 11 2 4
01000010001

ano

3 11 2 4
01000000101

nie

Prvá vec, ktorú si treba uvedomiť pri riešení tejto úlohy je, že ak má čokoláda viac alebo menej horkých tabličiek ako je počet Trojstenákov, tak odpoveď je automaticky nie, pretože nevieme splniť všetky podmienky.

Pomalé riešenie

Asi najviac priamočiare riešenie je vyskúšať postupne všetky možné rozdelenia čokolády a skontrolovať, či v každom súvislom kúsku je práve jedna horká tablička. Takéto niečo vieme urobiť jednoduchou rekurziou. Začneme pri tom, že naša rekurzia odkrojí z čokolády súvislý kus, ktorý má \(l\) tabličiek. Akonáhle sme čokoládu rozdelili na \(n\) kusov – aby každý Trojstenák dostal jeden kus – skontrolujeme, či sú všetky podmienky splnené a či nám žiadna čokoláda nezvýši. Ak je všetko v poriadku, môžeme vypísať ano. Ak niektorá z podmienok splnená nie je, pokračujeme ďalej v rekurzii. Rekurzia bude rozdelovať čokoládu na kúsky s \(l\) až \(r\) tabličkami. Akonáhle sme prešli všetky možnosti ako sa dá čokoláda rozdeliť a ani raz sme nenašli riešenie, ktoré spĺňa všetky podmienky, vypíšeme nie.

Vzorové riešenie

Na vyriešenie tejto úlohy však nepotrebujeme zbytočne skúšať všetky existujúce možnosti. Pre každú horkú tabličku nás zaujíma, na akom indexe sa nachádza, aby sme vedeli odvodiť intervaly, v ktorých môžeme rozdeliť čokoládu, aby sme určite mali v každom kúsku práve jednu horkú tabličku. Preto si prejdeme celú čokoládu a zapíšeme si indexy horkých tabličiek do poľa \(h\). Na čokoládu pozeráme zľava doprava a počiatočný interval je \((0, 0)\), čo je na začiatku čokolády. Čísla v intervaloch ukazujú na miesta medzi dvoma tabličkami. Ak máme napríklad interval \((2, 5)\), tak čokoládu môžeme rozdeliť pred tabličkou na druhom indexe až za tabličkou na štvrtom indexe.

Vytvoríme si funkciu, ktorá pre každú horkú tabličku vypočíta interval, v ktorom sa môže rozdeliť čokoláda za danou tabličkou. Začiatok intervalu musí byť vždy aspoň o \(l\) väčší ako predchádzajúci začiatok intervalu, pretože najmenej \(l\) tabličiek môžeme oddeliť od zvyšku čokolády. Avšak, môže sa nám stať, že aj keby oddelíme kus čokolády s \(l\) tabličkami, tak medzi nimi nebude horká tablička. Takýmto možnostiam sa chceme vyhnúť, pretože hneď vieme, že nespĺňajú všetky podmienky a nemá zmysel s nimi ďalej pokračovať. V takomto prípade musí byť začiatok intervalu za horkou tabličkou. Takže začiatok intervalu sa dá napísať ako \(\max(\mathrm{zaciatok\_predchadzajuceho\_intervalu} + l, h[i] + 1)\).

Koniec intervalu musí byť vždy maximálne o \(r\) väčší ako koniec predchádzajúceho intervalu, pretože môžeme od čokolády oddeliť kus s maximálne \(r\) tabličkami. Môže však nastať situácia, kedy v týchto \(r\) tabličkách už bude aj druhá horká tablička, čo nechceme, pretože by sme nesplnili podmienky. Takže chceme čokoládu rozdeliť najviac pred nasledujúcou horkou tabličkou. Koniec intervalu preto vieme zapísať ako \(\min(\mathrm{koniec\_predchadzajuceho\_intervalu} + r, h[i + 1])\).

Aby kód fungoval poriadne, musíme si na koniec poľa \(h\) pridať aj index \(k\), čo je koniec čokolády, pretože to je najďalej, kde vieme rozdeliť čokoládu. Chceme sa vyhnúť tomu, že by sme chceli rozdeliť čokoládu za jej koncom, pretože toľko čokolády na rozdávanie nemáme.

Vždy, keď si vypočítame interval pre danú horkú tabličku, skontrolujeme či začiatok je menší alebo rovný koncu intervalu. Ak by bol začiatok väčší, tak môžeme rovno vypísať nie, pretože neexistuje miesto, kde by sme dokázali čokoládu rozdeliť, aby sme splnili všetky podmienky.

Úplne na koniec nás zaujíma posledný interval. Ak koniec tohoto intervalu je menší ako celková dĺžka čokolády \(k\), tak Naďka nevie rozdať celú čokoládu a vypíšeme nie. Ak však prešlo hladko a nestretli sme sa so žiadnym problémom, môžeme vypísať ano, pretože sme splnili všetky podmienky a každý Trojstenák dostal svoj kus čokolády, bez toho, aby Naďke nejaká zvýšila.

Časová a pamäťová zložitosť

Na začiatku sme prešli celú čokoládu, aby sme zistili, na akých indexoch sú horké tabličky – \(O(k)\). Potom sme \(n\)-krát vypočítali interval rezu – \(O(n)\). Dokopy je teda časová zložitosť \(O(k + n)\).

Pamätáme si čokoládu a nejaké konštantne veľké premenné k tomu, takže pamäťová zložitosť je \(O(k)\).

import sys

n, k, l, r = map(int, input().split())
cokolada = input()

horke = list()
pocet_horkych = 0
interval = (0, 0)

def rez(interval, i):
    return (max(horke[i] + 1, interval[0] + l), min(horke[i + 1], interval[1] + r))

for i in range(k):
    if cokolada[i] == '1':
        pocet_horkych += 1
        horke.append(i)
# na koniec poľa nesmieme zabudnúť pridať koniec čokolády
horke.append(k)

if pocet_horkych != n:
    print('nie')
    sys.exit()

for i in range(n):
    interval = rez(interval, i)
    if interval[0] > interval[1]:
        print('nie')
        sys.exit()

if interval[1] < k:
    print('nie')
else:
    print('ano')