Блог пользователя ivan.popelyshev

Topcoder SRM 515
Автор ivan.popelyshev, 13 лет назад, перевод, По-русски

Соревнование начнётся в 12:00 PM EDT (20:00 по Саратову)

Да прибудет с нами Сила!

P.S. Обсуждая его здесь вы поднимаете мне вклад


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

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ну что, станешь наконец таргетом? :) Удачи в сегодняшнем матче, добери эти несчастные 15 баллов рейтинга ;)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
GL & HF
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Условие 250 отстой
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Конечно, многие его сходу неправильно поняли (в том числе и я), но формально я не вижу, что в нём не так. Значит, это проблемы тех "многих", а не условия :) В 1000 например было более подло - нигде в тексте не упоминались особые ограничения на F и R, и для любителей сразу решать задачу, не читая до конца ограничения, была подстава. Так что в 250 не худшее условие контеста.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А как ее решать при ограничении на F и R?
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Может, я что-то не понимаю, но казалось бы: перебираем F, перебираем R, считаем за O(nm) для каждой клетки сумму расстояний от неё до этих F и R. Теперь надо найти для каждой Lки min(по всем клеткам (i,j) dF(i, j) + dR(i, j) + dL(i, j)). Это очевидно делается добавлением фиктивного стока S, проведением во все клетки рёбер веса dF(i, j) + dR(i, j) и запуском Дейкстры из S на этом графе (за O(nm * log(nm)).
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Можешь подробнее описать какой граф ?(а то в моем понимании тут nm|L| ребер)
          → Ответить
          • 13 лет назад, # ^ |
            ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Вершины - клетки поля и S, итого nm+1. Рёбра - рёбра поля (вес=1) и рёбра во все клетки из S (вес=сумма расстояний от F и R) - итого <5nm рёбер. Минимальное расстояние от S до какого-нибудь L - это минимум по всем клеткам (w(S, (i,j)) + dist((i, j), L) в начальном графе), т.е. ровно то, что нужно.
            Всё естественно. Или я чего-то не понимаю?
            → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      По-моему, условие (без примеров) формально вполне допускает альтернативное прочтение. Ну написано там "from a certain mark" - ну да, сделала отметку и от нее отсчитала, а что? А соответствующему примеру очень не хватало комментария. Я так до клара и гадала, что это такое в примере, и откуда оно взялось.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Так вообще, если по задаче есть клариф, то условие по определению так себе! :)
        → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Самое обидное, что я до этого сам догадался прямо перед кларом ((
        → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну до этого дано определение того, что такое "mark", так что формально всё корректно. Хотя оно дано косвенно ("The clock has a scale marked"), никак не выделено, но это вопросы оформления, на формальную корректность они не влияют. Когда у меня не прошёл семпл - я внимательно перечитал условие и все вопросы сами отпали.
        → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Условия на то и условия, чтобы передать суть задачи. У нас же не соревнованию по пониманию условий (а в этом контесте вышло примерно так).
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну по-моему, главное - чтобы в условии формально всё было правильно (тогда за конечное время в нём можно разобраться независимо от того, насколько способ мышления автора задачи совпадает со способом мышления участника).

        А передавать суть и прочие неформальные вещи - это уже приятный бонус. Тем более тут условие на 2 строчки, можно потрудиться и прочитать внимательно.
        → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решать medium ?
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Там оказывается каждый момент времени может быть максимум 1 покупатель. Это значит, что количество покупателей, которые могут прийти в магазин несколько раз не больше 12. Тогда идет динамика по параметрам маска покупателей, кто был, время, которое сейчас идет и сколько мечей осталось.

    Блин, как же я так не прочитал про это! Пояснения почему тосбили с толку и я решил что один и тот же покупатель не придет в одно и то же время 2 раза! :(

    upd: вот досада, и первая упала :) пока красный цвет
    → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    дп по состоянию (текущее время, осталось мечей, кто уже был).
    в лоб не лезет, но можно заметить, что про клиентов, посещающих нас ровно 1 раз, можно не запоминать, были они у нас или нет.
    не таких максимум 12.

    ну и не забыть пересчитать вероятности в условные (вероятность клиента придти в момент времени i, если раньше он еще не приходил)
    → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Кстати как альтернативное решение (правда оно хуже чем динамика которую предлагают) можно сдать следующее. Будем сразу из каждой вершины возвращать ответ в виде вектора мат. ожиданий где i-ым числом будет - какое мат. ожидание прибыли, если дальше мы продадим их ровно i штук. Тогда из очевидного решения через DFS мы можем модифицировать решение в следующее: из каждого уровня делать не более 2х рекурсивных вызовов т.е. всего у нас вызовов до 2^24, ну и ещё надо объединить результат за линейное время, т.е. выходит что-то порядка 24*2^24 операций, что можно при желании затолкать (в дорешке сдал немного попинав код, на контесте упало).
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Не челенджовый контест
→ Ответить