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

Celý leták, který posíláme také papírově, v PDF.

Poslední letošní série tohoto jubilejního 2⁵-tého ročníku KSPčka se vám právě dostává do rukou. I když venku stále řádí pandemická doba, tak doufáme, že se s mnohými z vás uvidíme na podzimním soustředění – pokud se tedy chcete účastnit, tak máte poslední šanci získat ještě nějaké body.

V této sérii namísto seriálu přibalujeme interaktivní úlohu, kde budete muset z našeho serveru získat správné informace. Zapojit se může každý, tak toho využijte! Mimo to série obsahuje další čtyři teoretické a jednu praktickou úlohu. Kuchařku tentokrát nepřibalujeme, ale můžete se podívat do kuchařky minulé série, mohla by se vám hodit i v této.

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.

Díky řešení KSP se také můžete vyhnout přijímacím zkouškám na MFF UK! Stačí, když získáte alespoň polovinu bodů z ročníku (tedy 150 bodů), a my vám vystavíme osvědčení, díky kterému vás přijmou na MFF bez zkoušek. 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 a placku.

• Termín série: neděle 21. června 2020 ve 32:00 (tedy další ráno v 8:00)
• Odevzdávání: elektronicky přes Odevzdávátko
• Jak řešit: viz Návod na teoretické úlohy a Návod na praktické úlohy
• Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.

• Odměna série: Sladkou odměnu si vyslouží každý, kdo získá z této série alespoň 42 bodů

Zadání úloh

• 32-5-1: Poničený zdrojový kód
• 32-5-2: Propojovací kabely
• 32-5-3: Bomberman uklízí efektivně
• 32-5-4: Distribuované počítání
• 32-5-5: Druhá kostra
• 32-5-6: Geocaching s odhadem

32-5-1 Poničený zdrojový kód (10 bodů)

Posádka Hefaista by chtěla zprovoznit malou loď, kterou našli, aby měli alespoň nějaký dopravní prostředek na orbitu. Bohužel původní majitelé stihli poškodit programování lodi a to je potřeba opravit.

Poškození programování lodi je v podstatě jednoduché – ve zdrojovém kódu došlo k otočení některých složených závorek označujících bloky kódu na opačné složené závorky (z { se tak mohlo stát } a naopak).

Vaším úkolem je vymyslet algoritmus, který dostane na vstupu posloupnost závorek (třeba }}{{}{}}}}}}) a nalezne co nejmenší množinu závorek, kterou je potřeba otočit na opačné, aby byl celý „program“ správně uzávorkovaný.

Správně uzávorkovaný program vypadá tak, že každá otevírací závorka má párovou zavírací závorku napravo od ní, každá zavírací závorka má obdobně párovou otevírací závorku nalevo od ní a páry závorek se nekříží.

Například pro vstup }}{{}{}}}}}} je jednou z možností, která otočí co nejméně závorek, tato:

Řešení

32-5-2 Propojovací kabely (11 bodů)

Hlavní inženýr a jeho pomocníci by potřebovali zapojit všechny elektrické spotřebiče v dílnách do elektrické sítě. Mají už naplánovaný plán zapojení, který tvoří strom. Co ale ještě nerozhodli je to, kde povede jaký typ kabelu.

Bedna s běžnými prodlužovacími kabely se jim bohužel ztratila při havárii, takže jim zbyly jenom propojovací kabely, tedy kabely, které mají na opačných koncích vždy rozdílné konektory (takže mají třeba kabely typu schuko-USB, RJ45-HDMI, jack-USB a podobně :-)). Kabelů pro libovolnou kombinaci různých konektorů máme neomezeně, jenom nemáme ani jeden kabel se stejnými konektory na obou koncích.

Do jednotlivých vrcholů stromu pak musíme umístit uzly pro propojení kabelů. Uzel má vždy konektory jenom jednoho typu (tedy je to třeba USB uzel, schuko uzel, RJ45 uzel, …). Uzlů je také neomezené množství, ale jednotlivé typy uzlů mají rozdílnou cenu.

