Остается еще часов двенадцать до окончания квалификационного раунда Google Code Jam 2009.
Выполнив задачи A (Alien Language), B (Watersheds) и малую размерность задачи C (Welcome to Code Jam) я успешно сел в лужу на большой размерности задачи С. У меня там и не пахло отведенными 8 минутами на прогон данных. Сейчас ищу проблему, но поезд ушел -- на решение большой размерности дается только одна попытка.
Традиционный вывод: Good algorithms are better than supercomputers.
В итоге, пока я на почетном пенсионерском 1784-ом месте с 76-ю баллами (под именем begoon) из около 5700 всех участников.
Радует, что в топовой двадцатке три российских флага.
Хотя пишут, что для прохода в первый раунд надо только 33 балла, то есть фактически только одна полностью решенная задача, решения больших размерностей не проверяются в онлайне, и окончательная оценка будет только после окончания квалификации.
Забавно, через 3-4 часа после начала забега у них там что-то упало, и нельзя было скачать задания. Быстро все починили, но продлили время для участников на пару часов.
Кто-нибудь учавствует?
четверг, 3 сентября 2009 г.
Подписаться на:
Комментарии к сообщению (Atom)
Сообщения
Я участвую, сделал полностью A и C, B было лень ночью писать.
ОтветитьУдалитьНу время еще есть. ;-)
ОтветитьУдалитьЭтот комментарий был удален автором.
ОтветитьУдалитьЯ сделал вкратце так: обходим последовательно все ячейки слева направо сверху вниз. Для каждой ячейки строим маршрут, шагая либо вверх, либо вниз, либо влево, либо право пока есть куда шагать с сторону с меньшей высотой. Если шагать некуда (стена или вокруг высоты только больше), то значит найден новый слив. Берем для него очередную букву и помечаем все пройденные ячейки текущего маршрута этой буквой. Если в процессе построения маршрута наткнулсь на уже помеченную ранее буквой ячейку, то останавливаем построение и все пройденные ячейки помечаем буквой, на которую наткнулись. Обход маршрута нерекурсивный, так как путь всегда однозначный, и просто надо найти, где он кончается.
ОтветитьУдалитьЭтот комментарий был удален автором.
ОтветитьУдалить(Оффтоп)
ОтветитьУдалитьДавно Вас не слышно было. Читаю блог постоянно. Хорошо и интерестно пишите, спасибо!
Аналогично залажался на C-large, очень обидно что багу таки потом нашел :( Все остальное правильно (bearded). на рейтинг кстати очень сильно penalty time влияет. Но на c# больше не буду делать такие задачи.
ОтветитьУдалитьОчень интерестно посмотреть на решения девелоперов from top score. Потрясающе компактные решения. И чем дальше двигаешься вниз по score board тем более длинные и мутные решения.
ОтветитьУдалитьА еще интереснее посмотреть результаты за прошлый год, например, где приводятся решения самих авторов этих задач с объяснениями ;-).
ОтветитьУдалить