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

Opencup.ru: ГП Южного Кавказа(V Кубок Векуа)
Автор map, 13 лет назад, По-русски
Стандартно: подскажите пожалуйста, как решать задачу С.
И N.
  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

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

В задаче C можно просто делать дп по подмножествам и пытаться объединить наименьшего по номеру человека с кем-то. Можно показать, что будет достижимо относительно небольшое число состояний (где-то 200К в худшем случае).
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Это понятно. Как это запихать в 32 Мб оперативки?
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Так а в чем проблема? Все замечательно влазит в 32Мб, если хранить только достижимые состояния.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А как хранить только достижимые состояния?
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Ну я заранее построил множество состояний, которые теоретически могли бы быть достижимы при таком дп:
          Храним мы все битовым масками, тогда легко понять, что если в битовой маске стоит 2k единиц, то младшие k разрядов обязательно должны быть единичными.
          → Ответить
        • 13 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          Введем массив структур в которой одно состояние - маска, а второе - значение. Понятно, что можно последовательно двигатся по номеру следующего человека для использования, не забывая сжимать массив состояний, при этом нам надо массив только на 2 человека (текущий и все следующие). Дальше я думаю и так понятно.
          → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Мы делали проще. Делаем динамику, но кешируем только последние 20 битов. Т.е. на первых 6-ти битах идёт перебор, а на остальных динамика
          → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Подскажите, пожалуйста, как решалась M.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Офигеть. Красные пишут на опенкапе див2.
С вроде бы надо решать так: выбрали в одну долю 5(!) вершин, а дальше понятно(во всяком случае так решили Saratov SU Retired)
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится
    Ни слова не понял из вашего комментария. Где красные пишут div2? Как выбрать в одну долю 5 вершин (всеми способами?) и что делать дальше?
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я могу пояснишь лишь то, что я красный, и я пишу див2.
      Школьникам впринципе более привычен див2, ибо он напоминает ВКОШП.
      → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +44 Проголосовать: не нравится
    Пишут и не краснеют ;)
    → Ответить
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
C - возьмем первых min(n, 21) и для них стандартную динамику. Потом для оставшихся не больше 5 - перебор с кем они сидят и смотрим ответ для соответствующей маски
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    я написал рекурсивное ДП, а ответ запоминал только для масок у которых первые 5 человек уже назначены, т.е. по сути то что вы сказали, но одной функцией.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Подскажите, где ошибка в ниже описанном решении задачи А (или хотя бы тест, на котором это не работает):
Ориентируем в исходном графе все ребра таким образом: из вершины с меньшим номером в вершину с большим. Гамильтонов цикл, описанный в условии, будет существовать в исходном графе тогда и только тогда, когда в построенном орграфе существует два непересекающихся по вершинам (за исключением конечной и начальной) пути из вершины 1 в вершину n суммарной длины n (в смысле числа ребер). Два описанных пути (при этом кратчайшей длины (в исходном смысле длины)) ищем так: строим сеть, в которой:
- исток - 1 вершина, сток - вершина n
- вершины исходного графа раздвоены (стандартно, для исключения пересечений по вершинам)
- стоимости протекания по дугам назначены следующим образом: пара (-1,с), где с - длина соответствующего ребра в исходном графе, между раздвоенными вершинами - пара (0,0)
В такой сети ищем поток величины 2  и минимальной стоимости. Если найденный поток меньше 2, или первая координата стоимости больше -n, говорим "NIE", иначе ответ - вторая координата стоимости.

Поток мощности два - дает два непересекающихся пути. То, что мы ищем поток минимальной стоимости должно давать:
- пути суммарной длины n (в смысле числа входящих в них дуг), если такие существуют (пары сравниваются начиная с первой координаты)
- среди всех таких, пути минимальной суммарной длины (в смысле исходной задачи)

// Вместо стоимостей-пар, пробовал стоимости-числа, получаемые так -M+w, где
M - число большее, чем сумма длин всех ребер
w - длина исходного ребра
Это должно работать так же, как стоимости-пары: приоритет отдается числу входящих в путь ребер, на втором месте - суммарная длина пути (как сумма длин ребер входящих в путь).
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    А тест из двух вершин пробовал? Аналогичным способом сдавали, но ТЛ.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      И правда, упустил частный случай, спасибо. Получил заслуженный TL#5)).
      → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Может кто-нибудь расказать решение?
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 4   Проголосовать: нравится +13 Проголосовать: не нравится

      Решение задачи A за O(N + M):
      Нам нужно найти две цепи, исходящие из 1 и заканчивающиеся в n, так, что номера вершин в них идут в возрастающем порядке, эти цепи покрывают все вершины и не пересекаются по своим внутренним вершинам. Ну, и требуется минимизировать суммарную стоимость цепей.

      Продублируем вершины 1 (добавим вершину 0) и n (добавим вершину n + 1).
      Рассмотрим следующую идею динамического программирования:
      Пусть Ai + 1  –  это наименьшая стоимость цепей, которые начинаются в 1 и заканчиваются в i  и i + 1. Ответ  –  это An + 1, база: A1 = 0. Осталось догадаться как пересчитывать динамику. Утверждается, что An + 1 = minv(Av + 1 + w(v, n + 1) + len(v + 1, n)), где минимум берется по всем смежным с (n + 1) вершинам v < n (w(i, j)  –  стоимость ребра ij), таким, что в графе существует цепь (v + 1)(v + 2)...(n - 1)n (существование и её длина len(v + 1, n) = len(0, n) - len(0, v + 1) подсчитываются заранее).
      → Ответить
