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

TopCoder SRM 573.
Автор PavelKunyavskiy, 11 лет назад, По-русски

Посты последнее время появляются совсем незадолго до раунда, что при утреннем почти бесполезно.

TopCoder SRM 573 будет сегодня15 марта в 5:00 MSK (в других временных зонах).

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

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

Правильное ли решение Medium'а:

Динамика (вершина, высота предыдущей вершины в пути) -> ответ. Внутри перебор текущей высоты и куда пойти. В чем может быть проблемА, если правильное?

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

    Бывают проблемы в переходе. Грубо говоря надо не сделать так "опустить вершину, пойти в нее, поднять вершину, пойти из нее". Правда все три попытка прочеленджить по этому были неудачными. У двух правильное решение, которое я не понял, а у одного написан какой-то треш, который случайно отработал на слишком симметричном тесте.

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

    А циклов не будет в динамике? Тут Дейкстру лучше по тем же параметрам.

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

      Вроде циклы не должны мешать, если при входе помечать ответ как INF

      UPD: вроде бы понял, когда примерно мешают

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

        Алгоритм Дейкстры как раз даёт правильный порядок вычисления для этой динамики.

        → Ответить