4. Taký neporiadok! vzorové riešenie

2

5 4
1 -5
1 -3
0 0
1 2
1 3

9 -5
0 -4
1 -1
1 1
1 1
0 2
1 3
0 4
1 7
1 10

24
31

Na začiatok sa zbavme nezaujímavého prípadu: ak neexistuje žiaden kôš, tak Kubo vo svojej misii neuspeje. Vypíšeme preto -1. Ďalej predpokladáme existenciu koša.

Kubove upratovanie vyzerá nasledovne – najprv sa presunie k nejakému odpadku, a zdvihne ho. Potom sa presunie ku košu, a odpadok hodí do koša. Toto sa opakuje, kým existujú odpadky.

Zoberme si ľubovoľný odpadok. Zaujímavé sú najlbižší kôš naľavo (\(L\)), a najbližší kôš napravo (\(R\)). Zrejme nemá zmysel hádzať ten odpad do niektorého iného koša – cestou k nemu by sme ho vedeli zahodiť do \(L\) alebo \(R\).

Dostávame jednoduché riešenie v časovej zložitosti \(O(n! \cdot 2^n)\), kde \(n\) je počet odpadkov (nie košov) – vyskúšame všetky možné poradia, v ktorých mohol Kubo zahodiť odpadky, a pre každý odpadok máme dve možnosti, kam ho mohol zahodiť. Toto riešenie bolo hodnotené \(6\) bodmi.

Typy odpadkov

Pre jednoduchosť zatiaľ predpokladajme, že Kubo začína na pozícii, kde sa nachádza kôš. Potom pre každý odpadok vieme sledovať Kuba, ako ho zahadzuje. To pozostáva z dvoch častí – cesta od koša k odpadku, a cesta od odpadku k (nie nutne tomu istému) košu. Pre každý odpadok máme preto štyri možnosti, ako môže vyzerať jeho cesta do koša.

1. Kubo začne v koši, ktorý je najlbižšie naľavo, a odpadok hodí do toho istého koša. Teda Kubo začne aj skončí v koši \(L\).
2. Kubo začne aj skončí v najbližšom koši napravo od odpadku (\(R\)).
3. Kubo začne v \(L\) a skončí v \(R\).
4. Kubo začne v \(R\) a skončí v \(L\).

Podľa týchto štyroch prípadov budeme rozlišovať odpadky typu \(1\), \(2\), \(3\) a \(4\). Všimnime si, že keď Kubo navštívi akýkoľvek kôš, tak môže rovno poupratovať všetky odpadky typu \(1\) a \(2\), ktoré sa k tomu košu vzťahujú.

Načo 3 a 4?

Povedzme, že máme odpadok, ktorý je od ľavého koša vzdialený \(l\) a od pravého koša \(r\). Ak je typu \(1\), tak poupratovať ho nás bude stáť \(2l\) času, pre typ \(2\) zas \(2r\) času. V prípade \(3\) a \(4\) nás bude stáť \(l + r\) času. Ľahko vidíme, že ak by sme sa na to pozerali iba takto, tak prípady \(3\) a \(4\) sa vôbec neoplatia – vždy je jeden z prípadov \(1\) alebo \(2\) aspoň rovnako časovo dobrý, ak nie lepší.

Prípady \(3\) alebo \(4\) majú ale jednu výhodu – umožňujú nám presúvať sa medzi košmi. Bez nich by sme sa museli presúvať tak, že by sme pri presune nezahodili žiaden odpadok, čo by bola strata času.

Oplatí sa prechádzať tam a späť veľakrát?

Každé dve susedné koše nám určujú úsek odpadkov. Zrejme ak je najľavejší úsek prázdny, môžeme ho ignorovať. Podobne pre najpravejší úsek. Budeme ďalej predpokladať, že posledné úseky v oboch smeroch obsahujú aspoň jeden odpadok.

Zamyslime sa nad tým, či sa nám vôbec niekedy oplatí prejsť úsekom viac ako dvakrát. Napríklad prvýkrát zľava doprava, potom sprava doľava a nakoniec zľava doprava. To znamená, že Kubove upratovanie vyzerá nasledovne.

1. Kubo upratuje a časom sa dostane ku košu \(L\).
2. Kubo sa presunie z \(L\) do \(R\). Pritom možno zahodí odpadok typu \(3\).
3. Kubo upratuje a časom sa dostane späť ku košu \(R\).
4. Kubo sa presunie z \(R\) do \(L\). Pritom možno zahodí odpadok typu \(4\).
5. Kubo upratuje a časom sa dostane späť ku košu \(L\).
6. Kubo sa presunie z \(L\) do \(R\). Pritom možno zahodí odpadok typu \(3\).
7. Kubo upratuje ďalej.