13 лет назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

<не туда>

(Пожелание администрации: уберите уже, наконец, эту ссылку "Написать комментарий?" в самом низу страницы. Многие её случайно нажимают вместо "Ответить" в последней посте на странице)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
как решалась задача D?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1. Придумать самую простую динамику за 1000000*26^2
    2. Заметить, что памяти для нее достаточно 26^2
    3. Заметить, что переход теперь делается за 26
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Задача сводится к нахождению в массиве подмассива максимальной суммы (с небольшой модификацией). Решить ее нужно для каждой пары символов (которого больше всех и которого меньше всех), то есть, действительно, сложность LEN*26^2, однако понятно, что при обработке очередного символа меняются состояния не во всех 26*26 случаях, а только в 26, что и дает сложность 26*LEN
    Советую проверить на тестах:
    abbbbb
    aaaaab
    aabbaaaabbaa
    Ответ во всех случаях д.б. 4 =)
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Еще интересно было бы узнать, как решать задачу J. Я свел ее к нахождению минимального P такого, что N%P==0 && A[M]%P==0, и при этом A[i]%P!=0, для всех i<M. Тогда ответ - N/P. Но как теперь быстро найти P? Мое решение схватило TL 41...
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Тоже был TL 41. Сделал следующую оптимизацию: проверял на делимость не сами A[i], а только gcd(A[i], N), которых получается не так много. К тому же, я их отсортировал и бинпоиском определял, откуда начинать проверку для текущего P. После этих оптимизаций прошло.
    → Ответить
13 лет назад, # |
← Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

Интересно, а ГП Южного Кавказа (V Кубок Векуа) и Opencup когда-нибудь закончатся?
Вроде было объявлено, что после закрытия V Кубка Векуа результаты появятся. Но по расписанию уже больше суток прошло. Правда, перед этим товарищеский ужин, и я допускаю, что, с учетом грузинского гостеприимства, он очень затянулся =)
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Тоже с нетерпением жду результатов. У нас 8, надеемся на высокое место.
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      У нас =) 9.
      P.S. Правда G, по словам Гены, он пропихнул на чистой эвристике.

      P.P.S. Гена-то сейчас в Минске на сборах, это он мне по телефону рассказал.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        По G мы тоже пропихали шаманство. Такая задача была на одном из прошлых кубков. В тот раз мы ее сдали с +12, в этот раз - с +6.
        → Ответить
        • 13 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          А на сборах тогда разбор был, существует нормальное решение?
          Как я понимаю, это не к Вам вопрос, но кто-то ответ энает. Автора!
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится
            У нашей команды нормальное решение, так что оно существует :) Получилось сдать со второй попытки, в первой был закономерный ТЛ, из-за того, что сразу было лень делать оптимизации :)
            → Ответить
            • 13 лет назад, # ^ |
              ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

              А может раскажете?
              → Ответить
              • 13 лет назад, # ^ |
                ← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

                ________________________________________________

                Да, конечно. Но, возможно, я объясняю недостаточно хорошо, но думаю идея будет понятна.
                Основная идея решения - это сканирующая прямая, которая вращается вокруг точки. Будем для каждой точки поддерживать какую-то прямую, которая через нее проходит. При этом все такие прямые на начальном этапе параллельны (можно сделать вертикальными или горизонтальными). Также мы будем поддерживать порядок этих прямых (к примеру, справа налево). Это нам понадобится, чтобы искать ближайшую прямую. Как использовать эту информацию для решения? Событиями здесь будут те моменты, когда прямые для двух различных точек совпадают. Тогда в такой момент нам нужно просто найти ближайшую прямую к данной, и попробовать составить треугольник из точки на ближайшей прямой и двух точек, для которых совпадают прямые. Вот так проходим по всем событиям и ищем каждый раз треугольник минимальной площади. При этом следует заметить, что при каждом событии, порядок прямых не сильно меняется - соседние прямые могут поменяться местами.
                Вроде как где-то такое или похожее решение обсуждалось после Опенкапа годичной давности, но где, к сожалению, не помню...

                → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Чтобы новую тему не создавать и прямой эфир не засорять:

Будет ли 15-го мая Гран-При Беларуси (понятно, что внезачёта), или он планировался как запасной (на всякий случай) и в нём нет необходимости?
→ Ответить