Vaším úkolem bude vymyslet algoritmus, který dostane na vstupu ceny různých typů uzlů a naplánovaný strom zapojení, a nalezne nejlevnější rozmístění uzlů do jednotlivých vrcholů zadaného stromu.

Výstupem by tedy měla být informace, jaký typ propojovacího uzlu umístit do jakého vrcholu stromu tak, aby sousední uzly nikdy nebyly stejného typu (aby šly navzájem propojit dostupnými kabely), ale zároveň aby součet ceny všech použitých uzlů ve stromě byl co nejmenší.

Řešení

32-5-3 Bomberman uklízí efektivně (12 bodů)

Robot na odklízení trosek vjel do podzemních prostor základny, které si můžeme představit jako mapku na čtverečkovém papíru. Prostory obsahují nosné zdi (ty nejdou rozbít), trosky (ty rozbít jdou) a volná políčka (po těch se dá jezdit). Odklízecí robot vždy dojede na nějaké políčko, položí na políčko bombu, poodjede někam dál a pak bombu odpálí. Bomba pak vybuchne ve čtyřech směrech (nahoru, dolů, doleva a doprava) a zasáhne nejbližší neprázdné políčko v tom směru – pokud to je nosná zeď, tak se nic nestane, pokud to jsou trosky, tak se z nich stává volné políčko (a pokud to je robot na odklízení trosek, tak právě spáchal sebevraždu).

Vaším úkolem bude vymyslet algoritmus, který pro zadanou mapu vyrobí posloupnost příkazů, kterými robot na odklízení trosek „odbouchne“ všechny trosky, ale sám přitom neumře (příkazy jsou pohyb doleva, doprava, nahoru nebo dolů o jedno políčko, pak příkaz pro položení bomby a příkaz pro odpálení bomby).

Tato úloha je teoretickou verzí právě běžící opendatové úlohy začátečnické kategorie Bomberman uklízí, u které stačí najít libovolnou posloupnost kroků. Zde po vás ale chceme vymyslet a popsat algoritmus, který nalezne řešení s řádově co nejméně kroky – tedy vaše řešení budeme hodnotit podle toho, kolik řádově musí udělat kroků pro vyčištění libovolné mapy velikosti N×N.

Mělo by jít dosáhnout až řešení, které udělá lineárně mnoho kroků vzhledem k velikosti mapy, ale nějaké body dostanete i za řešení s větším počtem kroků. Nezapomeňte ale dokázat, že vaše řešení odbouchne skutečně všechny trosky (můžete počítat s tím, že to vždy půjde) a pořádně zdůvodněte svůj odhad na počet vykonaných kroků – bez toho vám nemusíme řešení uznat.

Řešení

32-5-4 Distribuované počítání (10 bodů)

Každá ze tří základen má u sebe třetinu naměřených dat. Data jsou ale příliš velká na to, aby je bylo efektivní přenést do jednoho místa (jejich vysílání by trvalo několik dní).

Každá základna drží právě N naměřených hodnot. Všech 3N naměřených hodnot jsou navzájem různá čísla a my bychom z nich potřebovali rychle spočítat medián (tedy prvek, který bude v setříděné posloupnosti hodnot přesně uprostřed). Základny mohou mezi sebou vysílat krátké zprávy: do zprávy se vejde jedno číslo (Myšleno rozumně malé číslo, například jedna naměřená hodnota.). A když jedna základna vyšle zprávu, tak ji zachytí obě dvě zbývající.

Navrhněte komunikační protokol (neboli postup, co by měly základny vysílat za zprávy), abychom po co nejmenším počtu kroků mohli jednoznačně určit, jaká hodnota je mediánem všech 3N naměřených hodnot. Řešení budeme hodnotit podle počtu nutných zpráv k vyslání v průměrném a v nejhorším případě. Postup, kdy základny vyšlou všech 3N hodnot jako zprávy, je bohužel příliš neefektivní a nedostanete za něj žádné body.

Řešení

32-5-5 Druhá kostra (14 bodů)