Namiesto takéhoto postupu mohol zvoliť ale tento, efektívnejší: spraví \(1\) a \(5\), potom spraví \(2\), a nakoniec spraví \(3\) a \(7\).

Pritom sme ale vynechali dve odpadky, ktoré Kubo zahodil v \(4\) a \(6\). Každý z nich ale vieme zahodiť do toho koša, ku ktorému je bližšie:

Ak je odpadok bližšie k \(L\) (\(l \leq r\)), tak Kubo ho zodvihne a zahodí v prvej časti upratovania (pred presunom doprava). Toto nás stojí čas \(2l\), čo je aspoň tak dobré, ako v pôvodnom upratovacom pláne – tam nás to stálo \(l + r\).

Ak je odpadok bližšie k \(R\), tak ho Kubo zodvihne a zahodí v druhej časti upratovania (po presune doprava).

Vidíme teda, že nemá zmysel prechádzať viac ako dvakrát. Takže každý úsek prejdeme buď \(2\)-krát, \(1\)-krát, alebo \(0\)-krát (začneme aj skončíme na jednom konci, bez toho, aby sme niekedy prešli na druhú stranu).

Kubove možnosti

Z horeuvedeného vyplýva, že Kubovo upratovanie musí vyzerať naslovne.

1. Začne pri koši, potom jedným smerom prejde všetky úseky v tom smere.
2. V poslednom z tých úsekov sa otočí – nemusí ho teda prejsť celý. (Predchádzajúce úseky musel prejsť celé, inak by nemohol pokračovať v smere. Za posledným úsekom ale už nič nie je, preto ho nemusí prejsť celý.)
3. Prejde všetky úseky v druhom smere.
4. Posledný úsek nemusí prejsť celý, z rovnakých dôvodov, aké sú uvedené v druhom kroku.

Máme teda štyri triedy úsekov:

1. Najľavejší úsek (ak začiatočný kôš nie je úplne vľavo).
2. Iné úseky naľavo od začiatočného koša.
3. Najpravejší úsek (ak začiatočný kôš nie je úplne vpravo).
4. Iné úseky napravo od začiatočného koša.

Kubovo upratovanie každej triede priradí typ podľa toho, akým spôsobom tento úsek prejde. Typy sú nasledovné:

1. Úsek bol prejdený práve raz (niektorým smerom, nezáleží na tom, ktorým). Pre takýto úsek vieme ľahko zistiť najlepší spôsob, akým pozbierať všetky odpadky v ňom – všetky odpadky okrem jedného budú typu \(1\) alebo \(2\), a posledný odpadok bude použitý na presun. Bude teda typu \(3\) alebo \(4\), a je zvolený tak, aby trvalo upratanie úseku čo najkratšie.

2. Úsek bol prejdený dvakrát. Najlepšie možné upratanie vieme zistiť podobne, ako v predchádzajúcom prípade, až na to, že až dve odpadky použijeme na presun.

3. Úsek nebol prejdený ani raz, a navštívili sme preto iba jeho ľavý koniec. Všetky odpadky v úseku musia byť typu \(1\), a vieme preto zistiť celkový čas potrebný na upratovanie.

4. Úsek nebol prejdený ani raz, a navštívili sme iba jeho pravý koniec. Všetky odpadky v úseku musia byť typu \(2\), a ľahko spočítame celkový čas potrebný na upratovanie.

Možností, ako môže Kubovo upratovanie vyzerať, je \(8\) – určujeme iba smer, ktorým sa na začiatku vydá, typ najľavejšieho úseku a typ najpravejšieho úseku. Pre každú možnosť vieme zistiť trvanie upratovania v čase \(O(n)\).

Čo keď Kubo nezačína pri koši?

Začiatok upratovania je nasledovný – Kubo sa presunie k odpadku, ktorý je v rovnakom úseku ako on, potom sa presunie k niektorému koncu úseku, a odpadok hodí do koša. Tým zahodil jeden odpadok a presunul sa k niektorému košu – od tohto momentu by sme vedeli použiť predchádzajúci postup.

Vyskúšame dve možnosti podľa toho, do ktorého z krajných košov odpadok zahodí. Zahodenie jedného odpadku v začiatočnom úseku ovplyvní iba cenu (čas potrebný na upratanie) tohto úseku. Vyskúšame všetky možné voľby prvého zahodeného odpadku – v každej voľbe vieme rýchlo v čase \(O(1)\) vypočítať vplyv na čas potrebný na upratanie úseku. Spomedzi všetkých možných volieb vyberieme tú cenovo najlacnejšiu.

Tento (všeobecný) prípad časovú zložitosť riešenia neovplyvní – tá ostane \(O(n)\).