Google Code Jam

[Mem]

Byla spuštěna registrace do soutěže v programování pořádané společností Google nazvané Code Jam. Registrace končí 17. července, takže je nejvyšší čas účast v soutěži zvážit.

Programovací prostředky si může každý zvolit podle svých preferencí. Základní 3 kola soutěže mají probíhat způsobem, kdy je online na stránkách zveřejněn problém a časový limit na řešení. Dále je k dispozici malý a velký testovací vstup, který si programátor stáhne a v daném limitu (4 nebo 8 minut) jej musí svým programem prohnat a výstup spolu se zdrojovým kódem (limit 100 kB) uploadnout zpět na Google, kde je výstup vyhodnocen (spolu s informací o tom, kolik času mu to trvalo, kolik měl pokusů atd.)

Pro následné regionální kolo získá 500 nejlepších soutěžících tričko a proplacení cestovních nákladů na pobočku Googlu, 100 nejlepších už získává peněžité odměny a proplacení cesty do místa finále v Kalifornii.
_________________

[Yossarian]

potkame se v Kalifornii

[adragon]

[if.then]

[Fila]

No je mile, ze je to zrejme konecne soutez v psani algoritmu a ne ve znalosti nejake technologie, nicmene tou dobou asi fakt nebudu mit na podobne veci myslenky .

[adragon]

tak jak se podarilo?,
ja uz zmaknul vsechno, i kdyz nevim jak to uspelo na tech velkych datech.
VIVA PYTHON !

[Mem]

Python saje Já ráno mezi průsery v práci naprogramoval mouchu, kde jsem zapomněl jen na menší drobnost, a pak už jsem se s k tomu nevracel, protože po zbytek dne jsem se drbal s tou záchranou vesmíru, kde super řešení v podobě rekurzivního stromu fungovalo do chvíle, kdy přišel větší testovací set Na víc nebyl čas, takže je to hop nebo trop, jeden příklad a otázka, jestli klapne large set nebo ne
_________________

[(CZ)genius]

no me chybi ta moucha.. napsal sem na ni nekolik naprosto genialnich programku ale zadnej ani trochu nefungoval ().. tedka mam teda napsanej jeden kterej vicemene funguje ale nevim kde tam bere odchylky v radu tisicin, takze nema cenu ani zkouset malou sadu..

[johnnash]

Taky sem resil prvni dve ulohy a celkem mi to hodilo 50 bodiku.
Prvni dva mi prisly celkem v pohode a resil jsem je spis intuitivnima metodama.
Treba na spravne reseni vesmiru stacil pouze jeden pruchod pozadavky.

Nekdo by se mohl podelit o to jak resil tu mouchu, ja mel navrhnuty algoritmus ve stylu Monte Carlo, ale pak jsem si vsimnul ze staci 25 bodu k postupu a dal to neresil.
I tak se mi, ale zdalo ze tak male chyby asi tezko dosahnu.

EDIT: kdyz si tak prohlizim v cem programovali lide z top 10 tak se docela divim tomu c++. Na takove "rychlosouteze" bych prece jenom volil neco jineho

[adragon]

prvni: prvne jsem si myslel, ze by mohl stacit hladovy algoritmus, ale pak jsem si to nakreslil a zjistil jsem, ze jde v podstate o hledani nejkratsi cesty v mape (a protoze tech enginu bylo daleko mene nez pozadavku, rozhodl jsem se pro prohledavani do sirky).

druhy: srovnal jsem si udalosti podle casu a vzdy reprezentoval od kdy je jaky vlak v jake stanici, pokud zadny vlak nebyl k dispozici, tak jsem si ho vytvoril. (v podstate hladovy algoritmus)

treti: zmensil jsem vsechny diry v palce o polomer musky a snazil se spocitat plochu palky a pravdepodobnost spocist jako pomer ucineho obsahu palky ku obsahu oblasti, kde se vyskytuje muska.

obsah palky jsem pocital jako obsah obruce, 2* obsah vodorovnych vypletu v kruhu palky minus obsah oblasti, kde se prekryvaji vyplety vodorovne a svisle.

ted uz bych asi pocital jen diry

dulezite je umet spocitat obdelnik, ktery ma horni stranu tvorenou kruznici. (v podstate integral z casti kruhu). zde jsem si pomohl wikipedii http://en.wikipedia.org/wiki/List_of_integrals_of_irrational_functions integral( sqrt ( a^2 - x^2 ), x1, x2)

v pripade lepsiho reseni se nestydte ho postnout nebo pokud by muj popis byl moc matouci se ptejte.

[johnnash]

1) Jednotlive pozadavky jsem ukladal Hashtable, jakmile byl pocet unikatnich pozadavku roven poctu enginu(nezbyva uz kam prepnout) tak je nutne prepnuti enginu. A takhle porad dokola az do konce pozadavku. V podstate O(n)

[adragon]

[posila]

tak co? soutezite jeste nekdo? dneska jsem uplne lamersky vypadl

[adragon]

[Yossarian]