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

Автор ilyakor, 12 лет назад, По-русски

Предлагаю обсуждать здесь задачи. Кто что делал в C? Кто-нибудь решал D? Мы нашли статью, там даже код есть, но скопипастить его к сожалению никакими способами не получилось, только кучу компо-времени убили :)

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

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

Скопипастить? оО Честно говоря, я ожидал это от кого угодно, но не от Вас. Не могу сейчас найти ссылку, но раньше обсуждалось, что пользовать Интернетом и тем более копипастить код даже в Интернет-соревнованиях нельзя. Что с тех пор поменялось?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -20 Проголосовать: не нравится

    Правила opencup'а с тех пор поменялись, теперь prewritten code разрешён =)

    (ну а про фразу в посте — это разумеется полу-шутка: просто C у нас писать никому не хотелось, и поэтому от нечего делать страдали фигнёй с извлечением текста из pdf)

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

      Глупый вопрос, а нельзя было перепечатать? :)

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

        1) Так не интересно, 2) А ты посмотри на объём кода там ;)

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

      prewritten code разрешен, а пользование Интернетом-нет. И с вашей команды спрос гораздо больше должен быть за нарушение правил, вы ведь пишете не из сектора.

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

        Я бы даже сказал,

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

        Замечание про prewritten code относилось к вопросу про "копипастить". Пользование интернетом (по модулю коннекта к opencup.ru) конечно запрещено, мы кроме этого ещё используем skype/hangout/(изредка)rdesktop, когда пишем из >1 локации. Если используем что-то кроме этого, на ход контеста это не влияет (в обсуждаемом контексте — мы отлично понимали, что D сдавать не будем, спасибо "обнадёживающим" финальным стендингам первые 5 минут контеста; за неимением других дел в определённый моментэтим было просто интересно заняться). Можно конечно относиться ко всем правилам формально и старательно вырубать все источники инета включая мобильники, но зачем? Я не вижу катастрофы, если используется что угодно, включая интернет, при условии что это на контест не влияет.

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

          Не, если вы уже точно решили, что больше не будете посылать на контесте ни одного сабмита, то нормально, конечно. Извини за наезд :)

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

            Да не, мы ещё надеялись, что чего-нибудь сделаем. И пока Яша думал, как написать C пооптимальнее, я страдал фигнёй с распознаванием pdf'ки. Впрочем, я на тот момент уже точно понимал, что больше ничего на этом контесте не сделаю.

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

              Ну интересен вот какой момент — а если бы в пдф-ке на первой странице было написано "задача тривиально сводится к макс потоку" (не применительно к этой конкретной задаче, конечно) — тогда получается тебе нужно не обсуждать эту задачу больше с сокомандниками :) Опасное дело.

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

                Да, опасное. Но учитывая, что в финальных стендингах, которые зачем-то показывались на старте, по D было 0 сабмитов, вероятность такого к счастью исчезающе мала :)

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

Как решать F?

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

    Это стандартный алгоритм на пересечение двух ДКА.

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

      А где про него можно почитать не подскажете?

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

      а как нибудь ещё можно? а то нам стыдно, что таких стандартных вещей не знаем

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

        Да, конечно.

        Построим новый граф, где вершина в нём будет парой вершин из старых двух -- первая из первого графа, вторая из второго, если буквы совпадают. Итого N^2 вершин и M^2 рёбер. Поймем, что если в таком графе есть цикл, то ответ -1. А в графе без циклов самый длинный путь мы можем найти топ. сортом + простой динамикой. Итого O(N2 + M2)

        http://pastie.org/private/c8oy4xfclad8pd9cwhb7a

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

      Все-таки НКА...

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

        Да, согласен, конечно недетерминированных.

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

