---
tags: KSP, úlohování
---
# Úlohování 34. ročník

## Zásoba úloh z minulých úlohování

### Plivaci testy [použito na výběrku MO-P]
* Testování na Covid plivacími testy
* Každý student je pozitivní s pravděpodobností p
* Můžeme testovat množilu lidí a zjistíma, jestli v ní je někdo pozitivní
* Cíl: Na co nejmenší počet (ve strední hodnotě) dotaů najit všechny pozitivní.
* Možná modifikace: Je k nemocných a chceme je najit (worst case)

### Vyhodnocení fyzikálního měření

* Vstup:
* spousta datových bodů v 1D (čísla) -- pohádka: spektroskopie
* Výstup:
* najít všechny místa, kde jsou dostatečné shluky datapointů a tím odfiltrovat šum - potřeba dodefinovat, co to znamená
* Řešení:
* Pokud bude limitem threshold v nějak velkém okénku: Setřídit, posouvat okénkem po bodech, dokud nepřekonám treshold. Potřeba dát pozor, pokud to dalším posunutím vyroste.
* TODO: dorozmyslet, jaké by mělo být rozumné kritérium

### Sčítání [ZZ]

* sečíst 2 dlouhá čísla
* v Pythonu moc jednoduché, museli bychom definovat jinou matematiku (sčítat jabka s hruškami - like?)

### Autoškola [Z]

* autor: DK
* zadání
* jezdím v autoškole a nemám rád odbočování doleva, protože to je těžké
* raději najedu o kilometr více než abych odbočil
* najít nejkratší cestu
* podobná standardní úloze

### Žebřík v bludišti [Z]

* recyklovaná

### Fyzikální simulace [těžší než se zdá]

* odrážení míčku od stěn (bez zrychlení)
* simulace po malých krocích
* gravitace + odpor vzduchu
* udělat správně je těžké, nechceme učit špatné přístupy

### Kde pověsit hamaku [H]
* autor: SE
* mám les a chci najít body dostatečně, ale ne moc daleko od sebe a nesmí mi překážet jiný strom
* zatím nevěříme, že máme řešení

# Úlohy z 1. a 2. schůze

## Hledání fylogenetického stromu
Autor: OS

Máme zvířata, která mají pro dané geny různé alely (tedy např řetězce AAB, ABA, kde se zvířata liší v posledních dvou genech) a hledáme fylogenetický strom, který obsahuje co nejméně mutací -- tedy strom, kde listy jsou zvířata a kde součet editačních vzdáleností je minimální.

- Složitá, neznáme rychlé optimální řešení, možná jako kompetetivní

## Online převod z desítkové do dvojkové soustavy
Autor: XA
Dostáváme číslo v desítkové soustavě pouze po cifrách a musíme hned vypisovat cifry ve dvojkové soustavě.

## Binární vyhledávání, kdy dotazy jsou různě drahé
Autor: JK
Máme dvě pole, jedno veřejné, které říká cenu za dotaz na daný prvek, a druhé, ve kterém binárně vyhledáváme -- cílem je minimalizovat maximální cenu.

Umíme nejrychleji pouze v O(n^3)

--------------------------------------

## Úlohování 30. 3. 2022

### Nápad: Dokázat zase nějakou NP úložku

### DNA - modifikace sena, aby v něm nebyla jehla

* Máme dlouhý text a hledaný výraz
* Chceme v něm provést co nejméně editací, aby se v něm hledaný výraz nikde nevyskytoval
* pozor na to, že jednou editací můžu jeden výskyt smazat ale zároveň nový vyrobit
* Volitelně: máme povolené jen konkrétní modifikace (třeba A->T a G->T)

* Zjednodušená verze:
* povolím si "pálit/kaňkovat" písmenka = změnit písmenko na něco, co se zaručeně v jehle nevyskytuje
* řešení: hladové KMP, vždy spálím nejpravější znak v nalezené jehle -> tím ji určitě zruším a možná zruším i něco dalšího
* jako opendata: asi nebudeme umět odlišit KMP vs primitivní opakování `strings.find(seno, jehla)`
* jako teoretická: asi yb se jen odkazovali na KMP do kuchařky ale nezaručí nám to, že ho pochopí

### Obracení mincí na velké šestiúhelníkové ploše [Z]

