Třetí série třicátého druhého ročníku KSP

Letošní vánoční číslo KSP, které je zároveň třetím číslem jubilejního 25-tého ročníku KSPčka, vám právě přistálo ve vaší schránce nebo na vašem monitoru. Opět jsme si pro vás připravili 5 vypečených úloh (z toho nějaké praktické) a k nim navíc pokračování datového seriálu. Seriál po dvou minulých dílech opouští OSM a bude si hrát s úplně novými daty – jízdními řády. Proto se nebojte do seriálu zapojit, i pokud vám OSM data nesedla. A závěrem tohoto čísla je kuchařka o tocích v sítích.

Připomínáme, že se z každé série stále započítává 5 nejlépe vyřešených úloh (tedy nemusíte vyřešit úplně všechny a i tak můžete dosáhnout na plný počet bodů). Také se vám body za úlohy přepočítávají podle vašeho služebního stáří – na přesnou definici se podívejte do pravidel na webu.

Za úspěšné řešení KSP můžete být přijati na MFF UK bez přijímacích zkoušek. Úspěšným řešitelem se stává ten, kdo získá za celý ročník (této kategorie) alespoň 50% bodů. Za letošní rok půjde získat maximálně 300 bodů, takže hranice pro úspěšné řešitele je 150. Maturanti pozor, pokud chcete prominutí využít letos, musíte to stihnout do konce čtvrté série, pátá už bude moc pozdě. Také každému řešiteli, který v tomto ročníku z každé série dostane alespoň 5 bodů, darujeme KSP propisku, blok, placku a možná i další překvapení.

Termín odeslání Vašich řešení této série jest určen na 24. února 2020 v 8:00. Řešení můžete odevzdávat jak elektronicky, tak klasickou poštou na známou adresu.

Dotazy ohledně zadání můžete posílat na adresu ksp@mff.cuni.cz, nebo se ptát přímo na diskusním fóru KSP.

Odměna série: Každému, kdo získá více než 3 body ze seriálu, pošleme sladkou odměnu.

Zadání úloh

Na konci minulého dílu jsme opustili Hefaistos s kolonisty na palubě uprostřed základny zasažené iontovou bouří. Postupně se začaly hroutit štítové emitory a bylo to na vašem hlasování, o co by se posádka měla pokusit. Vybrali jste volbu, že se mají pokusit vzlétnout a dosáhnout orbity.

* * *

„Všichni připoutat, nouzový start!“ křikla kapitánka přes vnitřní interkom. „Na můj povel odpojte externí štítové emitory. Hned potom chci maximální výkon do motorů. Tři… dva… jedna… teď!“

Následující sekundu se stala spousta věcí. Nejprve štítový generátor Hefaista dramaticky snížil svůj výkon, aby se vzápětí od trupu oddělily svorky s kabely doposud vedoucími k štítovým emitorům na okraji kolonie. Hned jak zmizela bariéra bránící iontové bouři v postupu, tak se vysokoenergetické částice vrhly do kolonie – blesky začaly tančit po vnějších budovách kolonie a trhat je na kusy. Současně s tím ale pilot Hefaista spustil program nouzového vzestupu na orbitu a atmosférické motory se opřely do okolní země. Devítisettunová loď se začala rychle zvedat.

Nebylo to však dostatečně rychle – přes proud výfukových plynů pronikl jeden z blesků iontové bouře do atmosférického motoru na pravoboku. Motor samotný to sice přežil, ale část řídících obvodů se spálila na škvarek a výboj pronikl i dál do řídící elektroniky a způsobil množství zkratů. Hlavní řídící počítač Hefaista se odmlčel, ale naštěstí měly jednotlivé motory již zadané profily letu a během následujících bouřlivých minut dostaly loď až na oběžnou dráhu.

Potom, co všichni přestali být tlačeni do svých sedaček a naopak se po potemnělém interiéru ochromené lodě začaly vznášet neupevněné předměty, vrhla se posádka hned do zkoumání škod. Prvním krokem bylo izolování vyzkratovaných systémů, aby opět mohli nahodit hlavní počítač.


Praktická opendata úloha32-3-1 Zkrat (12 bodů)


Kuchařková úlohaSystémy hvězdné lodě Hefaistos jsou ochromené, protože část obvodů byla vyzkratována. Hlavní inženýr potřebuje nahodit počítačové jádro, ale to nelze, dokud existuje spojení počítačového jádra a místa zkratu.

Energetickou síť si můžeme představit jako energetické uzly spojené vodiči (jeden vodič spojuje vždy dva energetické uzly), kde v jednom energetickém uzlu je zkrat a do jiného energetického uzlu je zapojené přímo počítačové jádro.