А кто нибудь сумел сдать K за N*log^2?

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

    Да. Для каждой вершины будем хранить её двоичный подъем. Операции с деревом устроены так, что все двоичные подъемы всех вершин без проблем быстро пересчитываются. Чтобы узнать ответ на запрос, делаем бинпоиск (по ответу). Нас интересует, верно ли, что при подъеме на высоту K всех вершин каждая вершина-результат получилась из некоторых вершин вдоль одного пути. Как это проверять? Отсортируем все вершины по такому параметру: (вершина, где оказались в результате подъема; исходная глубина). Условие, что все вершины-результаты имеют нужный вид — при фиксированном первом параметре, когда глубина увеличивается, очередная вершина — потомок предыдущей. Все это легко делается при помощи двоичного подъема, в итоге N*log^2, проблем с TL-ем не было.

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

Мы всё это сдали на дорешивании в ptz... В С проходят set если писать на своих аллокаторах и подвешивать меньшее к большим.. я писал на сжатых кординатах map масок из-за которого получается nlog^2n/32 и делал все операции за размер меньшего. А в D сначала находим целочисленный поток минимальной стоимости в таком графе, а потом делаем разворот циклов где стоимость ребра наша извратская... я искал циклы минимального среднего веса и разворачивал их.

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

    А можно подробнее про D? Вот нашёлся цикл. Насколько сильно его вычитать надо? Какой-то eps был? Или градиентный спуск?

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

      пускай p_i это стоимотсти а f_i это поток который течёт. Тогда если добавить по этому цикл поток велечины c прирости получится таким Sum[p_i{f_i + c}^2] — Sum[p_i{f_i}^2] = 2сSum[p_if_i] + c^2Sum[p_i] ну это квадратичная функция минимум у неё в точке -Sum[p_if_i]/Sum[p_i], но надо ещё взять минимум по пропускным способностям ребёр. Можно ставить eps что если ответ мало меняется (1e-4), то можно успокоиться. Больше eps не нужны если искать цикл минимальноного среднего веса за O(VE), но я искал бинпоиском и поэтому ещё был eps в бинпоиске 1e-2.

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

        Понятно... Там в output'е числа были с 10 знаками, что наводило на мысли о требуемой точности 10 - 10, так что надо было ещё догадаться, что на самом деле это не так :)

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

          Да, но ответ надо было выводить только с 3 знаками)

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

            Суммарный поток; а потоки по рёбрам — с 9 знаками. Ну да ладно, хорошая задача, в результате чтение статей и написание pipeline для OCR на bash — довольно неплохое времяпрепровождение.

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

          Можно было все домножить на 1010 и решать в лонг лонгах.

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

    А расскажите поподробнее про свой аллокатор. Что конкретно делаете и как это помогает?

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

В дорешивание сдали по C Nlog^2N/32 c нерекурсивным разбором. Реурсивный на контесте падал по стеку

Делаем так. Каждое множество — или множество или дополнение.

Тогда все операции выражаются либо как пересечение, либо как объединение, либо как разность множеств.

Все кроме объединения можно делать в тупую. Объединение надо делать объединяя меньший в больший. Это получился Nlog^2N.

