Блог пользователя Egor

Google CodeJam Round 2
Автор Egor, 14 лет назад, По-русски
Предлагаю здесь обсуждать второй раунд Google CodeJam 2010, который начнется 5 июня в 18:00 МСК
  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
У гугла странные отборочные.
Второй раунд пропускает 500 человек, то есть формально говоря для тех, кто реально борется за проходящие места, он заключается в необходимости не проспать его.
Третий раунд пропускает уже всего 25 человек.
То есть грубо говоря реально отборочный раунд получается всего один.
На топкодере это как-то покруче сделано, там можно вылететь на 3-ем, на 4-ом, на 5-ом, много интриги :о)

Кстати, делаю ставку, что решить все простые тесты хватит чтобы пройти в третий раунд.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Раунд GCJ имеет сильно больше оверхеда - надо потом запускать все эти решения (а оригиналы с брейнфаком/вайтспейсом/санскриптом всегда найдутся). Ну и топкодеровский раунд практически ровно 3/5 от GCJ. Хотя мне формат топкодера больше нравится, все-таки вот этот формат он больше катит для ipsc, где всякие приколы и т.п.
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    они просто 500 футболок напечатали и не знают куда их девать
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится
      Последний раз футболочки были очень клевыми и концептуальными.
      Интересно что будет в этот раз.

      П.С. Для тех, кто не получил в прошлом году футболку, картинка:
      http://code.google.com/codejam/contest/static/gcj-2009-shirt-back.jpg
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        да прикольно, особено понравилось то что когда  с низу вверх резко перекручиваешь картинку, то создается ощущение что сблизывается картинка.

        p/s круто если также будет и на футболке

        → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Не хватало только easy 
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    Беру свои слова назад про "не проспать" :о)
    Че-то я затупил, и не догадался, что даймонд можно вверх тоже расширять. В результате час на эту задачу безуспешно, и я не в топ500 :о(
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Не ты один :) Забавно, что после этого на СРМ-е занял 12-е место. Короче, по-моему при неудаче на личных соревнованиях можно очень сильно слить.
      → Ответить
14 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
Всем удачи кто пишет!
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Папки, ну и как C решается?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Ну и задачки..
    у меня 499 место :D
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Была у меня идея по С, не знаю правильно или нет. Но для нее нужно как то получить изначальный сет всех точек (как сделать это я не знаю). Вообщем если мы пройдемся дфс-ом по всем точкам, и найдем уголки (точки в которых на следующем шаге могут появится новые бактерии), а также найдем самые левые и самые правые клетки для каждой "компоненты связности", и соответственно покидаем их в  мепы (с соответствующим упорядочением). Ну и потом моделирование. Вроде как сложность линейная. Но не факт что идея не верная.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится
      моделирование катит только на small тесте
      на large - около 1012  операций

      а решать надо было так: все прямоугольники разобъем на группы соприкасающихся (прямоугольники соприкасаются если имеют общее ребро или точку (причем тут только один случай соприкосновения точкой подходит)). Каждая из таких групп в процессе проходится по прямоугольнику в правый нижний угол.

      Теперь для каждой группы найдем максимальный X, Y и x и y такие, что x+y - минимально. Тогда через X+Y-x-y ходов группа скукожится в правый нижний угол прямоугольника и исчезнет.

      Ответ - максимум этих величин по всем группам.
      → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Исходники решений доступны
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Из за расстройства даже забыл, что на gcj можно смотреть исходники, а также сразу появляются разборы.
      → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кто расскажет как решать А? Я решал проверяя все квадратные углы на диамонды ну и находил максимальный.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Надо было прямоугольные углы смотреть
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Я круглые углы смотрел, поэтому у меня не прошло.
    Овальные почти дописал, буквально пять минут не хватило. Думаю овальные бы прошли.
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    я просто повернул набок эту ромбообразную хрень - получился квадрат. он является элегантным, если все диагонали в таком квадрате удовлетворяют условию симметрии. потом тупо перебирал квадраты разных размеров, и перебирал позиции, куда можно поставить наш квадрат, чтобы получился элегантный квадрат в итоге. на большом тесте работало около минуты, но этого вполне было достаточно.
    → Ответить