Zkouška 26.5.2008

Název zadání: Knižní veletrh

• 10 spisovatelů rozdává na veletrhu autografy

• veletrh je čtvercová síť 20×20 políček

• o každé osobnosti víme, kdy přijde a jaká bude jejich trasa, tj. políčko, na kterém se zjeví a posloupnost písmen NSEWX (sever, jih, východ, západ, stát na místě) reprezentující jejich pohyb

• všechny časy dané "číslem kroku"

• autogram získám, když stojím ve stejný čas na stejném políčku jako nějaká osobnost, klidně může být více lidí na stejném místě, můžu získat víc autogramů najednou

• každý autogram má nějakou cenu

• program má naplánovat trasu, jak sebrat autogramy s co největší celkovou cenou

VSTUP: textový soubor, každá osobnost má jeden řádek:

• číslo kroku, kdy přijde

• políčko, na kterém začne

• trasa

• cena autogramu

VÝSTUP: textovýá plán trasy

• délka trasy

• cena nasbíraných autogramů

• políčko, kde začnu

• trasa

OMEZENÍ:

• 10 osobností

• veletrh má rozměry 20×20

• délka tras osobností <= 100

• osobnost může přijít v kroku od 1 do 5000

• paměť k dispozici: 27 MB

• cena autogramu je <= MAXINT/10

• priority řešení: 1. co největší cena, 2. nejkratší čas odchodu z veletrhu

• začínám v kroku 1

Hmm..ty jo..no ja to mel v 10!*100, takze socialni.... pochlubte se, kdo to ma nejak lip....

Vsadil som na vrabca v hrsti: Popisal som "hladovy algoritmus" (to znamena - odchytavam autora s najcennejsim podpisom, ktory sa nachadza na veltrhu) s tym, ze som v diskusii napisal, ze by sa rozmymi modifikaciami a zlepseniami (napr. vyber startovacieho policka nielen podla casu objavenia prveho autora, ale aj podla ocenenia podpisu jednotlivych autorov; v pripade troch atutorov na vystavisti odchytit dvoch s memsimi podpismi, ktory vsak mozu mat sucet cien vacsi ako ten treti...) dali nachadzat lepise vysledky.

Ako ste ulohu riesili vy? Je niekto isty tym, ze ma optimalne riesenie? ;)

10!*100? To by nebylo špatný... mě to vyšlo kolem 10!*10^20 v nejhorším případě... v průměrnym by to mělo být mnohem lepší (ořezávání)

Já jsem to řešil tak, že jsem si nejprve vygeneroval stavový prostor veletrhu v poli 5 100 x 20 x 20, kdy každá matice 20 x 20 zachycuje stav veletrhu v jednom kroku. Mohu si to představit jako graf, kde z každé bodu matice 20x20 vede nejvýše pět hran do bodů následující matice 20 x 20. Vzhledem k paměťovému omezení není možné graf reprezentovat poitry a zůstaneme v tomto poli. Hrany mají váhu buď nula nebo váhu autogramů, které využitím této hrany získám.

To, kde je která osobnost si pamataju jako bity ve dvoubytovém integeru. Když je tam nula, nikdo tam není.

Samotnou cestu hledám průchodem pole do šířky, kdy heldám nejdelší (resp. nejhodnotnější cestu) v co nejmenším počtu kroků. U každého vrcholu vyzkouším všechny jeho následníky, když by se tím zvýšila jeho hodnota, zapíšu příslušný vrchol jako jeho předchůdce na cestě. U každého vrcholu si kromě osobností, které tam v tu chvíli jsou nebo nejsou pamatuju předchůdce na na nejdelší cestě. Aby mohl algoritmus řádně probíhat, je nutné si pamatovat i jaké osobnosti jsme na cestě potkali a jaké je momentální délka nejdelší cesty do každého z vrcholů - ale kdybych si tyto údaje pamatoval u každé z vrcholů, opět by došlo k překročení paměťového limitu. Stačí si pamatovat údaje ve dvou nesvrchnějších vrstách šířící se vlny (jde udělat třeba sudá - lichá).

Průchod do šířky končí nalezením bodu, kdy jsem potkal všechny osobnosti nebo dojde až dokonce. V poslední matici 20 x 20 vyberu vrcholy které mají nejvyšší délku cesty a procházím ty cesty pozpátku - z těchto cest vyberu tak, která kobnčí dříve (resp. dříver přestane růst) a to je ta správná.

Využil jsem vlastně celou možnou paměť 27 MB.

