1. FFT (DFT, inverze, FFT, aplikace)
2. Máme šachovnici s chybějícími políčky. Jak na to položíme domino?
3. Máme profil výšky na horách, chceme zjistit nejčastější výšku.
(Je to prostě lomená čára, která je zároveň funkce)
Mé řešení, které asi není moc optimální, ale na pěknou známku s trochou přesvědčování stačilo.
1. Tady chtěl dost definice, složitosti i malý důkaz. To se nedá udělat jinak než si to přečíst.
2. Lze řešit perfektním párováním. To obecně trvá dlouho, ale lze to i nacpat do bipartitního grafu a za pomocí FF na O(n^4)
3. Úloha na barvení intervalů/zametání roviny. Stačí si udělat projekci a pak jen počítat otevírání a uzavírání závorek. O(n log n) za třízení podle výšky.
1. FFT (DFT, inverze, FFT, aplikace)
2. Máme šachovnici s chybějícími políčky. Jak na to položíme domino?
3. Máme profil výšky na horách, chceme zjistit nejčastější výšku.
[img]https://www.vyletnik.cz/data/trasy/cyklo/krusne-hory-zapad//Magistr%C3%A1la%20%28Kr%C3%A1sn%C3%A1%20-%20B.Dar%20-%20M%C4%9Bd%C4%9Bnec%29-profil.jpg[/img]
(Je to prostě lomená čára, která je zároveň funkce)
Mé řešení, které asi není moc optimální, ale na pěknou známku s trochou přesvědčování stačilo.
1. Tady chtěl dost definice, složitosti i malý důkaz. To se nedá udělat jinak než si to přečíst.
2. Lze řešit perfektním párováním. To obecně trvá dlouho, ale lze to i nacpat do bipartitního grafu a za pomocí FF na O(n^4)
3. Úloha na barvení intervalů/zametání roviny. Stačí si udělat projekci a pak jen počítat otevírání a uzavírání závorek. O(n log n) za třízení podle výšky.