Hlavní inženýr McCormack je opět v nesnázích a potřeboval by vaši pomoc. Jeho úkolem je udělat kalibraci družicové sítě, aby ji mohli použít pro detekci neznámé lodě na orbitě.

Družice představují vrcholy grafu a komunikační linky mezi nimi pak hrany. Jednotlivé komunikační linky jsou navíc ohodnoceny množstvím energie potřebném pro jejich provozování.

Hlavní inženýr plánuje družice spojit do minimální kostry (tedy určit množinu komunikačních linek s co nejmenší energií spojující všechny družice), ale pro správnou kalibraci by zároveň potřeboval vědět, jak vypadá druhá nejlehčí kostra. A to bude úkol pro vás.

Druhá nejlehčí kostra je kostrou grafu (tedy stále spojuje všechny jeho vrcholy), která je nejlehčí ze všech koster, které se neshodují s minimální kostrou (tedy mohou mít nějaké hrany stejné jako minimální kostra, ale ne všechny). Jen pro úplnost doplňujeme, že váha kostry je součet ohodnocení všech jejích hran.

Abychom se vyhnuli krajním případům, tak v zadaném grafu družic a komunikačních linek budou všechna ohodnocení hran (komunikačních linek) navzájem různá a graf bude souvislý. Pokud i tak naleznete více druhých nejlehčích koster, můžete si vybrat libovolnou z nich.

Pokud si potřebujete osvěžit techniky pro hledání minimálních koster, nahlédněte do kuchařky o minimálních kostrách, kterou jsme přibalili k minulé sérii. A dále by vám k řešení této úlohy mohl pomoci některý ze seriálů KSPčka z posledních pěti let – najdete je všechny na webu KSP v sekci Encyklopedie.

Toto je praktická open-data úloha. V odevzdávátku 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 vstupu dostanete dvě čísla N a M oddělená mezerou udávající počet družic a počet komunikačních linek mezi nimi. Na dalších M řádcích pak dostanete vždy trojici čísel a, b a e oddělených mezerou, které říkají, že mezi družicemi a a b je obousměrná komunikační linka, na kterou je potřeba e energie (1≤ e≤ 10⁹). Družice i hrany indexujeme od nuly a všechna e budou navzájem různá.

Formát výstupu: Na první řádek výstupu vypište váhu vámi nalezené druhé nejlehčí kostry. Na druhý řádek pak vypište indexy komunikačních linek, které jsou součástí vaší druhé nejlehčí kostry (indexujeme podle pořadí na vstupu od nuly). Upozorňujeme, že váha kostry se nemusí vejít do 32-bitového typu.

4 5
0 1 1
1 2 2
2 3 3
3 0 4
0 2 8

7
0 1 3

Nejlehčí kostra obsahuje hrany s energiemi 1, 2 a 3. Druhá nejlehčí používá energie 1, 2 a 4. Hranu s energií 8 se určitě nevyplatí použít.

Řešení

32-5-6 Geocaching s odhadem (13 bodů)

Mladý McCormack, tehdy ještě student fakulty Multidimenzionální Fyziky a Fúze, žil dobrodružným životem a velmi rád hledal ukryté poklady ve vesmírné obdobě staré hry Geocaching, kde se hledaly poklady – kešky – podle souřadnic. Část kešek byla přístupná veřejně a každý si mohl jejich pozice zobrazit na mapě hvězdné soustavy, část jich ale byla placená a jejich pozice byly dostupné jenom platícím uživatelům. McCormackovi se ale platit nechtělo.

Zjistil však, že API herní mapy při dotazu na obdélník souřadnic – výřez mapy – vrátí až 500 nejbližších kešek seřazených podle vzdálenosti od středu zadaného obdélníku. U běžných kešek odpověď obsahuje jejich souřadnice a vzdálenost od středu výřezu mapy, u placených ale tyto informace zatají. Pokud je ale placená keška vzdáleností mezi dvěma normálními, tak se dá její vzdálenost odhadnout vzdáleností těchto dvou normálních kešek, a posunutím výřezu mapy lze také přiblížit její souřadnice.

