Zkouska 06-21

[Trupik]

Tak co, co jste tam dneska vytvorili?
Ja kulovy....

Pro ty co tam nebyli:

Na vstupu seznam ulic ve meste ( ulic < 10000, krizovatek <1000 ), ulice maji jmeno a odkud a kam vedou, jsou jednosmerne (obousmerne budou v seznamu pro kazdy smer zvlast)
Kazda ulice ma "prutok" - kolik na ni muze maximalne projet aut za hodinu - a taky cenu, kolik bude stat rozsireni ulice takove, ze tam projede za hodinu o auto vic
Z jedny strany vede do mesta dalnice a z druhy strany vyjizdi.

A ukol: mate X penez a mate urcit, ktere ulice za tyhle penize rozsirit, aby mestem mohlo projet co nejvic aut.

Reseni? Rad bych nejake videl...

[Eubie]

Já sem nějaké řešení stvořil, vlastně dokonce dvě, jedno sice nenašlo to jednoznačně optimální řešení za nějakých velmi speciálních podmínek ale jinak našlo řekl bych skorooptimální. To druhé našlo optimum podle mě vždy, ale jelikož šlo o prohledávání všech možností, výsledku by se asi nikdo nedočkal. První řešení jsem rozvedl, mělo kvadratickou složitost, paměti sem použíl jen půlku (bylo dáno 256 kB), tak jsem si říkal "Je to v suchu".

Pak přišel Kryl.
Pár lidí mi před Krylovou pracovnou říkalo, že nemá moc rád holky (obecně) a kluky v obleku (můj případ). Vejdu dovnitř, v malý písemce mi našel jednu chybu (nepředával sem něco odkazem, ale to sem si sám našel a řekl, proč je to chyba, takže by se to možná dalo hodnotit jako že sem to tam zapomněl, resp to sem si myslel). Pak jsem měl chybu na jednom řádku v programu na 1,5 A4. Sice by kvůli tomu program nefungoval, ale rozumnej člověk to jednou pustí, vidí že to nejede a hned to uvidí, jenže pustit to z papíru to nejde. Čtyřka mne poměrně nemile vyrazila dech (za dvě chyby takovýho kalibru). Kryl navíc celý malý příklad prokládal "Človeče počkej, dyť ty tady vůbec neděláš tohle a tamto", vždycky sem mu na to odpověděl "Ale jo, jenže to je tady" (o dva řádky níž) - rád studentům přidává sebevědomí.

Velký příklad - jak jsem psal, myslím že moje řešení bylo aspoň na tři určitě, spíš bych ho odhadoval na dvě. Aniž bysme se dostali k jádru věci a začali mluvit o algoritmu, Kryl mě asi 2x přerušil a řekl že dělám něco špatně (Holan řekl mít více algorimtů a jeden rozebranej, Kryl říká mít jeden a rozebranej, takže když máte víc a jeden rozebranej, máte to podle Kryla blbě pochopený). (mimochodem jeden ze dvou profesorů co na MFF tykají, druhej je tělocvikář Stehno). Jak jsme se prokousávali mým řešením nepamatuju se na větu, do níž by mi neskočil a neřekl "Máš to to blbě, počkej...". Třeba něco vysvětlujete "Zavedu si tohle a tohle" a on řekne "Ale to máš blbě, na co bys to zaváděl?" předtím než by člověk vysvětlil, k čemu to vůbec bude. Tak se mi nějak podařilo doříct můj algoritmus, ale z toho co Kryl říkal bylo vidět že ho očividně nechápe (protože jednoduše to nebyl ten jeden algoritmus, kterej on zná a za nic na světě ho nevymení). Nakonec jsem podlehl jeho věčným "Máte to blbě, koukněte na protipříklad" (kterej nic nevyvracel, ale já jsem to v tu chvíli po důkladné masáži mého sebevědomí neviděl) a vzdal jsem neuskutečnitelnou obhajobu uznal jsem "No jo, máte pravdu.".
Navíc mi Kryl celou dobu říkal "Tys to ale taky blbě pochopil, protože si vem, že ty řidiči taky přemejšlej, oni nepojedou do nějaký prdele jen aby se skrz město dostali, prostě to musíš brát z praxe taky, joooo?" (citace) Uznal bych možnou pravdivost tohoto výroku, kdybych se sám na zadávání problému Holana neptal "A jak se chovají řidiči, hledají nějakou nejkratší cestu?" Holan odpověděl "Ne, jde jim jen o to, aby měli kudy projet, klidně to může bejt dlouhá cesta, jen nechtějí stát v zácpě."

Závěr: Ani se mě neptal na ústní, protože i velký příklad byl samozřejmě na čtyři a to už prej zkoušel s jinýma a nedopadlo to dobře.

KONKLUZE: Nenoste na zkoušku oblek, holky by na zkoušku měly doufat v Holana. Modlete se ať vymyslíte přesně to řešení, který má Kryl nacacheovaný v hlavě, jinak máte smůlu, protože on to vaše jednoduše nepochopí a i kdyby, pokud nebude řešit úlohu na 100% dokonale, nemáte šanci. Nenechte se zmást jeho kecama, že to máte blbě, pokud si myslíte, že to máte dobře, přehlídnete pak snadno chybu v jeho úvaze. A nemyslete si, že to co napíšete do papíru je něco pro ně podle čeho vás hodnotí, to moje ani nečetl a to jsem byl první na řadě.