Теперь надо поделить на 32. Для этого сжимаем координаты, и храним ненулевые маски в map

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

    В дорешивание Петрозаводска сдал решение за n*log(n) — то, что, видимо, и рассказывалось на разборе. Построим дерево разбора, в вершине хранится бинарная операция (/значение, если лист) + есть ли отрицание. У нас все бинарные операции коммутативны, поэтому детей можно переставлять. Размер поддерева = сумма размеров множеств (по числу элементов) по листьям в этом поддереве. Сразу договоримся, что размер правого поддерева меньше размера левого, а исходные числа сжаты (различных чисел всяко меньше 5*10^6, хотя, конечно, гораздо меньше). Теперь самое интересное. Для каждой вершины результат вычислений честно будем хранить в некотором массиве, своем для каждой вершины. Причем мы будем заботиться только о том, чтобы ответ располагался компактно — все числа шли бы подряд в любом порядке. Вычисления в дереве производим в таком порядке: сначала вычисляем для правого поддерева, потом для левого. Есть три вида операций — (l/!l)&r, l|r, l&!r. В первом случае в качестве ответа будет массив для правого поддерева, только из него кое-что нужно выкинуть (при выкидывании образуется дырка, её нужно заполнить последним элементом). Честно пройдем по нему и выкинем (как проверять, есть ли элемент в l? об этом позже). Во втором случае ответом будет ответ для l, к которому что-то из r приписали — честно проходимся по r, если в l нет, дописываем в конец. В третьем случае проходимся по r и честно из l удаляем. Как же проверять, есть ли элемент в l и если есть, то на какой позиции? Очень просто, заведем глобальный массив, в котором для каждого числа будем хранить, есть ли оно в последнем ответе, и если есть, то на какой позиции (легко понять, как это дело пересчитывается — используйте счетчики). Почему же это работает: да просто когда мы хотим воспользоваться этими глобальными массивами, то последняя операция была с левым ребенком, и они там насчитался правильно. Почему nlog(n)? Потому что всегда меньшее к большему. Код: http://pastebin.com/TDyCrf2E

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

    Рекурсивный разбор можно сдать, если при рекурсивном спуске внутрь скобок за один раз обработать все "лишние" скобки типа таких: ((( ... ))).

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

      А как это делать? Мы на контесте за две минуты не придумали.

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

        Для каждого символа сохраним rg[i]. Если i-й символ — это открывающаяся скобка, то rg[i] равен индексу соответствующей скобки, иначе -1.

        Пусть мы пишем рекурсивный разбор с глобальным указателем. Глобальный указатель называется idx. Пусть символ s[idx] — открывающаяся скобка. Сохраним текущее значение idx в переменной old_idx. Заведем два указателя clf = idx, crg = rg[idx] и будем делать clf++, crg--, пока оба указывают на скобки.

        Тогда сначала надо idx = clf, сделать рекурсивный вызов, а потом idx = rg[old_idx] + 1.

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

          Ясно. Я бы еще добавил, что надо еще проверять, что скобки друг другу соответствуют, иначе на тесте вида ((((())(()))) случится ужас.

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

как решать В? Весь контест пытался придумать и так и не смог ничего путного сделать...

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

    Понятно, что по всем стоящим рядом одинаковым буквам всё разбивается на независимые куски. Для каждого куска надо посчитать все возможные расстояния между парами разных букв. В голову сразу приходит 26 FFT, но к счастью всё гораздо проще :) Если немного подумать, то для куска длины l расстояния 1 ≤ i ≤ l не бывает только если i — какой-то из периодов куска. Считаем все периоды при помощи префикс-функции и решаем задачу.

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

А расскажите как решать А? (надеюсь там что-нибудь красивое)

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

    Нужно разбить все состояния на пары соседних и каждым ходом переходить в другое состояние в той же паре. Если общее количество состояний чётное, то играть за Алису, иначе за Боба (тогда нужно разбить на пары все состояния, кроме начального). n = 1 — особый случай.

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

      Не совсем так, в случае нечетного числа состояний все зависит от цвета старта в шахматной раскраске

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

      Есть ли хороший конструктивный алгоритм построения паросочетания для случая, когда мы выбираем играть за Боба?

      Я на контесте писал Куна с эвристиками, но интуиция подсказывает, что там вообще всё должно аналитически строиться.

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

        Мы делали так. Построим в этом графе гамильтонов путь. Это легко делается рукурсивно, спускаясь по размерности. После этого бьем на пары вдоль этого пути. Пропустить на нем клетку — не проблема.

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

        Мы делал так: давайте коробки, где изначально нечетное число шаров назовем плохими (у нас их четное число). Разобьем их на пары. Теперь будем искать пару данной коробке по следующему алгоритму:

        1. Если есть хорошая коробка, в которой лежит не столько шариков, сколько изначально, то сходим в первую такую коробку. Если там меньше, чем изначально, то из нечетного сходим в -, из четного — в +. Если больше — наоборот.

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

        3. Возьмем самую первую пару плохих коробок, в которой хотя бы одно количество отличается от изначального. Если нарисовать это дело на плоскости, у нас получится квадрат 3*3 без центра. Будем ходить по нему по часовой стрелке

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

      Не, я тебе потом уже не рассказал, но 1 — не особый случай в итоге

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

        Кстати да, разбиение на пары в случае n=1 тоже должно работать