Hlavní inženýr bude muset přerušit několik vodičů tak, aby neexistovala žádná cesta mezi místem zkratu a počítačovým jádrem. Vodiče jsou ale špatně dostupné, takže by jich chtěl hlavní inženýr přerušit co možná nejméně. Naprogramujte algoritmus, který mu určí, jaké vodiče má přerušit.

Toto je praktická open-data úloha. V odevzdávacím systému si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Formát vstupu: Na prvním řádku dostanete mezerou oddělená čtyři čísla N, M, zp udávající počet energetických uzlů, počet vodičů mezi nimi, index energetického uzlu se zkratem a index energetického uzlu s počítačovým jádrem (energetické uzly indexujeme od nuly). Na dalších M řádcích je pak vždy dvojice mezerou oddělených čísel ab udávající, že mezi energetickými uzly ab vede vodič.

Formát výstupu: Na první řádek výstupu vypište číslo K udávající kolik nejméně musíme přerušit vodičů, abychom oddělili zkrat a počítačové jádro. Na dalších K řádcích pak vypište indexy vodičů, které musíme přerušit (index vodiče je jeho pořadí na vstupu, indexujeme opět od nuly, na pořadí indexů na výstupu nezáleží). Pokud existuje více stejně dobrých řešení, můžete vypsat libovolné z nich.

Ukázkový vstup:
9 13 7 2
0 2
4 0
2 3
1 2
1 3
0 1
2 4
3 5
4 6
6 7
6 8
7 5
7 8
Ukázkový výstup:
2
8
7

Graf obvodů z příkladu

V příkladu výše stačí k oddělení dvou zvýrazněných vrcholů (zkratu a hlavního počítače) přerušit dva vodiče mezi uzly 4-6 a 3-5. Stejně tak by fungovalo i přerušení vodičů 4-6 a 5-7.

Po zprovoznění hlavního počítače a obnovení části systémů (ke spokojenosti žaludku kolonistů i pole umělé gravitace) se na můstku sešla část posádky na poradě.

„Jsme bez hyperprostorového pohonu, řídící obvody jsou na škvarek a nevím, jestli to půjde opravit,“ oznámil všem hlavní inženýr.

„Nepřišlo vám na té iontové bouři něco divného? A na té základně v horách?“ načal diskuzi mariňák Drake. „Skoro jako by tady někdo vyvíjel tajnou zbraň,“ zapřemýšlel nahlas.

„A když se jim něco nepovedlo a přiletěli jsme my, tak se pokusili zamést stopy…“ rozvinula jeho teorii kapitánka. Pak se otočila na komunikačního důstojníka: „Můžeme navázat spojení s velením na Antaraxu?“

Zax zavrtěl hlavou. „Ne, je tu rušení od iontové bouře na planetě, ale díky němu asi nejsme vidět ani my, dokud nezapneme motory. A navíc jsem si všimnul, že někdo mezitím překonfiguroval družice vypuštěné kolonií – změnily své komunikační linky a vytvořily novou síť, do které nejsme zapojení.“

„Můžeme je nějak napíchnout?“ zapřemýšlela kapitánka. „No když se nám povede odhalit jejich propojení, tak možná ano…“ řekl Zax a pustil se do práce.


Teoretická úloha32-3-2 Hledání konstelace (12 bodů)


Komunikační důstojník Zax by potřeboval odhalit v jaké konstelaci jsou družice na oběžné dráze. Každou družici si můžeme představit jako vrchol a přímé propojení mezi dvojicí družic jako hranu nějakého grafu.

Graf neznáme, ale povedlo se nám zachytit nějaké servisní zprávy – některá by mohla udávat tvar této konstelace.

Přesněji se nám povedlo zachytit posloupnost N čísel, o které si myslíme, že to jsou počty propojů, které každá družice má (v grafové terminologii bychom toto číslo nazvali stupněm vrcholu). Nejsme si ale jistí, jestli zachycená posloupnost popisuje nějakou konstelaci – vymyslete proto algoritmus, který pro zadanou posloupnost N čísel (uspořádaných od nejmenšího po největší) rozhodne, jestli tato posloupnost může popisovat nějaký graf.

Můžete k tomu použít znalost věty o skóre. Tato věta říká, že posloupnost N čísel d1, d2, … popisuje graf s vrcholy o stupních d1, d2, … právě tehdy když upravená posloupnost, ze které odebereme největší stupeň dN a odečteme od dN zbylých největších stupňů jedničku, také popisuje graf. Jednoduchá představa je, že z původního grafu odebereme vrchol s největším stupněm, který byl spojen s dalšími dN vrcholy s největším stupněm.