* vstup:
* spousta posloupností kroků "sever 10, severovýcho 2, jihovýchod 3, jih 7" (prostě 6 směrů na šestiúhelníkové síti)
* když někam dojdu, tak tam obrátím minci a vrátím se na start
* po provedení všech posloupností kroků se ptám, kolik mincí je obrácených (dv)

## Úlohování 6. 4. 2022

### Nejdelší cenzura

* Máme algoritmus, který dělá to, že nahrazuje vždy nejlevější výskyt jehly zadanou náhradou (a vždy hledá nejlevější výskyt, který může vzniknout právě i nahrazením)
* Náš úkol:
* doateneme zadanou jehlu + náhradu + N délku textu
* máme vymyslet text délky N, na kterém se provede co nejvíce nahrazení
* máme slíbeno: jehla není substringem náhrady
* Protipříklad na spoustu triviálních přístupů:
* jehla -> náhrada: ab -> ba
* optimální vstup je asi aaaaabbbbb, který se přepíše spoustou přehození postupně na bbbbbaaaaa
* zatím jsme z toho nevymysleli žádnou fungující úlohu

### Černá díra v grafu

* Vstup: graf
* Cíl: najít silně souvislou komponentu, do které se jde dostat odkudkoliv, ale z níž už se nejde dostat nikam jinam
* Řešení:
* nejdříve kontrahujeme silně souvislé komponenty
* pak uděláme topologické uspořádání
* potřebujeme k tomu sepsat kuchařku na hledání silně souvislých komponent

### Povodí

* Vstup: DAG
* Výstup: stok s největším povodím (Každý vrchol "teče" k nejbližšímu stoku.)
* Řešení: Najít upořádání, projít od konce a určit hrany ke správnému stoku a nakonec projít popředu a sčítat 1 + součet na hranách vedoucích sem.

### Taneční

zdroj: staré ADSko JS

Další problém v tanečních. Probíhá pánská volenka, pánové se dohodli a každý si vybral právě jednu partnerku (jinými slovy již máme párování). Pánové stojí v řadě (od 1 do N) na jednom konci sálu, dámy (opět v pořadí 1 až N) stojí na druhém konci. Trasy pánů se ale mohou křížit (například, když si první pán vybere druhou dámu a druhý pán první dámu). Najděte co největší podmnožinu pánů, jejich trasy k partnerkám se nekříží a mohou tak vyrazit najednou.

* řešení: hledání nejdelší rostoucí podposloupnosti

---------------------------------------
---------------------------------------
---------------------------------------

# Vybrané úlohy 34. ročník

## Vybrané úlohy do 34-H5

### Lehátka [opendata, 9b]

zdroj: staré ADSko JS

Turisté u moře řeší vážný problém. Turistů se sešlo T na jedné pláži, na které se současně nachází L v řadě rozmístěných lehátek (nemusí být rovnoměrně rozmístěná). Lehátek je více, než turistů, ale problémem je, že všichni turisté jsou členy Klubu samotářů a tedy by každý z nich byl nejraději co nejdál od všech ostatních.
Pro pozice lehátek zadané na vstupu (třeba v metrech od levého konce pláže) najděte rychlý algoritmus, který z L lehátek vybere T takových, aby vzdálenost mezi dvěma nejbližšími obsazenými byla co největší možná.

* Řešení: binární vyhledávání jaká největší vzdálenost je ještě použitelná k rozmístění turistů
* test pro vzdálenost X: umístím turistu na první lehátko a pak v čase O(L) procházím lehátka a když nasčítám vzdálenost alespoň X, umístím dalšího turistu... a testuji, jestli umístím všech T O(L)
* lepší test pro vzdálenost X: při hledání nejbližšího dalšího lehátka binárně hledám první vzdálenější než X od současného - O(T * log L)
* půlení závisející na vzdálenostech: min = vzdálenost dvou nejbližších, max = (vzdálenost prvního a posledního)/T
* pro opendata to bude stačit, protože log maximální vzdálenosti bude max 64...
* lepší půlení: ???

### Stíhání událostí [opendata, 10b]

