Slovák Forišek postúpil do finále celosvetovej programátorskej súťaže Google

DSL.sk, 11.6.2012

Slovensko bude mať zastúpenie aj v tohtoročnom 25-člennom celosvetovom finále otvorenej programátorskej súťaže Google Code Jam, keď sa zo sobotňajšieho tretieho kola opäť do finále prebojoval Michal Forišek.

Forišek získal 53 bodov a obsadil desiate miesto. Ako jediný vyriešil výrazne najťažšiu štvrtú úlohu D na veľkom vstupe, celkovo sa o jej riešenie pokúsili len traja z päťsto súťažiacich.

Forišek zvolil riskantnú taktiku, keď okrem najľahšej prvej úlohy A stihol vyriešiť už len najťažšiu štvrtú. Tá bola ale bodovaná spolu až 43 bodmi z celkového maximálneho počtu bodov 100, 7 za malý vstup a až 36 za veľký vstup, a jej úspešné vyriešenie stačilo na bezpečný postup.

"Podarilo sa mi trochu "zaspať štart". V najľahšej úlohe A som prehliadol, že sa dá správne riešenie odhadnúť z príkladu vstupu a výstupu, takže keď som úlohu poriadne doriešil, strácal som asi 20 minút na súťažiacich, ktorí na tej ulohe zariskovali. Vlani v tomto kole súťaže vyriešenie najťažšej úlohy na postup stačilo a téma tohtoročnej úlohy D mi sedela, tak som sa rozhodol pre riskantnú taktiku - namiesto doháňania straty na stredne ťažkých úlohách skúsiť vyriešiť najťažšiu, ktorá bola za viac bodov," vysvetlil svoju taktiku pre DSL.sk Forišek.

"Je to samozrejme veľké riziko, lebo je veľká šanca, že ani za dve hodiny si človek s takou úlohou neporadí a potom skončí hlboko v poli porazených. A keď som po hodine strávenej nad tou úlohou ešte stále objavoval nové a nové zákernosti, tak som to rozhodnutie uz aj oľutoval :)," dodal Forišek.

Nakoniec ale úlohu D na veľkom vstupe Forišek správne ako jediný zo súťažiacich vyriešil v čase 1 hodina a 51 minút a bezpečne postúpil.

Úlohu D riešil Forišek ako problém teórie grafov, pričom zo vstupu vytvorený orientovaný graf reprezentujúci zadanie dopĺňal na graf prejditeľný jedným ťahom, nájdením optimálneho najlacnejšieho váhovaného párovania vrcholov s nerovnakým počtom vstupných a výstupných hrán. To implementoval pomocou algoritmu na nájdenie najlacnejšieho maximálneho toku v sieti.

Pre 31-ročného Forišeka, vyučujúceho na FMFI Univerzity Komenského, podpredsedu Slovenskej komisie Olympiády v informatike a predsedu vedeckej komisie Medzinárodnej olympiády v informatike, bude júlové finále jeho piatym finále Google Code Jam. Najlepší výsledok dosiahol minulý rok, kedy skončil piaty. Okrem toho má na konte 10. a 18. miesto.

Google súťaž organizuje najmä za účelom vyhľadávania a získavania programátorov. Forišekovi ponúkol prácu už viackrát, zatiaľ ponuku vždy odmietol.


Najnovšie články:



Diskusia:

La Viva Feminista Od: Neviem | Pridané: 11.6.2012 10:52 Asi tam nechodi koli praci v Googli ale koli adrenalinu ... Odpovedať Známka: 9.0 Hodnotiť:

Re: La Viva Feminista Od: 100 rocny dedo | Pridané: 11.6.2012 11:39 hej super ze mu nejde len o prachy, talent zrejme ma a kebyze potrebuje prachy tak staci zavolat do googlu... tesi ma ze este takyto ludia v dnesnej dobe existuju. Odpovedať Známka: 8.7 Hodnotiť:

Re: La Viva Feminista Od: Neviem | Pridané: 11.6.2012 11:45 Ak mu nejde o prachy a chce ucit na skole, tak je to mudry clovek ale skor by som tipoval, ze ma na vedlajsi uvazok pracu, ktora je zaujimavejsia a lepsie platena ako praca v Googli. Odpovedať Známka: -5.0 Hodnotiť:

Re: La Viva Feminista Od: rms_ | Pridané: 11.6.2012 11:59 > zaujimavejsia a lepsie platena ako praca v Googli Kamo, ty mas teda silne cuco Odpovedať Známka: 6.3 Hodnotiť:

