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

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

Dostává se k vám páté číslo hlavní kategorie 36. ročníku KSP.

Letos se můžete těšit v každé z pěti sérií hlavní kategorie na 4 normální úlohy, z toho alespoň jednu praktickou opendatovou. Dále na kuchařky obsahující nějaká zajímavá informatická témata, hodící se k úlohám dané série. Občas se nám také objeví bonusová X-ková úloha, za kterou lze získat X-kové body. Kromě toho bude součástí sérií seriál, jehož díly mohou vycházet samostatně.

Autorská řešení úloh budeme vystavovat hned po skončení série. Pokud nás pak při opravování napadnou nějaké komentáře k řešením od vás, zveřejníme je dodatečně.

Odměny & na Matfyz bez přijímaček

• Termín série: neděle 23. června 2024 ve 32:00 (tedy další ráno v 8:00)
• Odevzdávání: elektronicky přes Odevzdávátko
• Jak sepsat řešení: viz Návod na teoretické ú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ží ten, kdo získá alespoň 2 body z každého dílu seriálu.

Zadání úloh

• 36-5-1: Opravování opravy vzducholodi
• 36-5-2: Polygloti
• 36-5-3: Všechny cesty vedou do Říma
• 36-5-4: Hackovaci soutez
• 36-5-X1: Superstring

36-5-1 Opravování opravy vzducholodi (10 bodů)

Organizátoři KSP se radují. Aby ne, když jim přišlo celkem N řešení úlohy 36-4-1! Bojí se jen, že jim bude trvat dlouho všechna řešení opravit.

Organizátoři se proto pokusili vytrénovat jazykový model, který by řešení opravil za ně. Moc úspěchu ale neměli: nejen že se jim nepodařilo modelu vysvětlit vzorové řešení, ale navíc se bojí, že když některý z účastníků nevyhnutelně vymyslí nějaké originální, netradiční řešení, tak ho jazykový model nepozná a zamítne. Podařila se jim však jedna věc: model naučili zhodnotit složitost a čitelnost daného řešení a na základě toho přesně spočítat, jak dlouho bude organizátorovi trvat ho opravit ručně.

Existuje K organizátorů, kteří mají čas řešení opravovat. Plánují se sejít a řešení si mezi sebou rozdělit. Každý organizátor postupně opraví všechna svá řešení, každé přesně za dobu předpovězenou jazykovým modelem. Opravování bude hotovo, jakmile svá řešení doopraví poslední z organizátorů.

Bohužel došel inkoust ve stroji, který řešení orazítkovává čárovými kódy, takže se organizátoři bojí, že se jim řešení pomíchají. Řešení si proto seřadili abecedně podle jména autora a každému organizátorovi plánují přidělit nějaký souvislý úsek.

Organizátoři by rádi řešení opravili co nejrychleji, aby mohli spolu jít na zmrzlinu. Poradíte jim, jak si mají řešení rozdělit?

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 budou dvě přirozená čísla: počet řešení N a počet organizátorů K. Na druhém řádku bude N přirozených čísel T₁ až T_N, časy potřebné k opravení jednotlivých řešení v mikrosekundách. Řešení jsou uvedena v tom pořadí, jak si je organizátoři abecedně seřadili.

Formát výstupu: Za každého opravujícího organizátora vypište jeden řádek s dvěma čísly a a b, číslo prvního a posledního řešení (včetně), které má daný organizátor opravit. Těchto řádků můžete vypsat nejvýše K.

6 3
4 1 6 10 1 2

1 3
4 4
5 6

Vysvětlení ukázkového vstupu: Prvnímu organizátorovi bude opravování trvat 11 mikrosekund, druhému 10 mikrosekund a třetímu 3 mikrosekundy. Opravování tedy bude hotovo za 11 mikrosekund, což je tak rychle, jak to jen jde.

36-5-2 Polygloti (12 bodů)

Honza se Šimonem byli ze školy vysláni na Konferenci sudokopytných polyglotů v Hrochschwabu, aby tam předali své znalosti hřečtiny. Nejprve ale potřebují vymyslet nějakou rozumnou trasu, kterou se dostat do tak daleké krajiny. Zároveň by si po cestě rádi zopakovali jazyky ostatních zemí. Pokud se totiž účastník konference zvládne domluvit s jakýmkoliv jiným účastníkem v jeho rodné řeči, vyhraje zlaté parohy.

Aby se navzájem motivovali ve cvičení jazyků, domluvili se Honza a Šimon na následujícím postupu: oba nejprve začnou putování v jejich domovském městě Hroška. Jakmile se jejich cesty rozdělí, začnou se oba samostatně učit nějaký nový jazyk. Až se jejich cesty zkříží, promluví si spolu tímto jazykem, obohativše se navzájem díky různým přístupům k učení. Jakmile se po nějaké chvíli zase rozejdou, celý proces se zopakuje s dalšími novými jazyky, a tak dále, dokud se jim nepodaří setkat se v Hrochschwabu.

