Google Code Jam'09 - Qualification Round

[dastapov]

Кстати, до конца квалификационного раунда Google Code Jam'09 осталось 11 часов. Учитывая, что задачки там - часа на полтора в общей сложности, еще не поздно зарегистрироваться и поучаствовать. http://code.google.com/codejam

PS: если кто участвует: скажите, какой у вас там ник

Comments

[janatem.livejournal.com]

Хотел посмотреть квалификационные задачки, но лень стало регистрироваться... Может они уже где-то опубликованы?

[http://users.livejournal.com/_denplusplus_/]

DenRaskovalov

[antilamer.livejournal.com]

jkff.
О злодей, ты украл у третьего номера fprog.ru 1 час труда над моей статьей!

В задаче B две попытки запорол на том, что неправильно назвал стороны света :(

[renatm.livejournal.com]

rem

[maximkat.livejournal.com]

MaximKat

[http://users.livejournal.com/_adept_/]

Там же можно спектатором зайти

[dfyz.livejournal.com]

dfyz

[http://users.livejournal.com/_winnie/]

dobrokot.
Вспомнил студенчество, решил задачки =)

[savinovalex.livejournal.com]

SavinovAlex :)
Как думаете, уровень 2 задачи в Round 1 будет соответствовать уровню 3ей сейчас?

[dkorduban.livejournal.com]

dkorduban

а вообще сейчас неинтересно. скорборд говорит только о том, кто во сколько пришел с работы =)

вас что-то не могу найти

[http://users.livejournal.com/_adept_/]

Я там - "ADEpt".

Интересно станет, когда закончится раунд и оценят large datasets. Во-первых, будут нормальные результаты по ним, а во-вторых, можно будет качать и смотреть чужой код.

[http://users.livejournal.com/_adept_/]

А у меня опыт только предыдущего gcj, который был длинее (по кол-ву раундов), чем этот. Так что загадывать сложно.

[vsquash.livejournal.com]

Squash

Третья задачка имхо посложнее чем первые две. Да и с математикой у меня не очень :(

[ilih.livejournal.com]

ilih

у второй задачи долго не мог условие правильно понять
а у третьей поздно догадался кеширование прикрутить для большого набора

[http://users.livejournal.com/_winnie/]

А я на тикающем таймере в 4-ре минуты правил баг с картой размера 1x1 =)

[unbe.livejournal.com]

unbe

[darkk.livejournal.com]

Она не сложнее, просто там не помешает кэширование результатов, хотя потенциальные тормоза на большом dataset легко оценивались по параграфу текста.

// darkk

[common-racoon.livejournal.com]

Nickolas

[dkorduban.livejournal.com]

квалификация - что тут смотреть

[http://users.livejournal.com/_winnie/]

Там кстати можно не кеширование с рекурсией f(j, j), а табличку table[i][j] и тупой цикл по таблице.

[ilyabo.livejournal.com]

ibananti
спасибо за напоминание! чуть не проспал...

[al-zatv.livejournal.com]

al.zatv

поздно пришёл с работы, хотел спать, но таки вторую осилил. к счастью, хватило:) на то что выйду из первого раунда, почти не расчитываю - я 2,5 часа только условия читаю:)))

[u1ik (from livejournal.com)]

ADEpt, респект за то что на Хаскеле пишешь! Знаешь кого-нибудь еще из хаскелеров (кроме Reid)?

[http://users.livejournal.com/_adept_/]

А что не склеилось в третьей?

[http://users.livejournal.com/_adept_/]

Так Reid же в этом году вроде не участвует?

Там, когда будут результаты, достаточно легко будет прошариться по Top-N и найти, кто пришет на Haskell.

Можно еще зайти на haskell@conference.jabber.ru и спросить - вроде там был кто-то

[antilamer.livejournal.com]

Тупо забыл взять по модулю 10000 :-|

[http://users.livejournal.com/_winnie/]

Забавно, в списке френдов все пишут на разных языках :)

[renatm.livejournal.com]

http://www.go-hero.net/jam/09/lang/Haskell

[http://users.livejournal.com/_adept_/]

А в Haskell можно сделать табличку, элементы которой ссылаются на эту же табличку. Получится рекурсия на табличке без циклов :)

Потом берешь значение из нужной клеточки, и клубочек разматывается.

-- SOLVE A TEST CASE HERE:

[http://users.livejournal.com/_winnie/]

Без циклов - это вот это -

memo = M.fromList [ ((k,part),v) | k<-tails str, part <- tails pattern, let v = worker k part ]

?

Re: -- SOLVE A TEST CASE HERE:

[http://users.livejournal.com/_adept_/]

Угу. Если посмотреть, то:
1)memo состоит из ((k,part), worker k part)
2)worker вычисляет какое-то значение на базе (val x y)
3)val x y - это, фактически, lookup значения из memo

Круг замкнулся.

PS
List comprehensions в условиях lazy evaluation циклом нельзя считать ну никак. Это декларация, а не "действие N раз".

Re: -- SOLVE A TEST CASE HERE:

[http://users.livejournal.com/_winnie/]

Вау, круто, работает. Вот бы ещё научиться чувствовать ту грань, до который узел ещё завязывается, и за которой накажут бесконечной рекурсией.

import qualified Data.Map as M import Data.Maybe memo = M.fromList [(i, worker i) | i <- [0..20]] val i = fromJust $ M.lookup i memo worker 10 = 7 worker i = 1 + val ((i+1) `mod` 20)  main = print memo

Re: -- SOLVE A TEST CASE HERE:

[http://users.livejournal.com/_adept_/]

Ну, если где-то сам устроишь бесконечный цикл, или слишком рано форсируешь вычисления.

С бесконечным циклом все понятно - написал "worker = worker", и привет.


Пример раннего форсирования: если вместо Map взять Map.Strict или UArray/IOArray (не Array!) или любой другой контейне, который стразу редуцирует свои значения до weak head normal form.