Zkouška 13. 6. 2011

Ahoj světe!

Tak dneska jsme chytali zločince v londýnském stylu (tj. kamera na každým rohu):
http://forum.matfyz.info/viewtopic.php? ... f92679db22

Jen abych odpověděl na poslední dotaz z výše zmíněného threadu ohledně opravy časů kamer (já jsem se taky před pár dny divil, že v podstatě nejdůležitější část úlohy byla v odpovědi takhle odfláknutá:).

Ono to totiz NEJDE. Tedy ne vzdycky - napr. pokud dostanu vsechny kamery se spatnym casem, sotva to muzu nejak zjistit. Ovsem takove pripady jsou skoro vzacnejsi nez suda cisla mezi prvocisly. Ale da se rict (a uplne to same napadlo i Topfera), ze jsou takova kvanta dat (kazdych 5 min 1000000 zaznamu, a to po dobu aspon 1 dne), ze temer vzdy se nam podari odhalit vsechny kamery. Ted priblizne jak se to da resit...

Nejprve, jedina relevantni data pro nas jsou casy, ID kamer a c. pasu. Posledni 2 si jeste nahradime poradovymi cisly od 1 do 1M (vnejsi trideni -> seskupena stejna ID/cisla pasu za sebou, a to vzestupne -> v kopii tohoto souboru to budeme psat s prislusnym poradovymi cisly). Seradime podle porad. cisel lidi, jako 2. kriterium porovnani bude cas zaznamu -> seskupi se nam to do celkoveho cestovniho logu/itinerare kazdeho jednotliveho cloveka.

Ted pujdeme "po jeho stopach" a protoze je zajimave, jen kdyz se osoba presouva mezi krizovatkami, budeme si vsimat dvojic po sobe jdoucich krizovatek/kamer (a do nejakeho pole priznaku [1..1M] si znacit '?', 'T', 'F', podle toho, co jsme o kamere zjistili). Clovek muze jit od:

(1) Spravna kam. (se spravnym casem) => spatna kam. .... v takovem pripade dotycny jakoby na 10 min zmizi (pac 2. kamera ma o 5 min vetsi cas, nez by mela mit). To je dobre, ponevadz muzeme definitvne tyto 2 kamery oznacit, vime, ktera je ktera.

(2) Spatna kam. => spravna kam. ... dotycny se objevi na 2 mistech "najednou". Vime jen, ze kamery jsou opacnych typu, ale nevime ktera je ktera. Ale i to nam muzu poslouzit (budu si pamatovat takove pary a jakmile jednou jednu z nich budu mi pozdeji urcenou, urci se tim i druha).

(3) Spatna => Spatna nebo Spravna => Spravna ... dotycny jde s prodlevou 5 min (jakoby normalne). Opet nevime, ktera je ktera, ale vime, ze jsou stejneho typu. Podobne jako ve (2) si muzeme pockat, az jednu z nich budu uz mit urcenou a tim i urcit druhou.

Ty (ne)korespondujici pary si klidne muzeme pamatovat na disku jako dluhy k vyreseni, az budeme vse ostatni uz mit hotove.

Ty je vse k oprave kamer -> proste musime DOUFAT, ze mame dost info, coz jako asi mame. Mozna jste nekdo vymyslel nejake dalsi optimalizace / heuristiky, klidne se pochlubte...

Zbytek reseni uz byl zminen drive, jen v rychlosti:

Seradim podle casu (2. krit. porad. c. kamer) -> sekupeni lide, kteri jsou v danou chvili spolu na dane krizovatce.

S predpokladem, ze vsechny casu uz jsou spravne (potrebuju u muzea poznat cas C pro oznaceni spravneych podezreleych), si v nejakym poli bool who_is_podezrely[1..1M] oznackovavam postupne podezrele. Zacnu u muzea v case C, oznackuju, v case C+5 si na jednotlivych krizovatkach oznackuji pritomne komplice (pamatuju si, kde mi zacinala krizovatka, kdyz narazim na pritomneho podezreleho, oznackuju celou krizovatku lidi), v case C+10 znova atd. atd.

V case 18:00 na CANu se kouknu, je-li tam nekdo mezi podezrelymi (pozor, ne driv, ne pozdeji - podezreli by mohli z CANu odejit uz driv & lup nenechaji jen tak na zemi).

Asi takhle, Topfer rikal, ze priblizne takhle to melo asi vypadat - jsem za to rad:)

Jo, a na ustnim toho byly haldy:)

Definice, indexovani v poli, heapsort (slozitosti u Insertu a u ExtractMinu), jde halda vystavit v {: alt="O(N)" type="image/"}? - jde, Tarjanuv alg. (ale jmena pry nikoho nezajimaj:), haldy o vyskach K se stavi s z haldicek vysek K-1 (viz Topferovy slidy), lze u haldy udelat Delete (ukaze se na nejaky konkr. prvek, lze smazat?) - lze, nahradi se poslednim prvkem v poli pro zachovani tvaru a musi se zabublat (to je takovy trikovejsi, zalezi pripad od pripadu, je-li mensi nez otec, zarotuju nahoru, vetsi nez syn, zarotuju dolu).

