*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

четверг, 3 сентября 2009 г.

Google Code Jam Qualification Round 2009

Остается еще часов двенадцать до окончания квалификационного раунда 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 часа после начала забега у них там что-то упало, и нельзя было скачать задания. Быстро все починили, но продлили время для участников на пару часов.

Кто-нибудь учавствует?

9 комментариев:

  1. Я участвую, сделал полностью A и C, B было лень ночью писать.

    ОтветитьУдалить
  2. Этот комментарий был удален автором.

    ОтветитьУдалить
  3. Я сделал вкратце так: обходим последовательно все ячейки слева направо сверху вниз. Для каждой ячейки строим маршрут, шагая либо вверх, либо вниз, либо влево, либо право пока есть куда шагать с сторону с меньшей высотой. Если шагать некуда (стена или вокруг высоты только больше), то значит найден новый слив. Берем для него очередную букву и помечаем все пройденные ячейки текущего маршрута этой буквой. Если в процессе построения маршрута наткнулсь на уже помеченную ранее буквой ячейку, то останавливаем построение и все пройденные ячейки помечаем буквой, на которую наткнулись. Обход маршрута нерекурсивный, так как путь всегда однозначный, и просто надо найти, где он кончается.

    ОтветитьУдалить
  4. Этот комментарий был удален автором.

    ОтветитьУдалить
  5. (Оффтоп)
    Давно Вас не слышно было. Читаю блог постоянно. Хорошо и интерестно пишите, спасибо!

    ОтветитьУдалить
  6. Аналогично залажался на C-large, очень обидно что багу таки потом нашел :( Все остальное правильно (bearded). на рейтинг кстати очень сильно penalty time влияет. Но на c# больше не буду делать такие задачи.

    ОтветитьУдалить
  7. Очень интерестно посмотреть на решения девелоперов from top score. Потрясающе компактные решения. И чем дальше двигаешься вниз по score board тем более длинные и мутные решения.

    ОтветитьУдалить
  8. А еще интереснее посмотреть результаты за прошлый год, например, где приводятся решения самих авторов этих задач с объяснениями ;-).

    ОтветитьУдалить