* máme graf, hrany ohodnocené dobou cesty, a události, které se odehrávají ve vrcholech v nějakých časech
* několik variant:
* a) Události jsou bodové, chci jich stihnout co nejvíc
* b) Události mají délku v celých minutách, za každou minutu strávenou na události vydělám 1 kredit, chci vydělat co nejvíce kreditů
* řešení a):
* předpočítám si cesty v celém grafu (mezi každou dvojicí vrcholů)
* setřídím si události podle času
* provádím dynamiku po událostech (každý krok v O(počet událostí))
* v každé události si držím číslo, kolik nejvíce událostí stihnu, když budu touhle končit
* vždy když přidávám událost, tak si zkontroluji časy dojezdu ze všech událostí a podle toho nastavím nové číslo do téhle
* na konci vyberu maximum ze všech událostí
* řešení b):
* podobně jako v a) jenom si rozmyslím, že se mi vyplatí v každé události hladově počkat až do jejího konce (všechny události jsou stejně cenné)
* vybraná varianta: události mají délku v minutách, ale pro první 2/3 vstupů platí, že délky události bude vždy 1 minuta

### Ohodnotit graf, aby byl jednoznačný [teoretická, 13b]

* viz ulohy/JK-010-dalnicni-poplatky
* máme neohodnocený graf a zadané dvojice vrcholů v něm
* mezi každou dvojicí vrcholů může existovat více nejkratších cest
* chceme vymyslet ohodnocení hran grafu tak, aby v ohodnoceném grafu platilo:
* mezi každou ze zadaných dvojic už existuje jen jedna unikátní nejkratší cesta
* tato nejkratší cesta je jedna z nejkratších cest v původním grafu
* řešení s dlouhým výsledkem:
* i-tou hranu odotnotím jako 2^i+n*2^n
* řešení v O(MN^2):
* všechny hrany chci ohodnotit milion + něco (tím si zafixuji počet hran na nejkratší cestě)
* potom začnu s kostrou, všechny hrany na ní ohodnotím třeba stejně
* zkonstruuji si tabulku NxN vzdáleností mezi vrcholy, pamatuji si počet hran a ohodnocení dosud nejkratší cesty
* pak přidávám hrany, jedno přidání hrany bude stát O(N^2)
* vytvořím si pole N^2 kandidátů na očíslování této hrany
* zkontroluji všechny dvojice vrcholů:
* pokud přidáním této hrany vznikne cesta s menším počtem hran -> vše ok, tohle bude nová nejkratší cesta (musím ji na konci tohoto kroku algoritmu aktualizovat v tabulce)
* pokud přidáním této hrany vznikne cesta se stejným počtem hran -> vyškrtnu si z pole kanditátů takové číslo, které by vytvořilo stejně dlouhou cestu (nemusím vyškrtnout žádné, pokud jsem si kandidáty zvolil jinak)
* pokud přidáním této hrany vznikne cesta s větším počtem hran -> vše ok, nejkratší cestu nemám jak rozbít
* projdu pole a očísluju hranu některým ze zbylých čísel

### x [teoretická, 13b]

* Původní varianta:
* Vstup: N čísel
* Existuje N^2 celočíselných podílů x_i // x_j -> chci jejich součet jako jedno číslo
* Vybraná varianta (půjde lépe zapohádkovat):
* vstup dva seznamy čísel A a B
* můžu udělat |A|x|B| celočíselných podílů a_i // b_j -> chci součet podílů jako jedno číslo
* Řešení: Ondra umí O(N \log N + K * log N log K), K je maximální hodnota na vstupu
* seřadíme čísla a spočítáme+deduplikujeme duplicity
* Pro všechny b_j spočteme rychle součet a_i // b_j přes všechna i
* Všimneme si, že počet možných výsledků je jen K / b_j
* Pro všechny takové výsledky si zjistíme levý a pravý okraj toho, která a_i dávají daný výsledek. Následně k celkovému výsledku připočteme výsledek * počet a_i která daný výsledek dávají
* Přes všechna b_j je složitost předchozí části součet počtu výsledků přes všechna b_j krát log n. Jenžé součet počtu výsledků přes všechna b_j lze odhadnout ze shora jako součet harmonické řady o K prvcích a tedy výše uvedená složitost.

------------------

## Vybrané úlohy do 34-Z5

### Jednoduchý splitwise [Z, opendata 8b]