Re: La Viva Feminista Od: Neviem | Pridané: 11.6.2012 12:23 Ty naivka. Pozri sa o dva clanky dozadu. Odpovedať Známka: -2.9 Hodnotiť:

Re: La Viva Feminista Od: vrmvrm | Pridané: 11.6.2012 16:41 bitch please.. Odpovedať Známka: 1.8 Hodnotiť:

Re: La Viva Feminista Od: lolo21 | Pridané: 11.6.2012 11:46 keby mu islo o prachy, uz davno neuci na matfyze :) Odpovedať Známka: 7.4 Hodnotiť:

Re: La Viva Feminista Od: janino 123 | Pridané: 11.6.2012 11:53 Raz som bol za ním konzultovať problém (na FEI to vedel jeden človek, čo to aj skúšal), mišo pozrel, vyjadril sa k tomu a nakoniec som podľa jeho návodu dohľadal plno učebných textov a skúšku som spravil úplne ľahko. Nie je dôležité vedieť, ale ale aj vedieť podať to iným. A to on zvláda, držím mu palce nech robí alebo učí hocikde. Odpovedať Známka: 9.4 Hodnotiť:

Re: La Viva Feminista Od: dumec | Pridané: 11.6.2012 18:35 veľa ľudí mi tvrdí, že nás zachránili zahraničné firmy, ale ja som presvedčený, že nie sme odkázaný sa iba zamestnávať v montážnych halách. Ak by sme sa dali ťažšou cestou, určite by sme boli už niekde inde. Minimálne by sme v takom počte nemuseli pracovať na zahraničné bruchá Odpovedať Známka: 10.0 Hodnotiť:

Re: La Viva Feminista Od: Squeak?!! | Pridané: 11.6.2012 20:39 Znovu raz: toto nie je zodpovednosť politikov, zahraničných firiem alebo marťankov, ale vždy iba tých konkrétnych ľudí. Nikdy nemusíš pracovať na zahraničné bruchá (okrem toho, mne je osobne absolútne jedno, či ma okráda Fico, maďarský pusztagazda, nemecký kryptofašista alebo hoci Maor), rozhodnutie je čisto na tebe. Odpovedať Známka: 8.2 Hodnotiť:

sutaz Od: srobik | Pridané: 11.6.2012 10:53 Vdaka za takychto ludi, ktori stale robia dobre meno nasej krajine.. Navyse je zrejme, ze Michalovi nejde o peniaze, ale chce podporovat dalsie mlade talenty, inak by bol davno z krajny von a zarabal by v Google, ktory by ho urcite zaplatil tak ako nikto iny.. Klobuk dolu Michal ! Odpovedať Známka: 9.3 Hodnotiť:

Re: sutaz Od: ehm | Pridané: 11.6.2012 11:44 takyto clovek zarobi aj na matfyz to sa neboj..aj tam su moznosti ;) ..mozno robi popri tom este aj na seba tak koniec koncom zarobi viac ako u google ..na SK je kopa firiem ako ESET, IBM a pod kde moze robit tiez na vedlajsi pomer ..a ostava na SK Odpovedať Známka: 2.3 Hodnotiť:

Re: sutaz Od: Element2 | Pridané: 11.6.2012 12:13 Bez urazky a na okraj, ale co to znamena, ze "dobre meno nasej krajine"? To uz koho zaujima nejaka krajina? Podstatne je, ci robi dobre meno sebe a ci je on sam pre tu krajinu - rozumej pre inych ludi tam - prospesny (co aj zjavne je, chvala mu). Kazda krajina do poslednej ma aj dobrych aj zlych ludi. Odpovedať Známka: 1.8 Hodnotiť:

Re: sutaz Od: absinth | Pridané: 11.6.2012 16:25 ked sa v sutaziach bude popri sutaziacich objavovat aj slovenska vlajocka hned to robi dobre meno krajine -> velmi hrubo povedane: firmy vidia ze tu mame sikovnych ludi a teda skor budu investovat/hladat kvalifikovanych ludi v takej krajine. inac super clanok ale hlavne vykon misof! Odpovedať Známka: 8.5 Hodnotiť:

Re: sutaz Od: dumec | Pridané: 11.6.2012 18:38 element, ty máš recht, za takú blbosť ešte aj pluská dostávaš Odpovedať Známka: -7.1 Hodnotiť:

Re: sutaz Od: Huh | Pridané: 11.6.2012 21:33 Nemam co dodat sam by som to nenapisal lepsie. Odpovedať Známka: -2.5 Hodnotiť:

Re: sutaz Od: Kapor z Vane | Pridané: 11.6.2012 13:00 ...tiez tak, mam rad ludi ktori este nezanevreli na tuto prehnitu krajicu pretkanu korupciou od hora dole... Odpovedať Známka: 5.0 Hodnotiť:

