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

Google Code Jam 2013, Round 3
Автор Rubanenko, 11 лет назад, По-английски

In less than half an hour the third Round 3 will begin. Top 25 participants will go to London to compete in Wordl Final. I wish everybody good luck and interesting problems.

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

ИТАК... В чём заключается стандартная ошибка в А-small?
2 часа, пять попыток, так и не понял.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    иногда имеет смысл делать заведомо проигрышные ставки

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      эту ошибку я исправил после первой попытки. Ещё варианты?

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        У меня даже после учета таких ходов была ошибка в том, что я предполагал, что всегда выгодно делать ставку до суммы B. Вообще, это очевидная тупость, но как-то мозг не очень-то слушался меня, когда я это написал.

        → Ответить
  • »
    »
    11 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

    Поднимать на единичку ставки, в которых наша доля мала, чтобы их не выбрали?

    EDIT: я сдал оба теста, дихом нашел максимальный минимум, и для каждого минимума из отрезка (максимальный минимум -100, максимальный минимум) запускал жадный, который по одному убирал(путем добавления единички) самую невыгодную ставку, которая может быть выбрана рулеткой, и пересчитывал ответ.

    Наверняка какие-нибудь части этого решения лишние, но зато оно работает)

    → Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    На всякий случай, я решал так: рассматривается ситуация, которая получится после нашей ставки. Перебирается сама минимальная ставка и количество чисел, на которые сделана именно такая ставка. Потом считается ответ, с учётом того, что выгодно, чтобы минимальная ставка оказалась на изначально минимальных значениях, а остальные ставки должны быть хотя бы на 1 больше.

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

      Думаю,дело в том, что не всегда хватает денег для того, чтобы ВСЕ остальные поднять на 1ку, это не значит, что не надо подымать некоторые. Я делал то же самое, только еще перебирал количество чуваков, которых мы при необходимости повышаем до мин. ставки + 1, и это зашло.

      Биг, кстати делается почти так же — только вместо перебора всех минставок перебирается минимально возможная и такие, при которых общая сумма приближается к Б (находится БП).

      Почему вообще хоть что-то из этого работает — не очень понимаю)

      → Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Я хз... Я пробовал даже тупо перебирать минимум,который будет, потом для него считать. Но это все равно давало ВА... За другие задачи так толком и не сел из-за нее:(

    → Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я перебирал число ставок, которые победят.

    Пусть это число К. При фиксированном К будем бинарить сумму, которая будет поставлена (не нами, а вообще) на номер-победитель. Т.е. понятно, что в наших интересах это число сделать максимальным — чем выше это число при фиксированном К, тем больше наша суммарная ставка на номера, которые победят, и больше наш профит.

    При фиксированном К и фиксированной сумме Х для этого К проверка внутри бинпоиска вроде простая: 1) все числа, которые меньше Х — за свой счет прокачиваем до Х (так как у победителя должно быть Х). 2) среди тех чисел, у которых Х, убираем по одному, прибавляя к нему единицу, до тех пор, пока их больше К (так как их должно быть ровно К). Если чисел с Х осталось меньше К — надо бинарить вправо (вверх), если суммарная стоимость наших действий больше нашего бюджета — бинарить влево (вниз).

    При таком бинпоиске можно найти пустой отрезок — если нашего бюджета не хватит, чтобы сделать ровно К победителей. Если хватит, то найденное бинпоиском число будет оптимальным для заданного К.

    → Ответить
»
11 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Сдал D в дорешивании. Идея такая:

Считаем динамику. Будем искать для каждого промежутка на окружности вероятность того, рандомные k людей (где k — количество точек на промежутке), появившиеся на этом промежутке, в нём и осядут (т.е. не будут ждать дальше). Также будем хранить для каждого такого промежутка матожидание денег, которые заплатят эти k человек.

Пересчёт динамики — перебором позиции, на которой остановится последний человек, зашедший на промежуток (при этом не сложно заметить, что промежуток разделится на две части).

Особое развлечение задачи — в том, что всё надо считать в логарифмической шкале.

→ Ответить
»
11 лет назад, # |
← Rev. 3   Проголосовать: нравится +29 Проголосовать: не нравится

congratulations to tourist for winning this round and everyone else who advanced to the finals!!!!!!!!

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Congratulations to everyone who enjoy this contest.

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится +83 Проголосовать: не нравится

no chinese at world final !!!

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +34 Проголосовать: не нравится

    I guess one of the reason is that the tasks are very creative. (And another reason is: ACRush can't participates in GCJ this year.)

    I love this kind of tasks though I'm not clever enough to solve them. :)

    → Ответить