Zkouška 10.1.2014 Mareš
Napsal: 17. 1. 2014 13:51
1. Goldberg -- popis, formulace všech lemmat a jak zajistit rychlou implementaci (stačí držet seznam vrcholů s nenulovým přebytkem a v každém vrcholu seznam vrcholů, kam jde převádět + vrcholy mají odkaz na své položky)
2. Maximální vlastní prefix, který je zároveň suffix stringu -- KMP lineárně
3. Máme červené a zelené body v rovině, jak najít přímku, která body rozdělí podle barvy? -- To bylo trochu tricky, jedno správné řešení: Najdu konvexní obaly barevných množin, konvexní obal všech. Ten druhý má jen 2 hrany, které nejsou ani v jednom barevném obalu. Od okraje jedné takové hrany posunuji přímku podél hrany barevného obalu. Koukám, kde mi případně vlezla do druhého barevného obalu a posunu ji do dalšího bodu po směru toho obalu. Tak se na každou hranu v "průřezu" podívám max. 1, takže celkem nlogn.
2. Maximální vlastní prefix, který je zároveň suffix stringu -- KMP lineárně
3. Máme červené a zelené body v rovině, jak najít přímku, která body rozdělí podle barvy? -- To bylo trochu tricky, jedno správné řešení: Najdu konvexní obaly barevných množin, konvexní obal všech. Ten druhý má jen 2 hrany, které nejsou ani v jednom barevném obalu. Od okraje jedné takové hrany posunuji přímku podél hrany barevného obalu. Koukám, kde mi případně vlezla do druhého barevného obalu a posunu ji do dalšího bodu po směru toho obalu. Tak se na každou hranu v "průřezu" podívám max. 1, takže celkem nlogn.