Oba kamarádi by rádi své cesty naplánovali tak, aby se během nich naučili co nejvíce jazyků. Jinými slovy, chtějí se na cestách co nejvíckrát rozejít a zase sejít. Pomůžete jim?

V našem světě existuje celkem N měst očíslovaných 1 až N podle toho, jak vysoko se nachází – nejníže položené město má tedy číslo 1. Jelikož chodit z kopce je nuda, cesty mohou vést pouze z níže položených měst do vyšších. Z i-tého města potom vedou jednosměrky do n_i dalších měst, a to pouze těch, které mají číslo větší než i. Hroška má číslo v_s a Hrochschwab má číslo v_c, přičemž v_s ≠ v_c.

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 zadané hodnoty N,v_s,v_c. Na dalších N řádcích obdržíte postupně popisy jednotlivých měst: i-tý řádek začíná číslem n_i. Za ním následuje n_i vzestupně řazených čísel měst, do kterých vede z i-tého města jednosměrka.

Formát výstupu: Nechť vámi nalezená Honzova a Šimonova cesta navštěvuje H, respektive S měst. Na prvním řádku vypište H mezerami oddělených čísel měst popisujících postupně Honzovu cestu, tedy prvním číslem musí být v_s a posledním v_c. Na druhém řádku vypište ve stejném formátu Šimonovu cestu. Pro tyto dvě cesty musí platit, že se na nich oba kamarádi co nejvíckrát rozejdou a zase potkají. Cesty nemusí být hranově disjunktní, je tedy povoleno, aby občas mezi dvěma městy cestovali Honza a Šimon spolu. Pokud existuje více stejně dobrých cest, vypište libovolnou z nich. Máte zaručeno, že mezi Hroškou a Hrochschwabem existuje aspoň jedna cesta.

7 1 6
3 2 3 4
1 4
1 5
2 5 6
2 6 7
0
0

1 2 4 6
1 4 5 6

36-5-3 Všechny cesty vedou do Říma (12 bodů)

Adam a Kačka se rozhodli udělat si pochod z Benátek do Říma. Sbalili si, nasedli na vlak a vyjeli do Benátek. Když jeli kolem hranic, tak se Adam rozhodl si protáhnout nohy a projít se po vlaku. Nicméně chvíli potom rozpojili vlak, a když se Adam snažil domluvit s průvodčím, dostalo se mu pouze odpovědi: „Non riesco a capirti.“

Nyní je Kačka v Benátkách a Adam je v Miláně. Nicméně i přesto se rozhodli udělat pochod do Říma. To udělají tak, že v současném městě zkusí se svou omezenou schopností italštiny zjistit, kterým směrem je Řím. Poté tímto směrem půjdou, dokud nedojdou do dalšího města, kde proces zopakují. Kačku a Adama nyní zajímá, kde se poprvé potkají.

Trochu formálněji: Vrcholy grafu Itálie tvoří města, kde každý vrchol má právě jednu výstupní hranu. Pokud začneme v libovolném vrcholu, a budeme z něj následovat hrany, časem dojdeme do Říma. Kačka stojí ve vrcholu b a Adam ve vrcholu m. Chtěli bychom najít první vrchol, kterým projdou oba.

Nicméně graf Itálie není malý, proto požadujeme, aby algoritmus kromě uložení grafu samotného používal jen konstantně mnoho paměti. Navíc pokud se Adam a Kačka budou se svou omezenou schopností italštiny ptát místních na směr do Říma a vždy se tímto směrem vydají, nejspíš nepůjdou úplně přímou cestou.

Proto určujte složitost algoritmu vzhledem k těmto parametrům:

• S_b – Vzdálenost Benátek a prvního společného města
• S_m – Vzdálenost Milána a prvního společného města
• R_b – Vzdálenost Benátek a Říma
• R_m – Vzdálenost Milána a Říma
• N – Počet vrcholů
• M – Počet hran

Například, kdybychom měli následující algoritmus, který je sice funkční, ale nepoužívá konstantní množství paměti:

• Najdeme všechny vrcholy na cestě B z Benátek do Říma O(R_b)
• Najdeme všechny vrcholy na cestě M z Milána do Říma O(R_m)
• Pro každý vrchol z B se podíváme, jestli se vyskytuje na cestě M. První, který se vyskytuje je náš hledaný. Protože takto budeme zkoušet vrcholy z B od začátku do prvního společného města, složitost bude O(S_b R_m)

Toto je teoretická úloha. Není nutné ji programovat, odevzdává se pouze slovní popis algoritmu. Více informací zde.

36-5-4 Hackovaci soutez (11 bodů)

Kačka na poslední Smršti navštívila přednášku o háčkování. To ji velmi nadchlo, koupila si háčky všech možných velikostí a příze všech možných barev a začala každou chvíli svého volného času vyplňovat háčkováním. Kromě řetízkového stehu se naučila háčkovat různě dlouhé sloupky, ubírat a přidávat oka a vyzkoušela si i některé složitější vzory. O pár dní později už byl její pokoj plný malých háčkovaných chobotniček.