Časová složitost 5100 * 20^2 * 5

10! * 10 * 101, takže řádově 10^10 - není to zřejmě optimální, ale myslím, že je to celkem dobrý, když máš ještě o řád míň, tím líp ;-)

Všechny permutace pořadí spisovatelů, ve kterém je navštívím, a pro každou permutaci musím každého navštívit co nejdřív.
Permutací je 10!, každého spisovatele musím navštívit v některém z max. 101 kroků, kdy je na veletrhu, a spisovatelů je 10.

A samozřejmě se to dá hodně ořezat, ale nevymyslel jsem takový ořez, aby mi klesla složitost v nejhorším případě - leda bych to musel počítat nějak amortizovaně.

Cabroušek: nojo, takhle to asi půjde... ale nějak mě to tam nenapadlo... holt co naděláme, že?

Jo hele v pohode, ja to udelal obycejnou hloubkou ale s orezavanim, takze na slozitost se radsi ani neptejte. No na to, ze to slo dynamicky tak to asi hloubka nebude optimalni reseni... Kua...

Ten příklad mi přijde docela brutální - můžete prosím blíže specifikovat jak dlouho na to bylo, jak to celé probíhalo, jak vypadá ústní kolo a jaké bylo skóre zúčastněných? Snad toho nechci moc, jen krátký report. Díky moc!

No prijdes tam rano v 9, zkousejici si te odskrne, pak si vemes papir, nekam se posadis.
Za chvili rekne zadani prikladu s tim, ze se muzes ptat a on ti to upresni. Pokud se nezeptas, tak v programu nemuzes predpokladat, ze neco plati, takze lepsi se ptat. Jinak do zaverecny analyzy poznamenat, ze si predpokladal vstup omezenej treba jen na < 255 autobusu, nebo co ja vim. Pak napise zadani na tabuly a taky tam napise sablonu jak ma vypadat shrnovvaci papir - tj. papir na ktrej napises dekompozici ulohy, diskuzi o volbe algoritmu o prubehu resen atd atd. Po 2 hodinach odevzdas a po odevzdani se zapises na takovej pejpr co tam zkousejici ma. Sou tam dva sloupecky. Kazdej sloupecek ma 3 sekce - pro kazdej den jednu - a je dale clenenej podle hodin, kdy prijdes na ustni. Obecne se nevi, jestli pravej sloupec znamena, ze budes zkousenej Topferem, nebo Holanem.

Mně to taky přišlo jako dost brutální... jenže ono není... stačí to dobře nahlédnout - a je to za chvíli. To nahlédnutí se mi nepodařilo - důvod je ten, že neumím násobit dvěma...

Bol uz niekto na ustnej casti skusky? Kto vas skusal a co sa pytal? ;) Nech vieme, ake otazky su tento rok v oblube :D

Písemnou část jsem dělal přímočaře s jednoduchou heuristikou: místo zkoušení všech 10! pořadí jsem zkoušel jen max. po N (např. 4) nejbližších spisovatelích a z toho v každém kroku šel k prvnímu nejvýhodnějšímu. Töpferovi se řešení líbilo (prý by hodnotil 1-), ale heuristiku komentoval tak, že je v podstatě zbytečná, že 10! možností se projít dá... Takže i to nejpřímočařejší zkoušení všech možností asi projde. Taky navrhoval rozdělit situaci podle intervalů, kdy na veletrhu žádný spisovatel není (což bude většina času) a zkoušet pořadí po částech zvlášť.

Na ústní se ptal na vnitřní/vnější třídění, grafové algoritmy... no nic překvapivého, všechno je v sylabu. Často chtěl odvodit složitost.

Ja jsem byl na ustnim dneska, zkousel me Holan.
Nejdriv si vzal k ruce moji pisemku a mel jsem mu popsat, jak jsem to resil - v prubehu popisu do toho obcas vstoupi, aby se na neco zeptal, pripadne
aby uvedl protipriklad a take si prubezne procita, co je v pisemce skutecne napsano (aby nekdo nepopisoval jine reseni, nez napsal do pisemky :D ), urcite je dobre zminit se o slabinach zvoleneho algoritmu (minimalne tak zkousejiciho pripravite o poteseni z ukazani prikladu, na kterem vase reseni selze), mne to, ze jsem si chyby a slabiny uvedomoval, pricetl k dobru.
Po analyze pisemky se prejde k teorii, konkretne me se zeptal na haldu - tak jsem mu popsal reprezentaci bin. stromem a polem, pak chtel ukazat nejaky konkretni priklad a na nem demonstrovat insert a delete minima, dale se ptal na trideni haldou (tj. heapsort) - princip, casova narocnost...
Jeste se ptal na to, jak postavit haldu v linearnim case, ale to uz jen tak bokem.
Celkove bych ustni hodnotil jako prijemnejsi cast zkousky (oproti pisemce), spise se tam da vase celkove hodnoceni zlepsit, nez zhorsit (teda aspon takovy pocit jsem mel ja)