Za 1: mega-ultra-velka spokojenost, myslel jsem, ze jsem pisemnou zkazil, neb jsem si myslel, ze moc nezvladl opravit ty casy kamer, ale ono to obecne nejde vzdy vyresit.

P. S. Doporucuji jit na ustni ten samey den, nejlepe co nejdriv po obede, to si ty papiry jeste nestihnou tolik precist a clovek se z toho jeste zvladne vykecat. A chcete-li si vybrat, ke komu jit, tak myslim, ze sloupec, co zacina dyl (od 13:00, ne od 12:30) patri zkousejicimu, co jeste musi na obed, a to je prave ten, co dozoruje u pisemky jako druhy. Ale je to v podstate jedno, oba dva jsou to strasni hodni a mili panove :D

Souhlas snad se vším, co jsi napsal. Pořád ještě si myslím, že bych ty opravy kamer ani teď nenaprogramoval, protože to je strašnej hnůj. Jen detail: v 1) když občan zmizí na 10 minut, tak se pak může objevit na dvou kamerách, z nichž jedna je správně a druhá zpožděná, takže jednoznačně lze určit jen tu vstupní (jako správnou), tu výstupní ne vždycky. Po asi 20 minutách rozboru písemky, kdy by mi klidně mohl dát za 3 kvůli pomalýmu a nejistýmu ošetřování kamer a častýmu lezení do souborů, se Holan zeptal, co je halda a jak rychle ji umíme vyrobit (jednoslovná odpověď "lineárně" mu stačila) a psal za jedna. Doteď tomu moc nevěřím! :D Ke komu půjdete je asi dost jedno, když tam neni Kryl. :wink: A myslim, že mě zachránilo, že jsem šel jako druhej, protože úterní písemky už budou mít přečtený a dá se čekat, že každej bude mít pořádně připravený řešení a obhajobu..ale nechci strašit..
P.S. Ten postřeh s tím, kterej sloupeček je kdo, je dost dobrej, to mě nenapadlo :)

mathemage wrote:Jo, a na ustnim toho byly haldy:)

Definice, indexovani v poli,

Jo, tady bacha, mala zaludnost na Ceckare -> indexuje se samozrejme od 1, paklize bych to vzal od 0, tak mam opakovanekrat indexy {: alt="2\times\2\times\dots\times2\times0=0" type="image/"} :P

Překvapila mě věc, na kterou se mě doc Topfer zeptal na ústním: Vyhodnocení infixového výrazu. Řekl jsem mu po chvíli dumání, že bych v rekurzi hledal nejméně prioritní operátor a sestavoval z toho strom výrazu, a ten pak vyhodnotil. To prý že je hezké, ale jde to v lineárním čase.
Na to mě nic nenapadlo, takže jsem v té otázce neuspěl. Prý se to dělá buď převodem na postfix nebo nějakou vychytralou rekurzí (nepamatuju si jak to nazval).
Ale byl na mě opravdu hodný, v písemce jsem měl správně jen to co jsem opsal tady z fóra, co jsem vymyslel sám bylo vesměs špatně (např. celé opravování kamer). Pojal to jako 2 až 3, a po neúspěchu u ústního mám 3.
vojta

vojta_vorel wrote:Překvapila mě věc, na kterou se mě doc Topfer zeptal na ústním: Vyhodnocení infixového výrazu. Řekl jsem mu po chvíli dumání, že bych v rekurzi hledal nejméně prioritní operátor a sestavoval z toho strom výrazu, a ten pak vyhodnotil. To prý že je hezké, ale jde to v lineárním čase.
Na to mě nic nenapadlo, takže jsem v té otázce neuspěl. Prý se to dělá buď převodem na postfix nebo nějakou vychytralou rekurzí (nepamatuju si jak to nazval).

Jo, to je bohuzel zrovna jedna z tech veci, ktery by clovek z fleku nevymyslel. Zminuje se o tom ve svych slidech, bud:

(a) prevod na postfix (cisla se zapisuji ve stejnym poradi jako jsou v infixu + zasobnik na operatory, pushnu pri kazdym novym operatoru, predtim si ale popnu operatory s stejnou ci vyssi prioritou, kdyz narazim na ukoncovaci zavorku, popnu ze zasobniku vsechny op. az k nejblizsi otevirajici zavorce) = O(N); nasledne vyhodnoceni v postfixu (cisla a mezivysledky na zasobnik, operace vzdy na 2 cisla na vrcholu zasobniku) = O(N)

nebo

(b) neprima rekurze (nejak vyraz = soucet clenu; clen = soucin faktoru; faktor = cislo nebo vyraz -> z toho se prirozene provede neprima rekurze jednim pruchodem) = O(N)