Druhá série začátečnické kategorie třicátého čtvrtého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Řešení úloh
- 34-Z2-1: Dýňová polévka
- 34-Z2-2: Podivná brigáda
- 34-Z2-3: Skládání krabic
- 34-Z2-4: Dělení království
34-Z2-1 Dýňová polévka (Zadání)
Při výpočtu je potřeba pamatovat si aktuální čas. Začínáme v čase S. Dále potřebujeme počítadlo na počítání polévek, které si Kevin dal.
Výpočet bude mít celkem N kroků. Na začátku k-tého kroku porovnáme aktuální čas s otevírací dobou k-tého stánku. Pokud je čas uvnitř uzavřeného intervalu otevírací doby, dá si Kevin polévku a aktuální čas zvýšíme o 10 sekund. Na konci každého kroku k času přičteme D sekund, protože tak dlouho Kevinovi trvá chůze k dalšímu stánku.
Po provedení všech N kroků budeme znát počet polévek, které si Kevin dal.
Časová složitost je lineární O(N), protože celý výpočet zvládneme provést na jeden průchod vstupu délky N.
34-Z2-2 Podivná brigáda (Zadání)
Jako obvykle si můžeme nejprve rozmyslet přímočarou simulaci – začneme v nulté minutě a pak vždy zadáme Kevinovi práci, má-li volno, a poté Sáře, má-li volno. „má-li volno“ můžeme kontrolovat tak, že si u Kevina i Sáry budeme pamatovat, kolik minut práce mají ještě před sebou a při přechodu na další minutu nenulová počítadla zmenšíme o jedna.
Tento algoritmus závisí na součtu délek úkolů; nedokázali bychom jej ukotvit pouze vůči počtu? Jsou-li úkoly dlouhé, algoritmus většinu času nedělá nic zajímavého, pouze snižuje počítadla zbývající práce. Můžeme tyto nezajímavé úseky přeskočit?
Pořiďme si opět pro každého brigádníka počítadlo, tentokrát ale s údajem, kdy bude mít aktuální úkol hotový. Je-li aktuální čas rovný počítadlu, má daný brigádník hotovo. Úkol zadáme tak, že do počítadla uložíme součet aktuálního času a délky úkolu. Teď snadno poznáme, kdy rychlejší z brigádníků skončí – ten s menším počítadlem. Můžeme tedy rovnou skočit v čase až na jeho hodnotu. Takto dosáhneme časové složitosti O(N), tedy lineární s počtem úkolů.
Pozor jen, že čas konce není ten, kdy dojdou úkoly, ale až se na posledním úkolu přestane pracovat.
Mimochodem, nepřipomíná vám tato úloha některou z druhé série minulého ročníku?
34-Z2-3 Skládání krabic (Zadání)
Hledáme takovou posloupnost krabic, kde následující krabice je ostře větší než předchozí. Takže vlastně hledáme nejdelší rostoucí podposloupnost (zkráceně NRP).
Pro nalezení NRP použijeme dynamické programování. Pro všechna k=1, 2, …, n najdeme nejdelší z těch rostoucích podposloupností, které končí k-tým číslem, a zapamatujeme si její délku. Je důležité, aby opravdu její poslední prvek bylo k-té číslo, abychom věděli, jaké prvky za ni jde připojit. Při hledání NRP pro vyšší indexy využijeme již spočítané informace pro nižší indexy. Tím ušetříme spoustu času.
Pořídíme si pole velikosti N. Hodnota v poli na k-tém prvku udává délku NRP končící k-tým číslem. Na začátku pole vyplníme jedničkami, protože je jisté, že existuje rostoucí podposloupnost délky 1 končící na indexu k (jednoprvková posloupnost obsahující jen k-té číslo).
Potom začneme pole vyplňovat od začátku. Pro každé k=1, …, n zjistíme, jestli lze k-té číslo ze vstupu připojit za některou už nalezenou NRP. Stačí projít všechny nižší indexy v poli i=1,…, k-1 a zjistit, jestli je k-té číslo větší než i-té.
Pokud k-té číslo můžeme za nějakou NRP připojit, tak zjistíme, jestli je tato rostoucí posloupnost delší než nejdelší už nalezená pro číslo k. Pokud je delší, uložíme její délku do pole na index k. Po průchodu všech už nalezených NRP budeme mít v poli na indexu k délku NRP končící k-tým číslem.
Toto provedeme pro celou vstupní posloupnost. Na konci projdeme vyplněné pole a najdeme největší hodnotu, což bude délka NRP pro celý vstup a zároveň řešení této úlohy.
Časová složitost algoritmu je kvadratická O(N2). Existuje i rychlejší řešení pro nalezení NRP, které běží v čase O(N log N). Kvadratické řešení ale je pro tuto úlohu dostačující.
34-Z2-4 Dělení království (Zadání)
Chceme naše města rozdělit mezi Arocha a Brocha tak, aby dvě města jednoho krále nesousedila. Uvědomme si, že jakmile jedno město přisoudíme Arochovi, musí všechna města, která jsou s tímto městem spojena cestou, patřit Brochovi. A to přesně budeme aplikovat i v našem řešení.
Začneme libovolným městem a přidělíme ho králi Arochovi. Všechna sousední města přidělíme Brochovi a umístíme si je do fronty. Následně z fronty města postupně vytahujeme a zpracováváme. Při zpracování se opět podíváme na všechny sousedy daného města. Pokud ještě nejsou přiřazeni, dáme je druhému královi, než jakému patří zpracovávané město, a také je přidáme do fronty na zpracování. Pokud už je sousední město přiřazeno, musíme zkontrolovat, že je přiřazené správně. Kdyby ne, znamená to, že města nelze rozdělit mezi naše dvě království. Pokud frontu vyprázdníme a některá města stále nejsou přiřazená, libovolné z nich přiřadíme a postupujeme odznovu.
Každému městu budeme hledat jeho sousedy nejvýše jednou. Po každé z cest projdeme nejvýše dvakrát, jednou v každém směru. Je-li počet měst N a počet cest M, bude celková časová složitost O(N+M).
Podobné úlohy se řeší často, mají proto ustálený popis. Naše města a cesty lze reprezentovat pomocí grafu. Chceme zjistit, zdali je graf bipartitní. Algoritmus, který byl výše popsán, je prohledávání do šířky. Více si o grafech a prohledávání do šířky můžete přečíst v kuchařce o grafech.