1. Pohodový festival vzorové riešenie

Zadanie

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Žabe na

Leto sa blíži a s ním aj Sysľov obľúbený hudobný festival. Tak ako každý rok, aj teraz naň príde veľa skvelých kapiel, ktoré by si Syseľ rád vypočul. Bohužiaľ, nedá sa stihnúť všetko, pretože jednotlivé koncerty sa prekrývajú. Aby však maximalizoval svoj hudobný zážitok, chcel by ich Syseľ stihnúť čo najviac. Viete mu poradiť, ktorých koncertov sa má zúčastniť?

Úloha

Festival začína v čase 0 a uskutoční sa na ňom niekoľko koncertov. Každý koncert má pevne určený čas začiatku a čas konca. Samozrejme, každý koncert skončí neskôr ako začal a začiatok ani koniec sa nebudú posúvať¹. Inak sa však koncerty môžu ľubovoľne prekrývať.

Keď si Syseľ vyberie niektorý koncert, chce sa ho zúčasniť celého. Nemôže teda počas neho odísť na nejaký iný koncert. Ak však nejaké vystúpenie končí v ten istý čas ako začína iné, Syseľ vie stihnúť oba koncerty. Naviac nemá žiadne preferencie, takže jeho cieľom je naozaj iba maximalizovať počet koncertov, ktorých sa zúčastní.

Predstavme si, že na festivale sú 4 koncerty – koncert A začína v čase 1 a končí v čase 10, koncert B začína v čase 12 a končí v čase 17, koncert C začína v čase 6 a končí v čase 14 a koncert D začína v čase 17 a končí v čase 20. Vidíme, že najlepšie, čo vie Syseľ spraviť je ísť na koncerty A, B a D. Koncert C sa totiž prekrýva s koncertom A aj B a ak by naň Syseľ išiel, stihol by najviac jeden ďalší koncert (D).

1. (3 body) Syseľ sa rozhodol vyberať si koncerty nasledovným spôsobom – ako na prvý ide na koncert, ktorý začína čo najskôr. Následne vždy keď skončí koncert, na ktorom je, ponáhľa sa na koncert s najbližším začiatokm.

   V našom príklade teda ide na koncert A. Ten skončí v čase 10. Koncert C je vtedy v plnom prúde a Syseľ ho už nestíha. Najbližšie začína koncert B a Syseľ sa ho zúčastní. Keď v čase 17 skončí aj ten, Syseľ si všimne, že ešte stíha začiatok koncertu D a preto sa tam ponáhľa. Po konci koncertu D sa už žiaden ďalší nekoná a Syseľ ide domov.

   Takýto spôsob vyberania koncertov je však chybný. Vytvorte taký zoznam koncertov (s ich začiatkami aj koncami), že opísaný postup na nich nenájde najlepšie možné riešenie. Na vašom príklade tiež ukážte, aké riešenie nájde popísaný postup a vysvetlite, prečo toto riešenie nie je optimálne.

2. (4 body) Po neúspechu z podúlohy a) prišiel Syseľ s novou metódou. Najskôr si pre každý koncert vypočíta, s koľkými inými koncertami sa prekrýva. Následne si vyberie koncert s najmenším počtom prekryvov. Zo zoznamu koncertov vymaže tento vybraný koncert a aj všetky koncerty, s ktorými sa prekrýval (a ktorých sa teda nebude môcť zúčastniť). No a opísaný postup (aj s počítaním prekryvov) opakuje na zvyšných koncertoch, až kým ich všetky nevyškrtá.

   V našom príklade si teda spočíta, že koncerty A a B majú 1 prekryv, koncert D má 0 prekryvov (koncerty B a D sa neprekrývajú) a koncert C má 2 prekryvy. Vyberie si preto koncert D a vyhodí ho zo zoznamu koncertov (a iba ten, pretože sa s ničím neprekrýva). Ostali mu tri koncerty, s počtom prekryvov 1, 1 a 2.

   Keďže mu nezáleží na tom, ktorý z koncertov s 1 prekryvom si vyberie, vyberie si napríklad koncert A. Zo zoznamu koncertov teda musí vyhodiť koncert A, ale aj koncert C, s ktorým sa A prekrýval. Ostal mu už len jeden koncert B a toho sa teda tiež zúčastní.

   Aj tento spôsob je však chybný. Vytvorte taký zoznam koncertov (s ich začiatkami aj koncami), že opísaný postup na nich nenájde najlepšie možné riešenie. Na vašom príklade tiež ukážte, aké riešenie nájde popísaný postup a vysvetlite, prečo toto riešenie nie je optimálne.