* Skupina kamarádů na výletě, společné náklady platí pokaždé někdo jiný
* Vstup: Dostaneme seznam nákupů, cílem je určit "stav účtu" pro každého (jen kolik dluží/má dostat, ne kdo komu) ve formátu `<částka> <kdo platil> <za kolik lidí> <jména lidí...>`
* jména jsou sekvence písmenek anglické abecedy (řeší to v Pythonu, stringem můžou snadno indexovat)
* příklad:

    800 adam 3 adam beda cyril
    200 cyril 1 adam

* Výstup: vypsat pro každého, jehož jméno se objevilo výše, kolik dluží (částka v mínusu) nebo kolik má dostat (v plusu)
* TODO implementace: vyhnout se zaokrouhlovacím chybám -> částka vždy musí být dělitelné počtem lidí na řádku
* Řešení: za každou operaci příčíst celou částku platícímu a odečíst částku/počtem lidí od každého člověka

### Otáčení papíru [Z, opendata, 11b]

* Máme průhledný čtvercový papír ležící na stole, na němž je napsáno písmeno "b"
* Provádíme operace (vše je z pohledu člověka sedícího u stolu):
* orotuj papír o 90° doprava (R)
* orotuj papír o 90° doleva (L)
* horizontální otočení (H) = zvedni papír, otoč ho podle levopravé osy a polož ho zpět na stůl
* vertikální otočení (V) = zvedni papír, otoč ho podle předozadní osy a polož ho zpět na stůl
* Vstup: číslo N a pak N řádků každý popisující jednu "seanci s papírem":

  3
  RLLLHLLVHLL
  HHVHVLLVHVV
  RRHRHRHRHRHV

* Ptáme se, v jakém otočení papíru skončíme:
* zavržená verze: je to stejné otočení, jako na začátku?
* vybraná verze: Je na papíru vidět nějaké písmeno b, p, q, nebo d? Nebo je tam neexistující písmeno (N = neplatné)?
* Řešení:
* držet si, která strana je nahoře (rub/líc) a kde je třeba původní vrchní hrana
* vymyslet, co s tím dělají jaké operace a lineárně je aplikovat
* vymyslet tabulku o 8 prvcích (rub|líc)x(nahoře|vlevo|dole|vpravo) říkající, jaké je tam písmenko, jde udělat ručně s papírem ;)
* TODO: je potřeba v zadání mít jasný obrázek b, p, q a d (musí být jasné, že na sebe jdou otáčet)

### Počet nových mostů [Z, opendata, 11b]

* Cíl: jednoduchá grafová úloha, hlavně aby si procvičili implementaci
* Zadání:
* Ostrovní království má spoustu ostrůvků (vrcholy) a mezi některými jsou postavené mosty
* Po velkém hurikánu spousta mostů popadala
* Dostaneme zadaný graf (ostrůvky a mosty) ve stavu po hurikánu a ptáme se, kolik mostů musíme postavit, aby království bylo opět souvislé
* Vstup: graf (klasicky jako seznam hran)
* Výstup: počet mostů, které musíme postavit
* pozor: je potřeba určitě neodpovídat "málo" nebo "moc", aby na tom nešlo vyhledávat
* Řešení: v O(N+M) spočítat komponenty pomocí BFS/DFS, vrátit počet komponent -1

### Teoretická: Recyklace "obsahu psa" 27-Z2-6 [Z, teoretická, 14b]

* Recyklace https://ksp.mff.cuni.cz/z/ulohy/27/zadani2.html#task-27-Z2-6
* Zadání:
* dostaneme obrazec ve čtvercové síti zadaný obvodem
* obvod je zadaný obcházením (2m východně, 3m severně, 2m východně, 4m jižně) a máme slíbeno:
* na konci opět dojdeme do startovního bodu
* obrazec se nikde nekříží
* ptáme se na obsah tohoto obrazce (bude celočíselný, je to ve čtvercové síti)
* Řešení: viz https://ksp.mff.cuni.cz/z/ulohy/27/reseni2.html#task-27-Z2-6
* TODO: udělat zadání co nejméně podobné 27-Z2-6 (aby nešlo vygooglovat)
* přepohádkovat
* změnit obrázek
* je to těžké, ale věříme, že se dá vymyslet i bez speciálních znalostí (naopak možná přílišné znalosti přemýšlení ztěžují, ozkoušeno :D)