vlada podpori Od: niioniio | Pridané: 11.6.2012 15:00 je uspesny a robi dobre meno? zdanit ho sviniara... Odpovedať Známka: 8.2 Hodnotiť:

....................... Od: ľuboš | Pridané: 11.6.2012 11:14 Síce som príklad ani nepochopil, už len po prečítani zadania mi ostalo špatne na žalúdku..:), podmienený reflex zo strednej, ale "kto umí, ten umí, ja len čumím..." Gratulujem / Rada pre uja Čaploviča: treba zobrať školám peniaze, vidíte, že ich majú dosť, ked si chodia po svete súťaže vyhrávať.../ Odpovedať Známka: 6.0 Hodnotiť:

titulok Od reg.: leader | Pridané: 11.6.2012 11:44 tak gratulujem a posielam kvety Odpovedať Známka: 8.5 Hodnotiť:

5 znakov Od: aaaaaaaaaaaaaaa | Pridané: 11.6.2012 12:07 Hmm, tak som rozmyslal, ze za 1:51 by som snad aj vymyslel riesenie. A potom citat, ze to on za ten cas stihol aj implementovat... Odpovedať Známka: -2.8 Hodnotiť:

pekne :) Od reg.: pan Inkognito | Pridané: 11.6.2012 12:07 ...kvety su na ceste :) Vdaka uzasnemu ucitelovi na teorii grafov by som to uz mozno vedel vyriesit aj ja ^^ ...ale urcite nie nacas. Odpovedať Známka: 5.8 Hodnotiť:

A a D Od: xlx | Pridané: 11.6.2012 12:26 tiez som nechapal, preco submitol tuto ulohu tak neskoro. Prezrel som si niekolko ostatnych rieseni pre A a boli to niekedy riadne elaboraty, vzhladom k tomu, ze stacilo "len" zotriedit podla l1*p2-l2*p1 ...Z ulohy A priamo vyplyva, ze vlastne bolo treba zacat tou najviac obodovanou D, co sa misofovi skoro nechtiac podarilo :-) Odpovedať Známka: -7.1 Hodnotiť:

Re: A a D Od: emeric | Pridané: 12.6.2012 8:20 tiez som nechapal, preco na tej sutazy nie si aj ty ;-) Odpovedať Známka: 10.0 Hodnotiť:

pcpcpcpc Od: okk | Pridané: 11.6.2012 12:31 kolko riadkov kodu riesenie asi zabere a v akom jazyku? Odpovedať Známka: 3.3 Hodnotiť:

Re: pcpcpcpc Od reg.: Redakcia DSL.sk | Pridané: 11.6.2012 12:36 Riešenia jednotlivých súťažiacich sa dajú sťahovať z http://goo.gl/7xlmb Odpovedať Známka: 3.3 Hodnotiť:

Re: pcpcpcpc Od: Lamicka | Pridané: 11.6.2012 14:51 Preco nepouzivate "oficialny" skracovac dsl.sk? :O dopice.sk? Odpovedať Známka: 7.1 Hodnotiť:

Re: pcpcpcpc Od: TomBA | Pridané: 11.6.2012 17:23 Lebo je to vulgárne? Odpovedať Známka: -7.3 Hodnotiť:

Re: pcpcpcpc Od: dfsgsdf | Pridané: 11.6.2012 21:46 zaujimave vsetci si vybrali C++ aj ten misof len rusi si vyberaju javu a jeden rus si vybral pascal. Odpovedať Známka: 7.5 Hodnotiť:

..... Od: xvzf | Pridané: 11.6.2012 12:37 Gratulujem! Odpovedať Známka: 7.8 Hodnotiť:

The Big Bang Theory Od reg.: saruman | Pridané: 11.6.2012 12:40 Tú najťažšiu úlohu vymyslel určite Dr. Sheldon Cooper. Odpovedať Známka: -2.6 Hodnotiť:

4553453454534543 Od: 534lj34klh345jk34h5jkh | Pridané: 11.6.2012 12:45 clovek s talentom a chutou svoj talent zdielat pre toho co pindal ze lepsia praca ako pre google nemoze byt moze si treba uvedomit co mu google ponukol ono on je matematik a jemu staci pretavit vedomosti pre stavkove spolocnosti pripadne inak zneuzivat teoriu hier a nemusi sa prestahovat len sediet doma na stolicke nie kazdy ma moznost a chut ist do USA/centra googlu mozno ma plany a rodinu tu na SK a to je casto silnejsia motivacia ako peniaze a "firemne google tricko" 18,10,5, teraz by to mohlo byt 3 a buduci rok prve miesto :P clovek ktory sa pernamentne umiestnuje taktom rebricku ma vyssiu cenu ako niekto kto tam zaziari 1x Odpovedať Známka: 5.8 Hodnotiť:

