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

UVA. World Finals Warmup II. Разбор
Автор indy256, 14 лет назад, По-русски

Поделитесь пожалуйста исходником для задачи E. Array Transformer

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

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


→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Решение за .
Прошло аж за 11 секунд из 15.
http://pastebin.com/Cn4VxszL
Было настолько лень что-то умное писать, что даже после изменения элемента A[p] пересортировал его кусок не за линию, а тупо sort-ом.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    спасибо
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да, у нас на Java такое же решение прошло - тоже около 10 сек.
    Была сначала идея писать дерево отрезков из декартовых деревьев, но это не влезло бы по памяти, да и работало бы наверняка куда медленнее!
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Никто не в курсе что у них с проверяющей системой? А то мы за последний час 4 задачи отправили и они так и не дотестировались...  :(
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    и куда вообще контест делся :)
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Он в Past contests под номером 270.
      → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Контест нас покинул, но ссылка еще жива. Правда, очередь решений не изменилась :)
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится
        Чуть-чуть изменилась: вчера первым в очереди был субмит 763, сейчас - 805.
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Хм, действительно. А утром вроде все еще 763 был. Похоже, начали тестировать!
          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Они даже вроде как все дотестировали!
            Правда мне почему-то не верится, что во всех 4 посланных за последний час задачах у нас TL... Особенно, в J, где решение просто за O(1) на каждом тесте.
            → Ответить
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Может, из-за большого размера input'а TL? А вообще странно, да. По J всего 4 TL.
              У нас 2 задачи получили CE. С учётом "оффлайн"-тестирования, доставляет немало радости :)
              → Ответить
              • 14 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Вряд ли в этой задаче такой большой input или output, что его не считать.
                Мне больше верится в баги у них:)
                → Ответить
                • 14 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Максимум - 10000 тестов по 6 10-значных чисел в каждом. Порядка 660К получается, если юзать cin, то можно постараться ( :) ) TLE получить. Но, думаю, это не ваш случай.
                  → Ответить
                  • 14 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится
                    Послали в дорешивание.
                    Одна задача прошла, еще в одной WA вместо TL и в 2 все-таки TL.
                    Все-таки они не справились с дотестированием всего:)
                    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Расскажите, как B надо было решать?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    ...и были ли у этой задачи решения, не использующие google? ;)
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Сначала научимся решать для небольших по длине перестановок, это делается простой динамикой f[i][mask] , где mask - маска длины 2*k+1, говорящая, какие элементы из диапазона [i-k,i+k] уже поставлены. Пересчет более менее очевидный. А дальше стандартный прием - возведение матрицы в степень.
→ Ответить