## Vybrané úlohy do 34-4

### Odsazování pseudokódu [praktická, 9]

* Na vstupu zdroják v pseudokódu podobném Pythonu, který se skládá buď ze řídících příkazů (jsou vždy ukončené dvojtečkou a musí za nimi následovat odsazený blok) nebo normálních příkazů
* Ptáme se, kolik existuje validních odsazení tak, aby za každým řídícím příkazem byl odsazený blok o alespoň jednom příkazu (řídícím nebo normálním)
* Řešení: kvadratická dynamika
* TODO: dopsat detaily

### Experti [teoretická, 10]
* Chceme jednodušší variantu
* TODO: Nutné přepohádkovat
#### Z mailu od Ríši:
Rozhodli jsme se, že se dáme na meteorologii, a následujících T dní
budeme předpovídat, zda bude pršet, nebo ne. Háček je, že o počasí nic
nevíme, zato známe m expertů, kteří každý den také zveřejňují svoje
predikce na následující den. Konkrétně každý den, v tomto pořadí:

- zjistíme, co předpovídají ostatní experti (každý expert předpovídá
"bude pršet"/"nebude pršet")
- uděláme vlastní predikci ("bude pršet"/"nebude pršet")
- zjistíme, jestli pršelo, nebo ne

O důvěryhodnosti jednotlivých expertů nemáme valného mínění, ale jsme
přesvědčeni, že je mezi nimi aspoň jeden, který má vždycky pravdu [lehčí
varianta] / udělá nejvýše r chyb [těžší varianta]. Chceme vymyslet
online algoritmus, který celkem udělá málo chyb / ne o moc víc chyb, než
nejlepší expert.

#### Řešení
Téhle úloze se říká experts problem a pod tím názvem se dá taky
vygooglit. V lehčí variantě umíme dosáhnout log m chyb: budeme si
udržovat množinu potenciálních "nejlepších expertů", kteří ještě
neudělali chybu, a při nové predikci si tipneme to, co říká nadpoloviční
většina. Pak platí, že pokud uděláme chybu, tak tím vyloučíme alespoň
polovinu z potenciálních nejlepších expertů, takže po log m chybách nám
zbyde jen ten správný a od té doby už žádnou chybu neuděláme.

U těžší varianty umíme něco jako O(OPT + log m) chyb, kde OPT je počet
chyb nejlepšího experta. Budeme vlastně dělat něco podobného, ale místo,
abychom rozlišovali lidi na "možná nejlepší experty" a lháře, budeme mít
u každého člověka váhu, jak moc mu věříme. Na začátku má každý expert
váhu = 1 a pokaždé, když expert udělá chybu, se jeho váha půlí. Při
rozhodování, co ten den predikovat, sečteme váhy expertů pro "ano" a
porovnáme s váhami expertů pro "ne", a tipneme si výsledek s větším
součtem. Dá se zanalyzovat, že tohle povede na O(OPT + log m) chyb,
zjednodušeně na jednu stranu součet vah na konci nemůže být moc malý
(protože je aspoň (1/2)^r za toho experta, co udělá jen r chyb) a
zároveň každá naše chyba součet vah zmenšuje hodně (na ≤3/4-násobek),
tudíž chyb nemůže být hodně.

### Korelace nejsou tranzitivní [praktická, 11]

* Na vstupu:
* množina korelací "A koreluje s B s faktorem 0.25" (čím více A tím více B) včetně záporných korelací "C koreluje s D s faktorem -0.8" (čím více C tím méně D)
* Výstup: Posloupnost tvrzení, kde každá dvojice spolu dostatečně koreluje, přitom poslední je negací prvního
* Chceme v korelacích najít spor - objevit cyklus "čím více X tím méně X"
* poselství úlohy je ukázat, že tranzitivita na korelacích je blbost
* Je docela těžké vysvětlit zadání, na úlohování to chvíli trvalo
* Řešení:
* Komponenty souvislosti
* Najít dvojici A A' v jedné komponentě a mezi nimi cestu