Dokážete si představit Kaččino nadšení, když na chodbě ve škole zahlédla plakát s velkým nápisem „Hackovaci soutez“. Samozřejmě dlouho nemeškala, na uvedené adrese se přihlásila a začala ještě více trénovat, aby ji na soutěži nic nepřekvapilo.

První podezření, že se někde stala chyba, pojala Kačka, když přicházela na místo soutěže. Místo lidí s košíky barevné příze, háčky a různobarevnými kusy oblečení všude okolo sebe viděla ostré hochy, ostrá děvčata a další ostré bytosti v černých mikinách, kteří u sebe neměli ani háčky, ani přízi, ale velké těžké staré notebooky. Další dávku podezření pojala na recepci, kde, když řekla, že přišla na „Háčkovací soutěž“, se na ní dívali poněkud zvláštně, než ji navedli správným směrem.

Všechno se vyjasnilo, až když soutěž začala a Kačka si přečetla zadání první úlohy. Vůbec totiž nebyla na Háčkovací, ale na Hackovací soutěži! Rozhodla se ale, že se jen tak jednoduše nevzdá a vyřeší alespoň jednu úložku. Pomůžete jí?

Na serveru běží následující program:

void print_flag1() { /* ... */ }

void print_flag2() { /* ... */ }

char skutecneheslo[40];

int main() {
	// ...

	bool ok = false;

	char heslo[40];
	printf("Zadejte heslo: ");
	gets(heslo);
	if (strcmp(heslo, skutecne_heslo) == 0)
		ok = true;
	if (ok)
		print_flag1();
	else
		printf("\nŠpatné heslo.\n");
}

Některé části kódu jsou úmyslně vynechané, celý zdrojový kód najdete zde.

K řešení máte k dispozici přímo zkompilovaný program, takový, jaký běží na serveru.

Vaším úkolem je zařídit, aby se spustily print_flag1() a print_flag2(), přičemž máte přístup pouze k standardnímu vstupu a výstupu programu, které jsou připojené přímo na TCP socket na adrese vm.kam.mff.cuni.cz a portu 13337. Na ten se můžete připojit například pomocí příkazu nc vm.kam.mff.cuni.cz 13337, na Windows pomocí PuTTY v režimu Raw nebo pomocí knihovny socket v Pythonu.

K řešení se vám bude hodit mít k dispozici nějaké Linuxové prostředí, nějaký disassembler (není potřeba nic složitého jako IDA nebo Ghidra, bohatě vám postačí objdump -S), abyste se mohli podívat, na jakých adresách jsou části programu uložené a debugger, například gdb, abyste se mohli podívat, co program dělá, když mu dáte různé vstupy. Zajímavé také může být prozkoumat knihovnu pwntools, ale tuhle úlohu zvládnete vyřešit i bez ní. Nakonec, nezapomeňte si přečíst naši novou kuchařku o práci s pamětí, která vychází součástí této série. Kdybyste narazili během řešení na nějaký problém, nebojte se zeptat na Discordu nebo emailem. Na Discordu ale dávejte pozor, abyste neodhalili část postupu řešení.

Tohle je experimentální open-data úloha. Když úlohu vyřešíte, vypadnou na vás dvě různé vlajky ve formátu ksp{.*}. Každá je správnou odpovědí na jeden ze vstupů v odevzdávacím systému. Odpověď na první vstup vypisuje funkce print_flag1() a na druhý vstup funkce print_flag2(). Když se vám podaří získat jenom jednu z nich, dostanete jen část bodů.

36-5-X1 Superstring (10 bodů)

Toto je bonusová úloha pro zkušenější řešitele, těžší než ostatní úlohy v této sérii. Nezískáte za ni klasické body, nýbrž dobrý pocit, že jste zdolali něco výjimečného. Kromě toho za správné řešení dostanete speciální odměnu a body se vám započítají do samostatných výsledků KSP-X.

Byl jednou jeden Medvěd a ten měl šuplík, kde schraňoval svou sbírku zajímavých řetězců. Teď zatřídil pár nových úlovků, ale co to? Šuplík už nejde zavřít. Napadlo ho, že když mají řetězce spoustu společných částí, mohl by je rozebrat na kousíčky a složit z nich jediný řetězec, v němž se budou nacházet všechny původní podřetězce. Jak ale takový řetězec najít?

Navrhněte algoritmus, který dostane n řetězců o celkové délce m znaků z nějaké malé konečné abecedy Σ. Na výstupu pak vypíše nejkratší možný řetězec, jehož (souvislým) podřetězcem bude každý ze zadaných řetězců.

Jelikož to v polynomiálním čase nikdo neumí (třeba budete první), spokojíme se s časovou složitostí O(2ⁿ·poly(m, |Σ|)).