Přeju všem co chytí Kryla, aby to dali.

P.S. Aby nevznikly nějaké domněnky o tom, že sem hlupák co si myslel že dá zkoušku a přitom nic neumí a teď brečí:) uvádím svoje známky k 15.6. 1 - LA, C++, ALG, 2 - MA.

[Eubie]

Jen bych rád doplnil, že poté co jsem slyšel dokonalé řešení, které mám od kolegy, který tento problém večer před zkouškou konzultoval s jedním doktorandem, můžu navíc doplnit, že to dokonalé řešení je téměř identické s tím, které jsem navrhl jako to složitější (jen jsem špatně odhadl složitost).
Co se to děje se světem?:)

[Isidor]

Fuh... sila
btw zapisoval si sa do laveho alebo praveho stlpca?

[Hugo]

ja to resil takhle (nevim, zda dobre, na ustni jdu zitra, ale dle me to je nadejne).
Pomoci DFS, najdes cestu mezi D1 a D2 - na ni najdes min - hranu si zapamatujes a v grafu oznacis treba 0, potom jedes znovu DFS, pricemz pres 0-hrany nejdes a opet ukladas minima na nalezenych cestach a pak az DFS skonci, najdes si z tech zapamatovanych hran nejlacinejsi a budujes, dokud nevyrovnas prutok. Kdyz na jedne ceste, je hran se stejnym min vice, sectu je a pripadne buduji rovnomerne. Tohle je asi tak zaklad...

[Eubie]

Fuh... sila
btw zapisoval si sa do laveho alebo praveho stlpca?

Do levého, zapisuje tam Holan, takže pokud chceš do pravéh, je nutné si vybrate termín, na kterém už někdo je a levá kolonka je už zaplácnutá. Ale třeba to termín z termínu mění, kdo si vezme který sloupeček.

[dr.Bik]

No, já nevim, jak to řešit, ale zkuste zagooglit "Toky v sítích" anglicky "Net flow", myslim, že tahle teorie by to mohla dost zjednodušit. Ale to budem brát až v druháku...

[LuKu]

...nemá moc rád holky (obecně) a kluky v obleku...
...mimochodem jeden ze dvou profesorů co na MFF tykají...

Tak teď se fakt modlím, aby na mě zítra vyšel Holan. I když se obávám, že mi to se známkou nepomůže, Holan mě v tom možná jen míň vykoupe.
Co mi ale vrtá hlavou je ten Kryl - taky jsem z několika stran slyšela, že nemá rád holky, ale když jsem ho měla v zimě na zápočtovej test, tak byl úplně v pohodě a jsem si stoprocentně jistá, že mi vykal. Nemá dvojníka

[Isidor]

Fuh... sila
btw zapisoval si sa do laveho alebo praveho stlpca?

Do levého, zapisuje tam Holan, takže pokud chceš do pravéh, je nutné si vybrate termín, na kterém už někdo je a levá kolonka je už zaplácnutá. Ale třeba to termín z termínu mění, kdo si vezme který sloupeček.

Dik. Je to celkom mozne... uvidime vo stvrtok. Som "vpravo"...

Toky v sietach tiez prave studujem

Ja som si tam nasiel jeden maximalny tok (niecim podobnym ako Dijstra) a na nom kriticku(-e) hranu(-y), tzn. tie ktore to brzdia. A tiez, ako velmi to brzdia, tzn. pokial este ma zmysel to rozsirovat (druha najuzsia hrana). Kriticke hrany som si zapamatal a potom cely ten tok odobral (odcital od hran priepustnost toho minima), tym sa minimalne jedna hrana vynulovala a hladal som znova. Ked uz neostala ziadna cesta z D1 do D2, tak som zacal rozsirovat tie zapamatane hrany, od najlacnejsich. Ak ostali nejake peniaze, tak sa islo hladat znova...
No ale myslim, ze optimum to nenajde. Skor len nejaka rozumna heuristika...

[Kate]