### Geometrie [teoretická, 15]
* Kuchařka: Geometrické algoritmy
* Je zadaný nekonvexní mnohoúhelník
* Cílem je najít řez přímkou, takový, aby mnohoúhelník rozdělil na co nejvíc částí
* Lehčí varianta [8b]: Řez bude vodorovný
* Řešení:
** Lehčí: Zametání
** Zobecnění: Uvažujeme všechny natočení mezi směrnicemi každých dvojic bodů
*** Vezmeme všechny úhly spojnic mezi všemi dvojicemi bodu
*** Víme, že průběh zametání se mění jen když otočíme přímku přes směr nějaké spojnice -> mezi dvojicí sousedních úhlů spojnic (po seřazení) uvážit pouze jeden směr
*** Plný počet bodů za O(n^3 log n), za lepší řešení bonusové body

### KSP-X
* Tentokrát nebude
* V případě, že nikdo neodevzdá předchozí úlohu, vydáme hint

## Vybrané úlohy do 34-Z4

### Halleyova kometa [Z, opendata, 8 bodů]

* Máme kometu, která se zjevuje každých K let (třeba 76 :)) a ptáme se, kteří ze zadaných lidí ji mohli za svůj život vědět
* Vstup:
* startovní rok R a perioda komety K
* N intervalů let udávajících, kdy žil který člověk
* Výstup:
* počet lidí (ze zadaných), kteří kometu mohli za svůj život vidět
* Poznámka:
* do zadání jasně specifikovat, jestli bereme ostré nebo neostré nerovnosti

### Lokomotivy na dlouhé cestě [Z, opendata, 12 bodů]

* Na vstupu:
* Množina lokomotiv s jejich dojezdem v km (na kolik jim vystačí uhlí v tendru)
* Množina tratí s jejich délkami
* Úkol:
* Spočítat, kolik existuje možností jak rozmístit lokomotivy na tratě
* Řešení:
* Od nejdelší tratě, vím že poslední trať může ujet K lokomotiv, takže počet možností je K * řešení téhož pro zbytek tratí mínus jedna lokomotiva (ať alokuji na poslední trať jakoukoliv z těch K, tak se řešení pro zbytek nezmění).

### Diskrétní simulace [Z, opendata, těžká, 12b]

* Na vstupu zadané bludiště - věznice s hlídači
* Pro strážce platí nějaká jednoduchá pravidla typu:
* pokud to jde, udělá krok dopředu
* pokud je před ním zeď, otočí se doleva
* Ptáme se na to, jak bude bludiště vypadat (kde budou strážci) po N krocích
* prvních pár vstupů dostatečně malé N, aby šla diskrétní simulace
* další vstupy s N tak velkým, aby to už nešlo
* Řešení:
* Pro každého hlídače si najdu, kdy se poprvé dostane na stejné políčko se stejným otočením, dostanu periodu P (a ocásek O :))
* Podělím N/O, dopočítám kde bude stát
* Vrchní časový odhad: počet hlídačů * velikost mapy (ale velmi pravděpodobně to bude o hodně menší)
* Poznámka:
* V zadání upozornit, že vstupy od BÚNO 4. budou mít velmi velké N

### Kamínky [Z, teoretická, 12 bodů]

* Z Wiki
* Zadání: Máme tabulku RxS, na některých políčkách jsou nerozlišitelné kamínky. Umíme zrotovat (cyklicky posunout) libovolný řádek nebo sloupec o libovolný počet políček. Najděte posloupnost rotací, která ze zadané pozice kamínků vytvoří zadanou cílovou.
* Poznámky:
* Hledáme jakoukoliv poslopnost operací, nikoliv nejkratší
* V zadání zdůraznit, že chceme nějak exaktněji popsat algoritmus/postup

## Vybrané úlohy 34-3

### Rekurzivní úředník [opendata, 10b]

* Pokračování úlohy 34-Z2-2 Podivná brigáda
* **Zadání:**
* Máme dva úředníky a hromadu na sebe položených papírů s úkoly
* Každý úkol má čas, jak dlouho ho trvá vyřídit (čím delší, tím obtížnější)
* Když úředník nemá co dělat, tak si vybere úkol a pustí se do něj
* Vybírá tak, že se podívá na vršek hromady a listuje úkoly tak dlouho, dokud nachází snadnější úkol (s menším časem), ten si vezme (tedy vezme si první úkol, pod kterým už není lehčí), zbylé úkoly nechá v původním pořadí
* Ptáme se na to, v jakém pořadí úkoly vyřídí
* **Řešení:**
* projdeme úkoly a rozsekáme na segmenty s klesající obtížností
* každý takovýto segment vždy zpracujeme odzadu
* pak stačí simulovat práci dvou úředníků a kdy se jim uvolní místo na další úkol
* řešení v O(N)

