Milan Kryl

Kryl Blog - RSS

Zpověď finalistu Google Code Jam 2004

04. 11. 2004 - 17:53

Rozhovor s Tomášem Dzetkuličem studentem MFF UK, finalistou soutěže Google Code Jam 2004 a úspěšným řešitelem podobných soutěží a olympiád. Protože se účastnil finále přímo v GooglePlexu, přináší i několik zajímavých informací ze zákulisí firmy Google. Soutěž, která vás nutí rychle programovat algoritmy a umožňuje jejich souboje mezi sebou.

Shodou náhod jsem se dostal k seznamu finalistů letošního ročníku soutěže Google Code Jam 2004. Hned na pátém místě mi přišlo povědomé jméno Tomáš Dzetkulič. Pátrání v paměti pomohlo k lokalizaci jeho momentálního umístění, našel jsem jej na MFF UK. A dohledat kontakt už nebyl problém. Souhlasil s tím, že mi poskytne odpovědi na několik otázek a tady jsou.

Zúčastnil ses podobných soutěží jako je Google Code Jam?

Před tím jsem se zúčastnil IOI 2002 v Jižní Korei (International Olympiad in Informatics), CEOI 2002 (Central European Olympiad in Informatics) a Czech Technic University Open 2003. Byla to kvalifikace na soutěž ACM. Tam jsme se bohužel s naším týmem nedostali, protože na MFF UK je konkurence velká. :-)

Co se týká těchto soutěží, tak jsem se ještě zúčastnil fyzikálních olympiád IPhO 2001 v Turecku ( International Physics Olympiad ) a IPhO 2002 v Indonézii.

Kromě toho se účastním soutěží zveřejňovaných na stránce www.topcoder.com (tady jsem se také dozvěděl o Google Code Jam). Byla tam soutěž TCO 2004 (Top Coder Open). Google Code Jam se jí podobala. Průběh soutěže byl stejný, zadání vymýšleli stejní lidé a administrovali to zaměstnanci topcoder.com.

V které z podobných soutěži nebo olympiádě ses umístil nejlépe? Které si nejvíc ceníš?

Nejvíc si cením stříbrné medaile na IEI 2002. Veliký úspěch byla i bronzová na IPhO 2002 a bronzová na CEOI 2002.

Jak jsi přisel na Google Code Jam 2004 a co tě přesvědčilo, aby ses přihlásil do soutěže?

V květnu 2004 jsem objevil stránky www.topcoder.com, tam jsem se dozvěděl jak o TCO, tak i o GJC. Předešlé ročníky jsem nedělal. Nikdo mě nepřesvědčoval, abych se zúčastnil. Jsou soutěživý typ a podobné soutěže vyhledávám. Zkoušel jsem se probojovat do finále i na TCO, ale mezi prvních 100 se mi nepodařilo dostat.

Jak bys zhodnotil náročnost otázek, které byly zadávané před finálem? Můžeš uvést příklad otázky, která tě zaujala?

Úlohy nebývají velmi náročné, ale musí se řešit velmi rychle. Na jedno kolo soutěže je totiž čas 75 minut a jsou zadané 3 úlohy. Nejlepší řešitelé vyřeší nejlehčí úlohu asi za 3-5 minut, střední úlohu za 10 minut a těžkou řeší okolo 20 minut. Já často nestihnu nejtěžší úlohu vyřešit a některou z vyřešených mám špatně.

Úloha, která mě zaujala (copyright na toto zadání má TopCoder): Je zadáno N - počet znaků abecedy. N-1 vztahů mezi písmenky abecedy. Znaky v abecedě jsou číslované od 0 do N-1, vztahy jsou číslované od 0 do N-2 a i-tý vztah říká, zda se znak číslo i nachází v abecedě před znakem i+1 (True nebo False). Úkolem je vypsat počet abeced, které splňují zadání.

Príklad:
N = 5
vztahy: True, False, False, True

Pokud si znaky označíme a,b,c,d,e potom znak a je v abecedě před znakem b, znak c je před znakem b, znak d je před znakem c a znak e je za znakem d. Vyhovující abecedy jsou potom: deacb, daecb, daceb, dacbe, adecb, adceb, adcbe, decab, dceab, dcaeb, dcabe.

Program tedy vypíše 11.

Můžeš uvést nějakou úlohu, která ti připadla z celého soutěžení nejtěžší?

Nejtěžší úloha byla ve finále v Googleplexu (copyright opět přísluší firmě TopCoder):
Máš hrací plochu 6x6 a na ní figurky. V jednom tahu udělá jedna figurka následující tah: buď se posune na vedlejší políčko a nebo přeskočí figurku na vedlejším poličku (skočí až za ni a figurka přeskočená vypadává ze hry). Úkolem je zjistit na jaký nejmenší počet tahů to lze udělat, aby zůstala pouze jedna figurka. Poslední figurka se musí nacházet na zadané pozici.

Podle zveřejněných výsledků již vím, že se ti nepodařilo umístit na prvních třech místech. Jak jsi nakonec dopadl?

Nakonec jsem byl 44. Ze 7500 je to dobré umístění, ale udělal jsem blbou chybu. Kdybych ji tam neměl, mohl jsem se umístit někde v první polovině. Z Ameriky jsem si odnesl $250, compact flash, tašku na notebook a tričko.

Jak se ti líbilo v Googleplexu? Asi jsi jeden z mála Slováků, kteří se do Googleplexu vůbec dostali. Nebo víš o někom z ČR nebo SR, kdo se letos chtěl taky podívat do finále, ale nepovedlo se mu to?

Ve finále jsem byl jediný z ČR a SR. Nevím o nikom, kdo by tam byl minulý rok. Googleplex vypadá fakt super (nechci to moc rozebírat, protože jsem podepisoval papír o mlčenlivosti a nesmím nikomu říct, co jsem tam viděl :-) ) Je to nejpříjemnější pracovní prostředí, jaké jsem kdy viděl. Je tam plno věcí určených na to, aby se zaměstnanci mohli odreagovat během práce (masážní křesla, ... dokonce je tam masérka), knihovna, atd. atd. Je to udělané tak, aby zaměstnanci nemuseli opustit práci - všechno mají po ruce - dokonce je tam i prádelna. :-)

Jinak je v USA blbé to, že je tam všechno hrozně daleko. Když jsme šli do restaurace, tak chlapík tvrdil, že je to blízko a šli jsme tam půl hodiny. Všechno je od sebe strašně daleko. Proto mají všude 4 proudové dálnice a všude se jenom vozí. :-) V Googlu mají naopak všechno po ruce, vše si jednoduše zařídí a můžou pracovat.

Už jsem slyšel o výborném areálu, kde mají možnost zaměstnanci odpočívat, relaxovat. Místo sedaček tam mají balóny v barvách Google a všechno je tam výborné. Co nejvíc zaujalo tebe?

Ty balóny tam doopravdy jsou :-) Mě zaujaly klavíry a to, že tam má každý 2 pořádně velké LCDéčka. Když člověk potřebuje hardware, tak přijde za chlapíkem, který to má na starost a ten ti dá, co potřebuješ. A když si můžeš požádat druhé LCD, tak proč ne? :-)

Díky za rozhovor a přeju hodně dalších úspěchů v budoucnu.

 

Líbilo se? Přidejte do Linkuj.cz | del.icio.us | vybrali.sme.sk | Přidat RSS blogu do Google

Tip: Nevíte čím obdarovat nejbližší? Nechte je napsat Ježíškovi.