zadani velkeho prikladu:
behem prazdnin mate v planu navstivit takove koncerty abyste si poslechly co nejvice muziky... kazdy den stihnete maximalne 1 koncert
koncerty se nachazi v ruznych mestech mezi mesty se vzdy da prejet behem jednoho dne
na koncertu se vzdy hraje nekolik skladeb daneho zpevaka
ohodnoceni koncertu je suma delky vsech pisnicek
za prazdniny muzete najet maximalne 2000 km...
mezi kazdymi dvema mesty existuje cesta celociselne delky ne vsak nutne prima trat
pocet pisnicek max 10000
pocet dnu 92
pocet zpevaku max 100
pocet mest max 100
na jednom koncertu max 100 pisnicek
pamet 5MB (relativne volne omezeni, kdyz nestaci je mozno v nouzi pouzit vice)
nastin reseni...: ano uloha MA polynomialni algoritmus...
timto beru vsem vcetne me
kteri se snazili najit nejakou heuristiku iluzeholanovo reseni vyuziva trirozmernou tabulku indexovanou dny mesty a kilometry...
ustni zkouska:
holan si nebyl jist korektnosti meho reseni maleho prikladu ale nakonec se nechal presvedcit ze program funguje
u velkeho byl zklaman ze jsem neprisel na lepsi algoritmus nicmene moji heuristiku uznal jako celkem rozumny napad.. je vazne v pohode.. kazdou myslenku s vami rozebere a vetsinou pripocita fiktivni kladne body
pak se me zeptal na dynamicke programovani
a nasledne prohlasil ze je to mezi 1 a 2 a zeptal se na vytvoreni haldy v case o(n)... na to jsem si vzpominal jen ztuha ale nakonec jsem to dal dohromady
nejdulezitejsi je jak uz tu bylo nekolikrat napsano neprustrelne reseni maleho prikladu... obtiznost malych prikladu je velmi rozmanita.. je to o stesti...
k velkemu je pak dulezite alespon neco rozumneho napsat... nemusi to byt zrovna to optimalni i s tim se da na zkousce uspet
na ustni se hlavne nestresovat...
jenom si myslim ze je z psycholgickeho hlediska velmi prijemne mit za sebou pred velkym solidne vyreseny maly priklad.. zvlast pokud velky nebyl snadny... co jsem mluvil se spolubojovniky tak nikoho polynomialni reseni nenapadlo...