Skúška 29. 5. 2017 - Voľby

Opakovalo sa zadanie volebná kampaň:

http://forum.matfyz.info/viewtopic.php?f=247&t=8279

Riešenie:

Najprv si vypočítame vzdialenosti medzi mestami Floyd-Warshallom, čo nám dá maticu, ktorá zaberie kopu miesta. To sa dá vyriešiť tak, že si zapamätáme iba dolný trojuholník z tej matice, čo vychádza na 1MB. Taktiež si zotriedime meetingy chronologicky podľa konca.

Samotné riešenie využíva dynamické programovanie a spočíva v tom, že prechádzame meetingy od prvého do posledného. Máme dve možnosti: na meeting ísť alebo ho vynechať. Pozrieme sa na prekryv meetingu s tými pred ním (tie za ním neriešime). Ak vieme ísť na viac meetingov vynechaním toho, ktorý skúmame tak si zapamätáme doterajšie maximum (uložené s indexom predchádzajúceho meetingu. V opačnom prípade si zapamätáme maximum z meetingov, ktoré sa s nim neprekrývajú + 1 za daný meeting. Zároveň je dobré si pamätať, na ktorom meetingu sme boli naposledy, aby sme vedeli postupnosť meetingov zopakovať. Zistenie, či sa niečo prekrýva je triviálna aritmetická operácia, ale treba myslieť na dĺžku cesty medzi mestami.

Dôležitý postreh: máme daný začiatok kampane a vieme, že potrvá menej ako 31 dní. Teda dátumy vieme reprezentovať ako minúty po začiatku kampane, čo sa zmestí do 2B intu.

Pamäťový limit je 2,5 MB, čo mi najprv znelo odstrašujúco, no je to reálne:

• • 1MB na dolnú trojuholníkovú maticu vzdialeností

• • 0,2MB na tabuľky vytvárané DP (najväčší počet meetingov pre daný meeting a meeting, na ktorom sme boli naposledy)

• • 0,3MB prioritná fronta s predošlými meetingami - tu pomôže mať dátum ako 2B integer

plus zanedbateľné tisíciny ako názvy miest atď

Detaily si rozmyslite ako cvičenie :)

Ku skúške: Holan bol naozaj milý a snažil sa pochopiť moje riešenie do tých najmenších detailov. Ako teoretickú otázku som dostala vonkajšie triedenie.

http://www.geeksforgeeks.org/weighted-job-scheduling/

Také sem hodím své postřehy ze zkoušky.

Zadání jsem předem neznal a napadlo mě jen toto.

Pomocí Floyd-Warshalla spočítat vzdálenost mezi každými dvěma městy. Když začnete popisovat svůj program s Floyd-Warshallem, určitě tím Pergela a Holana potěšíte, při nejmenším já tím Pergela potěšil.

Na backtracking v tomto případě zapomeňte, za to by vás prý rovnou vyhodili. Mě nenapadlo nic lepšího, než si vytvořit jakousi tabulku (dynamické programování), kvůli které jsem bohužel několikanásobně překročil povolenou paměť.

Začal jsem s posledním meetingem a u něj jsem si poznamenal, jak se na něj můžu dostat, respektive z jakých meetingů se na něj mohu dostat. To udělám jednoduše tak, že projedu prostě všechny meetingy před tímto a k času konce toho meetingu připočítám vzdálenost mezi oběma meetingy. To je jednoduché ...
Do prvního meetingu se nemohu dostat nijak.

Pak jsem jen od konce hledal nejdelší cestu...

Pergelovi se to celkem líbilo, tedy až na tu paměť, kvůli tomu mi snížil hodnocení písemky na 2. Ale tak mimo soutěž mi řekl, že kdyby tu písemku zadával on, nechal by nám kubickou paměť, nebo by to dal bez omezení.
Asi to není optimální řešení, takže se ho rozhodně nepokoušejte napodobovat. Ale můžete se tím inspirovat a nějak to vylepšit. Řešení v prvním příspěvku bude určitě lepší.

Z teorie mi vybral třídění založené na porovnávání dvou prvků.

Dostal jsem otázky:

1. Definice O, {: alt="\Omega" type="image/"}, {: alt="\Theta" type="image/"}

2. Definice složitosti problému

3. Dolní odhad složitosti třídění (chtěl i důkaz !)

4. Horní odhad složitosti třídění (dokáže se nějakým alg., třeba mergesortem nebo heapsortem)