### Faktoriál [opendata, 11b]

* Vstup: Číslo $N$ a základ číselné soustavy $K$
* Slíbíme, že se vejde do int128, doporučíme python+bigint
* POZOR: Výstup se tam musí taky vejít!!!! Pozor v implementaci!
* Výstup: Počet nul na konci zápisu $N!$ v číselné soustavě o základu $K$
* **Řešení:** ???

### Síly ve vlaku [teoretická, 12b]

* Autor: OS
* Kuchařka: Vyhledávací stromy
* **Zadání:**
* Stojíme ve vlaku, v jednom směru jsme schopni vydržet nekonečnou sílu, v druhém sílu *F*
* Víme v jakých časech bude v jakých směrech působit jaká síla
* Mezi jakýmikoliv dvěma časy se můžu pootočit o libovolný úhel (tak, abych byl schopen další působení síly ustát)
* Ptáme se, o jaký nejmenší úhel je nutné se v součtu otočit, abychom ustáli všechny síly?
* **Řešení:**
* v $O(n \log n)$ pomocí stromů
* TODO: rozvést
* Alternativní (nevybraná) možnost: chceme minimalizovat počet otočení -- jde hladově v O(n)

### Záškodník v bipartitním grafu [teoretická, 12b]

* autor: JK
* **Vstup:**
* graf o kterém tvrdíme, že byl bipartitní a pak do něj někdo přidal jednu hranu
* Chceme najít jednu hranu, kterou když z grafu odstraníme, tak bude opět bipartitní (nemusí to být nutně ta původní hrana)
* **Řešení:**
* ???

### Seriál [15b]

* vyrobí Tom

### Optika [X, teoretická, 10xb]

* Autor: Pali
* **Zadání:**
* máme graf a v něm vyznačený vrchol (centrálu)
* chceme spojit centrálu s každým vrcholem po hranách grafu drátem s nějakou barvou
* po žádné hraně nemůže vést více drátů stejné barvy
* chceme minimalizovat celkový počet různych použitých barev
* **Motivace:**
V meste je jeden DSLAM a N bytoviek prepojených M chráničkami. Tzn. graf s N+1 vrcholmy a M hranami. Z DSLAMu chceme do každej bytovky natiahnúť jednu telefónnu dvojlinku (bez prerušenia, point-to-point) pre pripojenie DSL modemu. Aby sme nemali problém s rozoznávavím káblov v chráničkách, tak požadujeme aby v každej chráničke sme nemali dva káble jednej farby. Koľko druhov farebných káblov budeme potrebovať na pripojenie všekých bytoviek do DSLAMu? Predpokladajme, že káble sú dostatočne dlhé; chceme minimalizovať počet druhov káblov.
* **Řešení:**
* Pali: tokmi (myslíme si, že máme polynomiální řešení)
* Medvědovo řešení:
* Binárně vyhledávám minimální počet barviček.
* To, zda stačí K barviček, testuji takto:
* Vyrobím síť, která obsahuje K kopií grafu chrániček.
* Každá kopie má podrozdělené vrcholy, aby vrcholem mohla projít nejvýše 1 cesta.
* Ze zdroje natáhnu hrany s kapacitou +∞ do všech kopií DSLAMu.
* Z každé kopie vrcholu natáhnu hranu s kapacitou 1 do pomocného vrcholu, z pomocného vrcholu hranu s kapacitou 1 do stoku.
* K barviček stačí ⇔ existuje tok velikosti K.
* JK má prý také nějaké řešení

## Vybrané úlohy 34-Z3

### 1. Otočená morseovka [Z, opendata, 8 bodů]

* na vstupu text z písmen a-z
* ptáme se, jestli když text zakódujeme do morseovky, otočíme a dekódujeme, jestli vyjde ten stejný text
* varianty (vybere implementátor):
* na vstupu více řádků, za každý z nich odpověď ano/ne
* na vstupu jeden dlouhý řádek, na výstup ho vypsat po zakódování, otočení a dekódování (za neexistující písmenka vypsat ?)

