7. Nečakaný výlet vzorové riešenie

3 3
1 4
2 3
2 8

1

3 2
1 4
4 9
6 14

2

Bruteforce

Prvý prístup, ktorý by nám mohol napadnúť je prechádzať postupne všetkými dňami a v každom sa pozrieť, koľko ľudí má vtedy voľno. Ak je ich \(x\), potom vtedy vieme vybrať \(\binom x k\) skupín. Keď však toto naimplmenetujeme, dostaneme od testovača verdikt nesprávna odpoveď. Prečo? Ak má totiž nejaká skupina prienik viac než jeden deň, započítame ju viackrát, čo nechceme.

Prvý spôsob ktorý by nám mohol napadnúť na riešenie tohoto problému je si už zarátané skupiny do set-u a opäť ich už tak nerátať. Toto by určite fungovalo, ale akú by to malo časovú zložitosť? Označme si \(L=\max b_i\). Potom v každom dni môžeme mať až \(n\) ľudí s voľnom a tak až \(\binom n k\) skupín. Každú z nich musíme vygenerovať a vyskúšať, či sa nachádza v set-e. A dní je \(L\), teda celková časová zložitosť je \(O(L k \binom n k)\). To je jedna z najhnusnejších zložitostí, čo som kedy videl a samozrejme za ňu náš program nedostane žiadne body.

Dačo rozumnejšie

Tak teraz by to asi chcelo nad úlohou sa skutočne zamyslieť a nie len do nej búchať dátovými štruktúrami. Chceli by sme teda vymyslieť spôsob, ako každú skupinu priradiť jedinému dňu. Asi najprirodzenejší a najjednoduchší spôsob je si jednoducho vybrať prvý deň jej prieniku.

Tento deň bude ale jednoducho posledný zo začiatkov intervalov voľna. To znamená, že túto skupinu zarátame keď narazíme na posledného.

Nový algoritmus je teda takýto: Prechádzame si postupne dňami a udržiavame si počet momentálne aktívnych intervalov (teda ľudí, ktorí momentálne majú voľno). Vždy keď narazíme na začiatok nového intervalu, zvýšime odpoveď o \(\binom x {k-1}\), kde je \(x\) je počet aktuálne platných intervalov (mimo tohoto nového) – skupinu vieme vytvoriť z tohoto nového človeka a ľubovoľných \(k-1\), ktorých sme už videli.

Takéto riešenie bude mať časovú zložitosť \(O(n + L)\) – každého človeka spracujeme len dvakrát pri zmene počtu aktívnych intervalov a raz pri prepočítavaní odpovede. Pamäťová bude tiež \(O(n + L)\), keďže si potrebujeme pre každý deň predpočítať, ktoré intervaly v ňom začínajú a končia.

Odbočka: kombinačné čísla

V odhade časovej zložitosti sme sa tvárili, že kombinačné čísla vieme počítať v konštantnom čase. Ako však na to? Použijeme klasický vzorček \(\binom a b = \frac{a!}{b!(a-b)!}\). Prvým krokom bude predpočítať si faktoriály čísel do \(n\) (evidentne \(a, (a-b) \leq n\)). Avšak delenie vo zvyškovej triede tiež nie je triviálne. Hľadanie modulárneho inverzu https://www.ksp.sk/kucharka/modularna_aritmetika/. V tomto kontexte je síce korektné povedať, že to je konštanta, keďže modulo je konštantné, avšak ide to aj lepšie.

Všimnime si, že jediné čísla, ktorými delíme sú faktoriály, ktoré máme predpočítané. A keďže je ich rozumne málo – \(O(n)\) – môžeme si k nim predpočítať aj inverzy v \(O(n \log \text{MOD})\) a tak naozaj vedieť kombinačné čísla počítať v konštantnom čase.

Optimálne riešenie

Od predošlého riešenia nám ku vzorovému chýba iba kúsok. Všimnime si, že v dňoch kde nezačína ani nekončí žiadny interval nič nerobíme a tak nám nič nepokazí, ak ich proste preskočíme. Tomuto sa hovorí zametanie – zoberieme si udalosti, ktoré nás zaujímajú, zoradíme si ich a prechádzame len nimi.

Postup je teda jednoduchý – zoberieme si všetky začiatky a konce intervalov, zoradíme si ich podľa času a spracovávame ich v takomto poradím.

Takéto riešenie má časovú zložitosť \(O(n \log n)\) – udalosti potrebujeme zoradiť podľa času. Pamäťová zložitosť je \(O(n)\).