titulok je na prd Od: zrukynoha | Pridané: 11.6.2012 12:56 ten smajlik v clanku nema chybu :) Odpovedať Známka: 6.4 Hodnotiť:

gratulacia Od: pica | Pridané: 11.6.2012 19:15 michalovi obrovska gratulacia. je fajn vediet, ze taki ludia este neodisli do zahranicia. za kolektiv Billa Bajkalska zela vsetko najlepsie pica. Odpovedať Známka: 7.8 Hodnotiť:

ftjhwerjkhrwejkth Od: KalafunaLand | Pridané: 11.6.2012 21:58 a My pridavame gondolenciu pre Bellu z Bajkalskej bo mate cervene ceny 22 centov Horalka ale nikde ani zmienka ze od 3 kusov! Odpovedať Známka: 7.6 Hodnotiť:

gz -titulok prispevku musi mat aspon 5 zasranych znakov Od: Kopac | Pridané: 11.6.2012 23:29 zobral ako jeden so 4 najtahsiu ulohu a ako jediny ju vyriesil? Pre mna je uz teraz vitaz !!!! Odpovedať Známka: 7.8 Hodnotiť:

Gratulujem, Od: konciaci_matfyzak | Pridané: 12.6.2012 18:44 a dakujem MisoFovi, ze na tom Mafyze zostava a uci tak skvele, ako to len on vie. Seriozne, kazdemu kto rozmysla nad informatickymi VS: MisoF a samozrejme aj ini ucitelia (napr. Kralovic, Stanek, Olejar, Vinar, ...) su hlavnym tahakom Matfyzu, cas straveny s nimi vas skutocne pohne dopredu. Odpovedať Známka: 10.0 Hodnotiť:

Re: Gratulujem, Od reg.: tomexx | Pridané: 15.6.2012 13:04 No u nas vo firme, ked pride na pohovor matfyzak tak ma len velmi malu sancu prejst dalsim kolom, pretoze nech uz maju matfyzaci akekolvek dobre znalosti, vacsinou su to asociali, ktory by vobec nezapadli do pracovneho kolektivu. Na soft-skills sa u nas nezabuda a tie su nemenej dolezite ako IT znalosti... Odpovedať Známka: -5.0 Hodnotiť:

Re: Gratulujem, Od: awgawgaw | Pridané: 1.7.2012 16:31 soft skills su potrebne, ale kebyze ich niekto chce tak sa ich nauci (hocikto kto ich chce - pozrime si pocet vsetkych marketerov, studentov socialnj prace, masmedialnych a pod.) TOP znalosti z matfyzu sa daju porovnat s MIT a rocne ich nadobudne tak 5 ludi z rocnika Hadaj co. 3 z nich sa odstahuju do SV, jeden ide na OX/CAM/ETHZ a jeden sa zlutuje a zostane na slovensku Odpovedať Hodnotiť:

Re: Gratulujem, Od: menomusibytaspon5*matfyzak | Pridané: 28.10.2013 14:54 tvoj prispovek napoveda, ze budes z jednym ztych strasne talentovanych matfyzakov keby sa matfyzaci sami nedosadzovali cez kamaratov v pro forma pohovoroch nikdo okrem VS a skol na ucenie matematiky by Vas nezamestnal nato je matfyz studium akurat dobre Odpovedať Hodnotiť:

gratulujem Od: konciaci_matfyzak 2 ;) | Pridané: 12.6.2012 23:20 Gratulujem misofovi k uspechu a zelam vela zdaru aj vo finale. Inak plne suhlasim s kolegom - je to vyborny pedagog a spolu s dalsimi tvori hlavnu devizu informatickej sekcie matfyzu (nech uz budova vyzera akokolvek). Odpovedať Známka: 8.0 Hodnotiť:

Re: gratulujem Od: Cuda | Pridané: 13.6.2012 20:31 Kockatá hlava? No s tým musí byť zábava... :-( Odpovedať Známka: -8.2 Hodnotiť:

Re: gratulujem Od: sitard | Pridané: 15.6.2012 8:43 retard? Odpovedať Známka: 10.0 Hodnotiť:

5 znakov Od: Matoo01 | Pridané: 13.6.2012 19:38 Roses are red, violets are blue, if Asians can't solve it, it's impossibru! Odpovedať Známka: 7.5 Hodnotiť:

Pridať komentár