K vyřešení úlohy nepotřebujete znalost důkazu této věty – můžete nám věřit, že platí. Pouhé naivní použití věty v algoritmu ale na moc bodů stačit nebude – chceme od vás algoritmus, který zvládne o zadané posloupnosti rozhodnout, jestli tvoří skóre nějakého grafu, v co nejlepším čase. Plného počtu bodů půjde dosáhnout jen za řešení v lineárním čase vzhledem k velikosti daného grafu, neboli v O(N+M).

Zatímco se Zax pokoušel nabourat se do družicové konstelace, tak kapitánka debatovala s ředitelem kolonie. Materiál pro stavbu tajné základny (nemluvě o spoustě jiné techniky) musel být na planetu nějak dopraven, a to pravděpodobně na palubě běžných zásobovacích lodí.

Při kopírování hlavního počítače kolonie získali i soubory o různých kontejnerech dopravených na planetu a naopak v tajné základně získali inventární seznam jejich skladu – teď to jenom napasovat na sebe a možná to dá nějaké zajímavé indicie. Kapitánka s ředitelem se dali do identifikace kontejnerů, do kterých by se různé věci nalezené na tajné základně vešly.


Teoretická úloha32-3-3 Kontejnerové počty (11 bodů)


Kapitánka se ředitelem kolonie by chtěli rychle vyfiltrovat kontejnery, do kterých se vejde předem daná hromada vybavení. Kontejnery jsou kvádry o rozměrech A×B×C s maximální délkou strany K.

Protože hromada vybavení nemá žádný hezký pravidelný tvar (různé tyče, zahnuté potrubí, kulaté nádrže, …), tak se nedá lehce určit, jak velký kontejner je potřeba. Kapitánka s ředitelem si vždycky vezmou pevnou hromadu vybavení a pak zkoumají, do jakého kontejneru by se vešla. Pro zadané A, BC umí určit (poměrně náročným a zdlouhavým postupem), jestli se vybavení do takového kontejneru vejde, nebo ne.

Protože je ale možných velikostí kontejnerů řádově K3, tak se jim nechce pro každou kombinaci rozměrů samostatně počítat, jestli se věci vejdou – ocenili by drobnou pomoc.

Ohledně kontejnerů platí jediné pravidlo, a to, že pokud se zadaná hromada vybavení vejde do kontejneru A×B×C a tento kontejner se (nějak pravoúhle otočený, šikmé umístění neuznáváme) vejde do druhého kontejneru A'×B'×C' (tedy že otočený první kontejner není v žádné ose větší než druhý kontejner), tak se vybavení vejde i do druhého kontejneru.

Například můžeme říci, že pokud se vybavení vejde do kontejneru 5×2×10, tak se určitě vejde i do kontejneru 2×10×11. Naopak o kontejneru 9×9×9 ale nemůžeme prohlásit nic (a budeme se muset zeptat lidské obsluhy).

Vaším úkolem je vymyslet algoritmus, který (pro pevně danou hromadu věcí) nejdříve položí dotazy na nějaké velikosti kontejnerů kapitánce se ředitelem, a pak bude umět správně odpovědět na jakýkoliv dotaz pro A,B,C ≤ K. Vaším cílem je minimalizovat počet „pomalých“ dotazů na kapitánku se ředitelem – minimalizujte i multiplikativní konstantu a zkuste dokázat, že na méně dotazů už to nelze.

Lehčí variantaLehčí varianta (za 7 bodů): Vyřešte úlohu jenom ve 2D, tedy namísto kvádrů uvažujte pouze obdélníky o rozměru A×B.

Po odečtení kontejnerů, které s jistotou byly rozebrané v kolonii, a kontejnerů, které podle výpočtu byly použity pro materiál na tajné základně, dospěli k tomu, že schází zhruba půl tuctu kontejnerů, které musely být dovezené ještě někam jinam. Materiál v nich by stačil na stavbu zhruba poloviční základny, než byla ona objevená tajná základna v horách. Teď už ji jen najít…

Zaxovi se mezitím povedlo zjistit konfiguraci družicové sítě. Jenom s pomocí manévrovacích trysek se Hefaistos pomalu přesunul k jedné z družic. Když pilot stabilizoval loď dvacet metrů od družice, tak se k ní vydali dva členové posádky ve skafandrech a v domluvenou chvíli jí přerušili napájení. Přesně v tu samou chvíli anténní soustava Hefaista ožila a začala se vydávat za právě odpojenou družici – snad si nikdo ničeho nevšimne.

Poté dopravili družici skrz malý hangár pro servisní raketoplán do nákladního prostoru Hefaista, kde se na ni vrhl hlavní inženýr. Uvnitř těla družice narazil na zajímavou komponentu, která vypadala dost jako prototyp – spousta drátů zapojených do různých konektorů na různých přístrojích. Po chvíli rozebírání si ale s hrůzou uvědomil, že si nedělal poznámky, kam který drát patří…