Zkoušel mě tedy Pergel a to jsem opravdu vyhrál. Byl strašně v pohodě. V písemce se vůbec nešťoural, během dvou minut jsme to prolítli. Skoro mě ani nepustil ke slovu, abych mu vysvětlil Floyd-Warshalla :D
Oproti tomu Holan, co jsem tak slyšel, se v písemce docela šťoural. Co jsem taky slyšel bylo to, že docela dost lidí na tom mém termínu vyletělo. Ale tím nikoho nechci strašit.

Má rada je, nepodceňujte přípravu na teorii, jako jsem to udělal já. Zkouška se zdá býti lehká - a ona i "lehká" je, ale pouze tehdy, když se na ni pečlivě připravíte. Ve finále jsem byl rád, že mě Pergel poslal domů s trojkou.

Cítim potrebu vyjadriť sa k niektorým veciam, nech je tu viac pohľadov na vec:

Speedding wrote: Když začnete popisovat svůj program s Floyd-Warshallem, určitě tím Pergela a Holana potěšíte, při nejmenším já tím Pergela potěšil.

Holana to práveže nezaujímalo, hneď sme to preskočili a šli na hlavnú časť, ktorá mu pripadala podstatnejšia.

Speedding wrote: Zkoušel mě tedy Pergel a to jsem opravdu vyhrál. Byl strašně v pohodě. V písemce se vůbec nešťoural, během dvou minut jsme to prolítli. Skoro mě ani nepustil ke slovu, abych mu vysvětlil Floyd-Warshalla :D
Oproti tomu Holan, co jsem tak slyšel, se v písemce docela šťoural. Co jsem taky slyšel bylo to, že docela dost lidí na tom mém termínu vyletělo. Ale tím nikoho nechci strašit.

Je pravda, že Holan sa zaoberá písomkou až do detailov, ale rozhodne to nie je nič odstrašujúce. Skôr by som povedala, že sa ten algoritmus snaží pochopiť, aby ho zhodnotil čo najobjektívnejšie. Hľadá chyby, ale aspoň mne dal príležitosť mu vysvetliť, ako by som ich opravila. Nemyslím si, že by sa snažil niekoho vyhodiť.

Speedding wrote: Má rada je, nepodceňujte přípravu na teorii, jako jsem to udělal já. Zkouška se zdá býti lehká - a ona i "lehká" je, ale pouze tehdy, když se na ni pečlivě připravíte. Ve finále jsem byl rád, že mě Pergel poslal domů s trojkou.

Tento výrok je veľmi rozumný a zaslúži si byť zdieľaný. Ak sa pripravíte, tak sa nemáte čoho báť :)

patuchen wrote: Je pravda, že Holan sa zaoberá písomkou až do detailov, ale rozhodne to nie je nič odstrašujúce. Skôr by som povedala, že sa ten algoritmus snaží pochopiť, aby ho zhodnotil čo najobjektívnejšie. Hľadá chyby, ale aspoň mne dal príležitosť mu vysvetliť, ako by som ich opravila. Nemyslím si, že by sa snažil niekoho vyhodiť.

To neříkám, jen jsem tím chtěl říct, že když se vám nepovede písemka, tak u Pergela máte i tak šanci uspět. Samozřejmě v té písemce musí být nějaká rozumná myšlenka, na které by se dalo stavět.
Holan mě nezkoušel, tak nemůžu soudit.

Btw. k tvému prvnímu příspěvku, nepotřebuješ na matici vzdálenosti 2 MB? 1000 * 1000 * 2 B, protože nejdelší vzdálenost mezi dvěma městy je 500 minut a to se ti do 1 B nevejde. Ale to je jen detail, do limitu se vejdeš i tak.

Speedding wrote:

Btw. k tvému prvnímu příspěvku, nepotřebuješ na matici vzdálenosti 2 MB? 1000 * 1000 * 2 B, protože nejdelší vzdálenost mezi dvěma městy je 500 minut a to se ti do 1 B nevejde. Ale to je jen detail, do limitu se vejdeš i tak.

Tento problém je zodpovedaný hneď na začiatku, viď priložený quote. Každopádne, ďakujem za upozornenie, napíšem to jednoznačnejšie.

patuchen wrote:

Najprv si vypočítame vzdialenosti medzi mestami Floyd-Warshallom, čo nám dá maticu, ktorá zaberie kopu miesta. To sa dá vyriešiť tak, že si zapamätáme iba dolný trojuholník z tej matice, čo vychádza na 1MB. Taktiež si zotriedime meetingy chronologicky podľa konca.

Jo sorry, to jsem nějak přeskočil :D