FFT (DFT, inverze, FFT, aplikace)
Máme šachovnici s chybějícími políčky. Jak na to položíme domino?
Máme profil výšky na horách, chceme zjistit nejčastější výšku.
https://www.vyletnik.cz/data/trasy/cykl ... profil.jpg
(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.
Tady chtěl dost definice, složitosti i malý důkaz. To se nedá udělat jinak než si to přečíst.
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)
Ú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.