Teoretická úloha32-3-4 Zmatek v konektorech (11 bodů)


Hlavní inženýr rozebral zkoumanou družici, ale teď by potřeboval pozapojovat vytažené dráty nazpět. Má teď v ruce spoustu koncovek, ale neví, do kterého konektoru kterou koncovku zapojit. Naštěstí mají koncovky i konektory více různých tvarů, ale nejsou bohužel úplně unikátní. Přesněji každou koncovku lze zapojit do právě dvou různých konektorů.

Vymyslete algoritmus, který pro zadané koncovky (pro každou koncovku dostaneme zadaná čísla právě dvou konektorů, kam pasuje) najde správné zapojení, nebo oznámí, že to nelze. Správné zapojení je takové, kdy je každá koncovka zapojená do právě jednoho konektoru a v žádném konektoru není více než jedna koncovka.

Příklady:

  • Koncovky (1,2)(3,4) lze triviálně zapojit třeba tak, že první koncovku zapojíme do konektoru 1 a druhou do konektoru 4.
  • Koncovky (1,2), (2,3)(3,1) lze také správně zapojit.
  • Naopak koncovky (1,2), (1,3), (1,4), (3,2), (3,4)(5,6) správně zapojit nelze.

„Někdo ty satelity upravil kapitáne. Tohle jsem ještě neviděl, ale podle zapojení a komponent bych hádal, že to nějakým způsobem ovládá směrování iontové bouře. Má to celkem velkou energetickou náročnost, ale za chodu to už čerpá energii z iontové bouře. Na detaily se mě neptejte, sám tomu úplně nerozumím,“ vysvětloval po pár hodinách zkoumání satelitu hlavní inženýr McCormack ostatním.

„Co je ale zajímavé, je, že ve stand-by režimu to musí být extrémně úsporné, aby to zvládlo parazitovat na normálních součástkách satelitu. A to si to každou hodinu posílá docela komplikované zprávy po celé síti…“


Teoretická úloha32-3-5 Energetická náročnost (10 bodů)


Pro propočty ohledně fungování satelitní sítě je potřeba spočítat její energetickou náročnost ve stand-by režimu. Již jsme zjistili, že satelity jsou pospojované do souvislé sítě ve tvaru stromu a známe energetickou náročnost poslání zprávy mezi propojenými satelity (jinými slovy máme strom s ohodnocenými hranami).

Každou hodinu každý z N satelitů vyšle zprávy všem N-1 zbylým satelitům. Zprávy putují po satelitní síti nejkratší cestou a energie spotřebovaná na předání jedné zprávy po nějaké „hraně“ odpovídá ohodnocení této hrany. Protože komunikační protokol navazuje nové spojení pro každou zprávu, tak předání k zpráv po hraně ohodnocené „cenou“ c stojí celkově k·c jednotek energie.

Nás by zajímala celková spotřebovaná energie když každý ze satelitů vyšle zprávu každému jinému. Vymyslete algoritmus, který to pro zadanou síť zvládne spočítat co nejrychleji.

Příklad: Pro satelitní síť na obrázku níže je celková spotřebovaná energie pro vyslání všech zpráv ze všech 5 satelitů celkem 152 jednotek energie. Zprávy ze satelitu A spotřebují 27 jednotek energie, ze satelitu B také 27 jednotek, ze satelitu C 24 jednotek, ze satelitu D 34 jednotek a ze satelitu E 40 jednotek energie.

Ukázková satelitní síť

Díky všem indiciím se povedlo posádce Hefaista koncem dne lokalizovat druhou tajnou základnu na planetě. Pokud mohli hádat, tak právě odsud byly kontrolovány iontové bouře a tam sídlil někdo, kdo se rozhodl, že nepotřebuje svědky, kteří vědí příliš mnoho.

Nadsvětelná komunikace s velením na Antaraxu byla pořád blokovaná a následky iontové bouře, které oslepovaly senzory tajemné základny a ukrývaly poničeného Hefaista, postupně slábly. Brzy je odhalí a těžko říci, jaké další akce podniknou k tomu, aby se zbavili svědků. Nyní byla ale karta stále na straně Hefaista, jenom se rozhodnout, co podniknout…

* * *

Opět rozhodněte o tom, jak má příběh pokračovat. Hlasujte do 10. únoraanketě.

Třetí díl příběhu pro vás sepsal

Jirka Setnička


Seriálová úloha32-3-6 Jízdní řády (15 bodů)


Zadání seriálu bude zveřejněno během několika málo dní. Ladíme poslední detaily s jízdními řády, máte se na co těšit :)

Filip Štědronský