HonzaK: jak se dela to vytvareni haldy v lin. case? jen se pridavaji prvky a nic se nedela? Dik

Myslím, že ta halda v lin. čase spočívá v tom, že se staví odspoda (takže u heapsortu odzadu)

Him wrote:HonzaK: jak se dela to vytvareni haldy v lin. case? jen se pridavaji prvky a nic se nedela? Dik

Dela se to, jak to Holan nazval, "ucetnickym trikem":
Vyjde se z toho, ze pri reprezentaci haldy temer uplnym bin. stromem se velka cast vrochlu nachazi bud v posledni hladine (tj. jsou to listy), nebo predposledni hladine - celkem to vzhledem k exponencialnimu rustu poctu vrcholu vzhledem k hladinam dela n/2 vsech vrcholu, ktere se uz vemou, ze jsou na svem miste, tj. cas na jejich umisteni je 0 (pri reprezentaci polem to odpovida druhe polovine pole). Dale se vezmou vrcholy, ktere tvori zbytek predposledni hladiny a cast predpredposledni - tech je n/4 a na vlozeni kazdeho z nich potrebujeme max 1 prohozeni (s nejakym vrcholem, ktery uz v hlade je). Pak se vezme dalsich n/8 vrcholu (na umisteni kazdeho z nich potrebujeme max 2 prohozeni), pak n/16 atd.

Tedy celkem je potrebny cas: 0n/2 + 1n/4 + 2*n/8 + ... coz je O(n)

Takze tak nejak... :wink:

Kdybyste někdo náhodou chtěli brát moc vážně to řešení, co jsem tam napsal, tak to neděleljte, není dobře :oops: ... Ale kdyby se to kapánek předělalo, tak to bude fungovat dobře. A mohlo by to mít ještě mnohem menší složitost, jelikož je mnoho tahů, kdy se vlastně nic neděje.

Lidi, dá se na téhle zkoušce vyletět?

U Topfera to asi možný je... když zvoráš ten algoritmus, tak budeš muset bojovat o 3 (pokud nepůjdeš rovnou)... ale to jsem tak slyšel... já byl u Holana

Mohli byste někdo, kdo už má tuhle zkoušku za sebou napsat z čeho jste se učili, atp? Hlavně moc nechápu, jak moc podrobně to musí být u té písemné části rozebrané. Jestli stačí napsat např. teď si vygeneruju stavový prostor, a prohledávám do hloubky, nebo tam bazírujou na detailech?

DÍK

No musí bejt jasný, jak bys to udělal. Aby z toho bylo vidět, že si uvědomuješ, jak konkrétně by se to napsalo, jak přesně by vypadaly datové struktury, aby z toho byla vidět složitost... Určitě nebazírujou na detailech, musí tam bejt to podstatný, to důležitý. Pokud nějakou důležitou věc ohledně řešení budeš vědět akle nenaúpíšeš ji tam, tak to není dobré. Já osobně jsem popsal asi 6 těch velkejch stránek a musel jsem si během toho ořezávat tužku, ale myslím, že jsem to psal zbytečně moc podrobně. Každopádně káš 2 hpdiny času, to toho člověk stihne napsat dost, mě by byla stačila hodka a půl.
Na písemku jsem se neučil. Na ústní jsem se učil z poznámek a ze slajdů co má topfer na stránkách, a co se týče těch stromů a takovejch těch datovejch struktur, tak na to jsem kouk v Algovision.

rozhodne nebazirujou na detailech ale musi bejt videt ze vis jak bys to udelal.
jiank z tech peti tematovejch okruhu co tam mame napsat (postrehy, algoritmus, ds, atd atd) jsem mel jeden a pul a stejne, jelikoz jsem tam mel vsechno dulezity, tak to bylo za jedna.

Máte někdo tušení, jak aspoň začít s řešením tohohle příkládku? Nějak vůbec nevím, kde začít a dle čeho navyšovat. Díky
Zadání: http://forum.matfyz.info/viewtopic.php?t=1885