toky v sitich (hledani maximalniho toku a podobne vykriky do tmy) bylo asi to jedine, co dnes muj velky priklad vytahlo z uplneho bahna zapomneni a ctyrky .... nejsem si jista, ale myslim, ze driv se prave toky ucily uz v prvaku - ten predmet se jmenoval nejak "teoreticka informatika/uvod do ..." (prosim, kdyz tak me opravte, jestli se pletu). takze je mozne, ze na programku pak zustal tento priklad proste zapomenuty
...
nicmene, co se tyce rudly kryla, mam s nim zatim sice jen dobre zkusenosti (v zime byl slusny, dokonce i vykal (! ), ale to asi jen proto, ze v zime ten program proste bud fungoval, jak mel a nebo ne, kdezto tady je to hodne o okecavani/vyjadrovani/nalade zkousejicich atd.

jsem si 100% jista, ze mit dneska kryla, tak to nedam. holan byl ale skvely, ne mekky, ale bylo videt, ze ma zajem nechat si veci vysvetlit, ze uznava, kdyz nekdo neco ma trochu jinak, ale ne vyrazne hure atd. proste TOM JE NASE ZLUTA SUPERSTAR !!! preju vsem na zkousce toma

[Návštěvník]

Nazdar nadzar! Ako ste to napchali do pamati??? Neviete niekto nejaku vhodnu hashovaciu funkciu, ktorou zahashujete string[50] do integeru? A ozaj kde je vyvesene u koho mam ustnu?

[Ferro_the_King]

...
nicmene, co se tyce rudly kryla, mam s nim zatim sice jen dobre zkusenosti (v zime byl slusny, dokonce i vykal (! ), ale to asi jen proto, ze v zime ten program proste bud fungoval, jak mel a nebo ne, kdezto tady je to hodne o okecavani/vyjadrovani/nalade zkousejicich atd.

jsem si 100% jista, ze mit dneska kryla, tak to nedam. holan byl ale skvely, ne mekky, ale bylo videt, ze ma zajem nechat si veci vysvetlit, ze uznava, kdyz nekdo neco ma trochu jinak, ale ne vyrazne hure atd. proste TOM JE NASE ZLUTA SUPERSTAR !!! preju vsem na zkousce toma

No, ja si je v zime vyzkousel oba, takze muzu srovnat:-) U Kryla sem chyt pomerne tezky zadani, celou dobu mi vykal a zas tak neprijemnej nebyl. Byl ta jeden kluk, co po 20 minutach vypad vej, ze de na WC a vratil se po 20 minutach (ze byl prej na cigu). Kryl ho brutalne serval, ale co sem vubec necekal, dal mu novy zadani a nechal ho delat znova (a cas mu prodlouzil!!) Ja sem sice vylit, ale co, holt sem mel jen pulku a jeste blbe
Co se tyce Toma - Dostal sem lehky zadani, celkem se choval docela prijemne, akorat tam s nekym neco resil snad ohledne mluveni pri testu nebo co. Pak se mi povedlo dokopat muj program do konce a zacalo to...
Nejdriv sem mel zada vstupni data a on kontroloval vysledky. Ty byly dobre. Potom sem mu ukazal zdrojak... Jeho prvni vetou bylo "Vy jste prase." Tak sem mu to zacal polopaticky vysvetlovat (totalne nechapal snad ani pul radky kodu ) Vzdycky me u neceho zastavil a vymyslel novy data, na kterejch to "Zarucene musi spadnout", jenze program se drzel, takze zase ucebnou znelo zlovestne "Vy jste prase" Nakonec ale povida "No, neda se nic delat. Vy jste proste prase. Ale zapocet mate..."
Takze Tom je jasna volba

[sandius]

No, ja mel Kryla na cvika a pamatuju si, ze vsem vykal, takze to musel bejt jenom nejakej ulet (spatna nalada / smutecni ohoz)...

[bilbo]

Ahojte,
tak dnes to bolo fakt huste. Mam popisane asi 3 strany, ani riadok kodu, ziadna zmienka o zlozitosti. Cely cas som sa snazil vymysliet a popisat algoritmus, ktory by tuto ulohu riesil.
Prisiel som toto (v skratke):
1. vyhadzat z toho grafu slepe cesty, vobec s nimi nepracovat
2. ohodnotit graf podla priepustnosti na hranach, najprv som to ohodnocoval smerom od D1 cez vsetkych naslednikov prvej krizovatky, atd (po hladinach) az po D2. Cize ak viedlo viac ciest do jednej krizovatky, priepustnosti sa pre danu krizovatku scitali.
Potom som to obratil (obratil vsetky hrany) a siel od D2 smerom na D1 a znizoval som priepustnosti na zaklade predchadzajucich hran, ktore viedli do krizovatiek. Takze ak bola napr. v povodnom grafe hrana s priepusnostou 50 a za nou hrana s priepusnotsou 1, tak cely usek (obe hrany) mal priepusnost 1. Samozrejme som si povodne priepusnosti pamatal.
3. vyberal som useky s rovnakou povodnou priepustnostou a minimalnymi nakladmi na rozsirenie. Zvysoval som ich priepusnost, kym dany usek nedosiahol priepusnosti predchadzajuceho useku na ceste z D1 a D2 a tym sa predlzil. Toto som opakoval, kym boli peniaze. Vzdy som vyberal najlacnejsi usek.

Teraz zistujem, ze som tam narobil kopu zbytocnych operacii.

Maly priklad som mal vlozit prvok do BVS, takze to by malo byt za jedna.

Ma to niekto podobne riesene alebo je to aspon ciastocne dobre?

Tak vela zdaru.

A este jeden link o tokoch v sietach:
http://www.cs.vsb.cz/hlineny/vyuka/DIM- ... redn11.pdf

[Eubie]

Tak to tykání je asi jen další indicií vedoucí k tomu, že mě vyhodit chtěl.