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

TopCoder SRM 517
Автор golyj_na_stole, 13 лет назад, По-русски
Всем привет!
Сегодня в смотреть здесь состоится TopCoder SRM 517. Регистрация откроется через 5 минут. Желаю всем поднять свой рейтинг, приобрести новые знания, да и просто неплохо провести время! Как говориться GL & HF!
И по традиции предлагаю после SRM вести его обсуждение здесь.

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

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Оперативно , регимся!
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Второй див, задача 250
Кое-что напоминает, да?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    По-моему она и не только там светилась :) 
    Классика.
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Никак не получалось вспомнить что за задача :)
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Отправил сейчас в дорешке на CF - Accepted.

    Хоть что-то радует)
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Попался на "легкую" 250 Div1, пришлось перепослать. Неплохие задачи.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А какой там подвох?
    Видел, что люди перепосылали, но не понял, почему.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Если делать не dfs-ом, то можно пропустить несколько случаев.
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Неверно упростил задачу - искал только разбиения N, если оба делителя не target, выводил No. Вовремя (хотя и после отправки) нашел тест 32, 4.
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Какова идея динамики для 500?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    То что не успел докодить:
    если делаем ход в позиции И, то числа слева и справа от него дальше не поменяются, писал:
    A[l,r,ll,rr] l,r - границы, ll,rr - числа на границах.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Казалось бы, такое решение имеет сложность O(N5), но там очень много недостижимых состояний. Да и даже без этого очень маленькая константа. Так что точно такое же решение у меня получило Passed System Test. Причем я решил обезопаситься и написать все на 64-битных переменных.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        В дорешке зашла без long long.
        Да, сложность O(N5), но константа маленькая. Жалко что забыл, что при следующем ходе еще на С нужно домножить...
        → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Можно убрать два последних параметра. Там для всех l, r возможна лишь одна пара ll, rr(см. комментарий ниже).
      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Это как?
        Пример:

        1 2 3 4 5 6

        Поменяли 4 и 5. Перешли в состояние (1,4,1,5) и что-то еще.

        Поменяли  5 и 6, потом 4 и 5. Перешли в состояние (1,4,1,6) и что-то еще.

        UPD: Написанное выше, считать 1-индексированным.

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

          Я переходил от заданной перестановки к (0, 1...n-1). И когда делил на две части (0..i-1)(i..n-1), от всех элементов правой отнимал i.
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Отнимание i от правой части никак не влияет на единственность. То что среди достижимых состояний ll и rr бывают разные при одинаковом l,r показывается тем же примером.А вот в то что только из одной пары достижимо что-то осмысленное я готов поверить.
            → Ответить
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Ну если при этом не делать ситуации когда ответа очевидно нет, то единственна. А его нет, если при делении получается что min(i..n-1)<i.
              → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Можете, пожалуйста, поподробнее объяснить: границы чего являются параметрами динамики, как осуществлять переход между состояниями?
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Границы в массиве, тоесть с какого по какой мы сортим, лл и рр это числа по краям, только они не будут соответствовать тем которые в массиве на данном интервале. Переход за О(Н), перебираем где сделаем следующий шаг, при том что все числа слева должны быть меньше чем все числа справа. При переходе аккуратно передаем границы в два интервала, что получились и умножаем на С из кол-во оставшихся ходов на интервале по кол-во ходов в правой или левой половине(в данном случае без разницы).
        → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Реализовал следующую идею за куб: каждый перемещаемый элемент налагает некие условия на порядок выполнения у кроликов. Предположим что pi > i, тогда получаем что кролик номер i - 1 должен выполнить свою операцию только после кролика i, кролик i раньше чем i + 1, кролик i + 1 раньше чем i + 2, ..., кролик j - 2 раньше чем j - 1, а j - 1 в свою очередь позже чем j. Пересекая все подобные ограничения получаем что либо решения нет, либо для каждых двух соседних кроликов мы знаем который должен действовать раньше. Далее идёт динамика по двум: параметрам: текущий кролик, какое время среди уже обработанных он занимает. Переходы тут очевидны: если следующий кролик должен быть раньше, пихаем его в разные места ранее денного, в противном случае позже.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ооооо, я не один такое укуренное решение придумал и написал!!! ^_^ Правда, слегка набажил и пришлось сделать ресабмит =(
      Решение с f[l, r, ll, rr], по-моему, куда тривиальнее, проще и более стандартное, чем это.
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я тоже такое написал, не придумал проще.
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кто-нибудь может мне объяснить как человек во втором дивизионе сдал задачу B(div 2) == A(div 1) с баллами 499,88???
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Он очень быстро кодит с другого аккаунта
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    К сожалению, на ТС есть читеры. Обычно вскоре после окончания контеста их дисквалят.
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Cheating only, я думаю. Имхо, это нереально закодить за полминуты ( полминуты уйдет на чтение).
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Вопрос для всех знающих: когда обновляеться рейтинг? (на следующий день?)
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Надо перезайти  в арену. Там уже обновился. На сайте через несколько часов.
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Спасибо, действительно обновился
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        На сайте тоже уже обновился, только не посортили всех по новому рейтингу пока ;)
        → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
за то что Petr обогнал tourist-a на CF, tourist сегодня перегнал его на SRM-e :)
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    И стал вторым по сайту.

    Теперь аж первая четвёрка на CF и на TC совпадает =) .
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кто-нибудь подскажет как решать div1 900?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Сдал в дорешивание такое решение(жалко на раунде не успел отладить):
    1. Если v - пустой, то ответ 0.
    2. Если в v все буквы равны, то ответ min(v.size(),v[0].size())
    3. Найдем строку в которой все символы одинаковые. Если такой нет, то транспонируем v - ответ очевидно не изменится. Если все еще нет, то ответ +inf. Иначе мы нашли строку.
    4. Есть два варианта. Либо покрасить эту строку последней, либо не красить ее вообще, но покрасить все столбцы в этот цвет.
    5. В первом случае мы свелись к меньшей задаче. Посчитаем ответ рекурсивно.
    6. Во втором случае ответ - количество строк в которых есть другие буквы + количество столбцов. Или же +inf. Значит осталось проверить ответ на существование в таком варианте.
    7. Если есть строка в которой 2 другие буквы - ответа нет.
    8. Иначе каждая буква создает условие типа то-то надо покрасить раньше того-то.
    9. Проверить совместимость этих условий = dfs.
    10. Время работы T(N + M) = T(N + M - 1) + O(N·M). По моему это O((NM)2).
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Предположим что мы закрашиваем все строки и столбцы. Тогда самый первый будет полностью закрашен - его можно убрать. Получается что какой-то столбец и строка отсутствует. Переберём его, предположим это строка. 
По отсутствующей строке можно определить цвет столбцов. Для каждой другой строки можно посмотреть где она отличается от цвета столбцов и либо определить её цвет, либо понять что у неё должно быть более одного цвета (то есть вариант с отсутствующей строкой не подходит), либо понять что её красить не надо.
Зная цвет каждой строки и каждого столбца можно по клетке пересечения определить что было раньше, если, конечно, цвета не совпали. Осталось проверить полученный граф отношений на циклы, например использовать алгоритм флойда.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
screencast от Petr-а
→ Ответить