### 2. Tečkový displej [Z, opendata, 10 bodů]

* tečkový displej ve vlaku (2D mřížka diod), něco zobrazuje
* displej je starý, takže některé diody jsou vyplé i když by měly svítit
* máme k dispozici seznam názvů zastávek, co tam můžou být zobrazené (zadané taky jako 2D mřížky bodů) a ptáme se, jestli je to co vidíme na displeji jednoznačné
* inspirace: https://bergen-open21.kattis.com/problems/bergen-open21.glitchingscreen

### 3. Tabulky a olympiáda [Z, opendata, 12 bodů]
* máme fyziku popsanou jednoduchými vzorci
* chceme sekvenci na získání výsledku (jeden konkrétní identifikátor)
* na vstupu dostaneme vzorečky co platí
* operace: +-*/
* identifikátory jsou tvořeny z posloupností písmen anglické abecedy
* tvaru vstupu: ccc=aa+b (kde ccc, aa a b jsou různé identifikátory)

### 4. Velikost plachet [Z, teoretická, 14 bodů]

* máme množinu stěžnů nějakých výšek a množinu ráhen nějakých šířek
* když zkombinujeme stěžeň výšky V a ráhno šířky Š, tak na ně můžeme pověsit plachtu o ploše VxŠ
* vymyslete algoritmus, který dostane množinu stěžnů, množinu ráhen a nakombinuje je tak, aby celkový součet velikostí plachet byl co největší
* důležitou součástí řešení je dokázat, že vymyšlený algoritmus vrátí ten nejlepší výsledek

## Vybrané 34-2

### 1. Cesta (Skupinová jízdenka) [H]

* autor: VK
* zadání
* dva (hardcore: tři) kamarádi jedou ze školy do svých domovů
* chtějí jet co nejdéle spolu, pak jim čas ubíhá zdánlivě pomaleji
* minimalizujeme vnímanou dobu jízdy
* řešení
* třikrát Dijkstra

### 2. Lezení [H]

* autor: OS
* zadání
* jako na Olympiádě, konečné pořadí je určeno součinem pořadí z jednotlivých disciplín
* znám výsledky prvních dvou disciplín
* kolikátý nejhorší můžu skončit, když vyhraju poslední disciplínu
* varianta: když budu v poslední disciplíně n-tý
* řešení
* binární vyhledávání

### 3. Průniky n-úhelníků (Na hroších pláních)[H]
* teoretická
* máme mnoho n-úhelníků s jejich polohou a obsahem
* jaký bude obsah jejich průniků
* je to geometrie a bude to chlupatý opruz

### 4. Brněnská procházka [H]
* autor: SE & JP
* soutěžní optimalizační úloha (opendata)
* cílem je najít nejdelší indukovanou cestu v ohodnoceném grafu -- tedy co nejdelší cestu, která má vzdálenost nesousedících vrcholů minimálně 2 (na žádnou nepoužitou ulici se nedíváme z obou směrů)
* vstup je statický, jde o mapu Brna a okolí vyextrahovanou z OSM -- tedy jde o skoro rovinný graf
* je kompletně implementovaná
- máme i dvě orgořešení (SE a JP), přišlo nám to jako zábavná úloha
* SE-000-opt-brnenska-prochazka v gitu /ulohy/, kde je i kompletní zadání

## Vybrané 34-Z2

### 1. Hledání podintervalu [Z] 7
* dostanou zadanou množinu intervalů a periodiku bodu
* kdy se potkají

### 2. Úředník a žádosti [Z] 11
* dva úředníci, kteří mají hromadu na vyřízení
* když uředník nemá co dělat, vezme si další úkol
* každý úkol má čas potřebný na vyřízení
* celkový čas

### 3. Plnění krabic v obchodě [Z] 13
* na pásu jedou krabice u kterých víme jaké přijedou
* mi můžeme vzít naší krabici a dát ji do jedoucí

### 4. Neobarvení negrafu [Z] 13
* teoretická
* i se zdůvodněním pravdivosti
* musíme se vyhnout slovům: graf, bipartitní a obarvovat