3. (8 bodov) Sysľa už nič ďalšie nenapadlo, preto je na vás aby ste vymysleli postup, ktorým má Syseľ vyberať koncerty tak, aby ich vybral najväčší možný počet. Vo svojom riešení popíšte algoritmus – teda postupnosť krokov a pravidiel, ktoré určia, ktorých koncertov sa má Syseľ zúčastniť. Tento postup má pritom fungovať bez ohľadu na to, kedy začínajú a končia jednotlivé koncerty a koľko týchto koncertov je. Ak existuje viacero rovnako dobrých riešení, je jedno, ktoré z nich váš postup nájde.

   Dôležitou časťou vašeho riešenia musí byť aj dôkaz správnosti. Skúste popísať, prečo je vaše riešenie správne a prečo vždy nájde správnu odpoveď. Pokúste sa vyhnúť tvrdeniam "Na týchto koncertoch to funguje..." a "V takomto prípade to bude správne...". Namiesto toho vysvetlite, prečo vždy, keď váš algoritmus vyberie nejaký koncert, tak tým nič nepokazí bez ohľadu na to, ako sú umiestnené zvyšné koncerty.

---

1. Ani keby diváci žiadali prídavok akokoľvek úpenlivo.↩

Podúloha a)

V tomto prípade je situácia veľmi jednoduchá. Lebo bez ohľadu na to ako umiestnime naše koncerty, tak je jasné, na ktorý z nich Syseľ pôjde – na ten, čo začína najskôr. Chceli by sme preto Sysľa za tento výber potrestať. No a nie je nič ľahšie, ako ho už na žiadny ďalší koncert nepustiť, čo môžeme docieliť tak, že koncert, ktorý začína ako prvý, skončí ako posledný. Tým pádom vieme počas trvania tohto predstavenia usporiadať veľké množstvo kratších koncertov, ktoré sa navzájom neprekrývajú a teda keby sa ich Syseľ zúčastnil, bol by spokojnejší.

Podúloha b)

Syseľ si vyberá koncerty podľa toho, s koľkými inými koncertami sa prekrývajú. A snaží sa tvrdiť, že ak zakaždým pôjde na ten, ktorý sa prekrýva s najmenším množstvom iných koncertov, určite ich navštívi najväčší možný počet.

Ak sa snažíme vymyslieť protipríklad, je to o niečo zložitejšie ako v podúlohe a), pretože to ako rozmiestnime koncerty ovplyvňuje Sysľov výber. Najlepšie je naozaj si zobrať papier a pero a skúšať rôzne možnosti. Dobrý prístup môže byť zvoliť si jeden koncert (označme si ho \(A\)), ktorý bude mať najmenší počet prekryvov. Následne sa snažiť dokresliť ostatné tak, aby sa viac oplatilo neísť na koncert \(A\).

Pritom nám môžu pomôcť ešte dve pozorovania. Ak sa nejaké koncerty odohrávajú napravo od koncertu \(A\) (neskôr), tak symetricky s nimi môžeme to isté robiť aj naľavo. Koncert \(A\) sa teda stane stredom našeho riešenia. Takýto postup nám zjednoduší hľadanie protipríkladu a intuitívne sa zdá, že nám to nič nepokazí.

No a nakoniec ešte musíme vyriešiť to, aby mal koncert \(A\) naozaj najmenej prekryvov. K tomu nám vie pomôcť to, že vieme vytvoriť veľké množstvo koncertov, ktoré sa odohrávajú v ten istý čas. Ich úlohou bude naozaj iba umelo nafúknuť počet prekryvov pre nejaký iný koncert.

Jedno možné riešenie môže vyzerať takto:

Všimnime si, že Syseľ si najskôr vyberie koncert \(A\), ktorý má iba dva prekryvy. Potom ho prestane uvažovať, spolu s koncertami \(C_1\) a \(C_2\), ktoré sa s ním prekrývajú. No a potom postupne vyberie napríklad koncerty \(B_1\) a \(B_2\). Zúčastní sa teda iba troch koncertov – \(A\), \(B_1\) a \(B_2\).

Ak by však nešiel na koncert \(A\), mohol by sa zúčastniť až štyroch koncertov – \(B_1\), \(C_1\), \(C_2\) a \(B_2\).

Podúloha c)

Oba Sysľove pokusy boli neúspešné, musíme preto prísť s nejakým iným riešením. Prekvapivo, správne riešenie vôbec nie je ťažké a naviac je pomerne intuitívne. Pokúsme sa naň spoločne prísť.

Predstavme si nejaký zoznam koncertov, ktoré sa v daný deň majú konať na festivale. Na žiadny z nich zatiaľ nepoďme, skúsme čakať a sledovať čo sa stane. Postupne niektoré z týchto koncertov začnú. Nechceme sa však riadiť podľa času kedy začínajú, lebo ako sme videli v podúlohe a), tak to neviedlo k dobrému riešeniu. V nejakom momente však prvý z koncertov skončí, označme si ho písmenom \(A\).

A toto je presne moment, v ktorom sa chceme zamyslieť nad tým, či sme sa koncertu \(A\) nechceli zúčastniť. Zoberme si ľubovoľné optimálne riešenie. Teda také, v ktorom Syseľ navštívy najväčší možný počet koncertov. V tomto riešení sa Syseľ zúčastní niektorého koncertu ako prvého – nech je to koncert \(B\).

Ak by \(B\) začínal neskôr ako končí koncert \(A\), naše riešenie by nebolo optimálne. Mohli by sme k nemu totiž pridať koncert \(A\), ktorý by sa určite s ničím neprekrýval, keďže \(B\) bol v tomto riešení prvý koncert a \(A\) končí skôr ako začína \(B\). Týmto pridaním by sme však dostali ešte lepšie riešenie, čo je nemožné, lebo naše vybrané riešenie bolo optimálne.

V každom správnom riešení teda platí, že prvý koncert, ktorého sa Syseľ zúčastni (\(B\)) začne skôr ako skončí koncert, ktorý končí ako prvý (\(A\)). To ale znamená, že koncert \(B\) nemôže skončiť skôr ako koncert \(A\). No a všetky zvyšné koncerty v tomto optimálnom riešení začínajú až potom ako skončí koncert \(B\) (lebo sa s ním neprekrývajú) a teda všetky začínajú aj po skončení koncertu \(A\). V tomto momente si môžeme uvedomiť, že v našom riešení môžeme nahradiť koncert \(B\) koncertom \(A\) a naše riešenie sa určite nepokazí a bude obsahovať rovnaký počet koncertov, teda bude rovnako dobré.

Táto úvaha vedie k veľmi jednoduchému riešeniu. Syseľ si vyberie koncert, ktorý končí ako prvý a tohto koncertu sa zúčastní. Následne vyškrtne tento koncert a aj všetky, ktoré sa s ním prekrývajú, lebo sa ich už nebude môcť zúčastniť. Na zvyšné koncerty potom použije vyššie uvedenú myšlienku a teda si opäť vyberie najskôr končiaci koncert, ktorého sa zúčastní. Takto bude pokračovať, až kým nevyškrtne všetky koncerty.

Toto riešenie je pomerne intuitívne preto, lebo čím skôr skončí koncert, na ktorom sa Syseľ nachádza, tým viac času mu ostane na návštevu zvyšných koncertov. Takéto riešenie voláme “pažravé” (po anglicky greedy). Ako ste však videli v podúlohách a) a b), pri vymýšľaní takýchto riešení si musíte dať pozor, aby ste sa nenechali okmalať zdanlivo dobrou úvahou a svoju myšlienku si vždy overte tak ako v podúlohe c) – porovnaním s ľubovoľným optimálnym riešením.