Pokud pak provedete více dotazů z různých míst, tak můžete pozici takové placené kešky celkem dobře určit.

Tato úloha je interaktivní – dostanete k dispozici server, na který můžete s vygenerovaným tokenem (detaily viz níže) posílat dotazy a on vám bude vracet odpovědi. S jedním tokenem budete moci poslat nejvýše 5000 dotazů a vaším úkolem bude nalézt co nejvíce placených kešek a odevzdat jejich souřadnice s odchylkou nejvýše 0.00001 v každé ze souřadnic od souřadnic reálných. Mapa je pro každý token unikátní, můžete to tedy zkoušet vícekrát, jen musíte vždy začít zjišťovat informace znovu.

Technické detaily

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

V souboru se vstupem dostanete výše zmiňovaný token. Jako výstup odevzdávejte soubor se seznamem lokalizovaných placených kešek, každou na jeden řádek ve formátu lon lat guid, kde lon je zeměpisná délka, lat je zeměpisná šířka a guid je identifikátor placené kešky.

Ukázkový vstup:

eyJ0eX..m6E

8.242733 10.718694 3392aa2d-9ff4-4718-8168-caac341595cf
8.62143 3.50012 01969818-3e19-4004-a781-d5b7d3a82764

Server, s kterým budete komunikovat je webový a naleznete jej na adrese https://ksp.mff.cuni.cz/api/32-5-6/. Pro všechny požadavky specifikujte token query parametrem ?token=<token>.

K dispozici jsou dva endpointy, oba přístupné HTTP metodou GET. Odpovědi serveru jsou ve formátu JSON.

Prvním z endpointů je /token/status. Ten vypíše zbývající počet požadavků pro token.

Příklad požadavku (HTTP GET):

/token/status?token=eyJ0eX..m6E

Příklad odpovědi (JSON):

{"remaining_uses":12}

Druhým endpointem je /map/caches, který vypíše kešky ve výřezu mapy specifikovaném minimální a maximální zeměpisnou šířkou (lat) a délkou (lon). Maximální šířka i výška výřezu mapy je omezená na jeden stupeň. I v takovém jednostupňovém výřezu už se může nacházet tisíce kešek, což je více než limit kolik API vrací (API vrátí 500 kešek nejbližších středu výřezu).

Stejně tak jsou souřadnice (lat i lon) omezeny do rozsahu od -5000 do 5000, dále mapa nesahá. Doporučujeme se držet blízko středu. API vrací pro běžné kešky dist, jejich euklidovskou vzdálenost ve stupních. Vzdálenosti jsou tedy počítány v rovině, žádné zakřivení zde není.

Příklad požadavku (HTTP GET):

/map/caches?min_lon=8.5&max_lon=9&min_lat=3.2&max_lat=3.8&token=eyJ0eX..m6E

Příklad odpovědi (JSON):

[{
  "lon":8.612847283249843,
  "lat":3.502198688487054,
  "dist":0.013034067590925793,
  "guid":"ddf758a2-6e0c-497f-9b0c-66e8d37a3ef2"
},
{
  "lon":null,
  "lat":null,
  "dist":null,
  "guid":"01969818-3e19-4004-a781-d5b7d3a82764"
},
{
  "lon":8.630878819665622,
  "lat":3.4931887828703307,
  "dist":0.031621103439467516,
  "guid":"357428fb-037e-4adf-912c-f8bd59e43393"
}]

Všimněte si druhé kešky, která má null pro souřadnice a vzdálenost. Jde totiž o placenou kešku, a právě pro takové chceme odhadnout jejich pozice.

Pro získání plného počet bodů je potřeba zaměřit alespoň 100 placených kešek. Při menším počtu získáte poměrný počet bodů.

Disclaimer: Prosím nezkoušejte podobné postupy na oficiální Geocaching API – podobný postup by provozovatelé jistě neocenili a kdyby zjistili, že je masivně zneužívaný, mohlo by dojít ke zhoršení situace pro všechny. A to by nikdo nechtěl.

Řešení