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

Автор Zlobober, 2 года назад, По-русски,

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

Задача G, имхо, тоже очень сомнительное развлечение. Это, конечно, очень забавно, но будет обидно, если кто-то не отберется по спонсорскому зачету в Петрозаводск из-за того, что не справился с угадайкой.

Как решать задачу H?

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

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

И еще, кто-нибудь кроме нас писал специально на JavaScript, чтобы решить задачу K?

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

    Мы на питоне сдали. Боялись, что считать не успеем, но в итоге сразу зашло.

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

Аааа горит! Как решать задачу C?

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

    Динамика: i — количество типов, dp[1] = { K }. Хотя динамика — громко сказано.

    Для i = 2..N: M — сколько нужно голосов, чтобы выжить самому старшему; cnt — количество умерших на предыдущем слое динамики. Если M - cnt > K (подкупать умерших не надо, так как они и так будут на нашей стороне, ибо иначе умрут), то копируем предыдущий слой и дописываем -1 самому старшему. Иначе самый старший может выжить, если подкупит тех, у кого на предыдущем слое динамики не было денег вообще. То есть подкупать тех, кто до этого умирал — не надо, они и так будут на стороне самого старшего, так как их цель — выжить (1 приоритет); подкупать тех, у кого ничего не было — можно, их цель заработать побольше (2 приоритет); подкупать тех у кого и так что-то было — нет смысла, потому что они всё равно захотят убить самого старшего (3 приоритет) или он может заплатить им больше, но тогда нарушит 2 приоритет для себя; ну и нужно подкупать самых старших (4 приоритет).

    Подкупать нужно единичкой, чтобы у старшего осталось как можно больше.

    Надеюсь понятно написал.

    Ответы на пару тестов

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

      можно не рассматривать случаи с умершими, а просто считать что они получили -1. Тогда мы выбираем нужное количество с минимальными значениями и даем им на 1 больше.

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

        Технически — тоже самое, но вроде if написать проще, чем задумываться о таких вещах)

        P.S. Ну хоть один человек ответил, а то я уже стал думать, что может все вокруг считают, что я какую-то другую задачу объясняю.

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

А мы весь контест решали С, потому что считали, что у грабителей с меньшим номером должно быть больше денег (как диаграмма юнга). На клар нам ответили "No comments".

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

H нам дали в четверг на тренировку. Ту же задачу, но с куда более жесткими ограничениями. Простого куска хватило для этой задачи. Баяны -- это классно! :)

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

Problem H: https://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorithm

Well, is it allowed to use such tasks in contests? This task is just a copy of Schreier and Sims' idea and there is zero originality. I hope authors to come up with original tasks.

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

    And problem I — I believe it's not a good idea to try to separate MCMF and Hungarian. Both are O(n^3).

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

      MCMF worked 0.336 seconds in my case, not even close to TL (and I believe it can be still optimized a lot, by changing long long to int etc.).

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

        Interesting fact: most of the people who had issues with MCMF fitting into the time limit never have issues with long long.

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

      Were they actually trying to separate them though? I passed with Dijkstra on Set in my Min Cost Flow. So it was even O(N^3logN).

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

      MCMF with Ford-Bellman works 0.8

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

Написал много гавнокода на К. Какие проблемы могут быть?

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

    Ключ может быть пустой строкой. У меня был WA2 из-за этого.

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

Вы еще не в параллель с онасайтом решали. Условие F и J понять было совсем нельзя, и в I были кривые тесты. (и в A еще, но там нас не сильно задело). Ну и H на 13 минуте заслать готовое решение, которое я в четверг объяснял -XraY- это было смешно.

Кстати, говорят H еще была на контесте Unpredictable в птз летом 2011.

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

Лучше бы вы четверть провели на этом

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

    Лучше для кого?

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

    Так это же несвязанные вопросы :) Орги могли сделать на этом чф, могли опенкап, могли ничего. Могли и то, и то.

    Наши кволы бы, я думаю, стали бы опенкапом, если б в те же выходные не было бы отбора на ГП Сибири.

    Ну на самом деле конечно чф не могли на этих задачах, т.к. готовили участники чф. Могли или опенкап или не опенкап. Авторы захотели опенкап, Олег не отказался. Где сбой в системе? :) Олегу нужно требовать данные заранее? Это вроде нереализуемо.

    Я не совсем понимаю, как такое универсально могли решить.

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

      Сбой в системе — время готовности условий. За сутки до онсайт-контеста времени для того, чтобы найти какой-то компромисс с авторами и привести условия в порядок, хватит.

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

      Кволы опенкапом? Совсем там поехал? Зачем давать на опенкап контест из трех задач?

      В упор не понимаю, почему ты так гордишься этими кволами. С задачей "дать порешать что-то неACMщикам" он справился. Давать на опенка задачи для неACMщиков — это странная тема.

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

        Ну в OpenCup есть не только спон... первый дивизион. Так что идея такая была, если бы не свойство отбора на Всесибирскую Олимпиаду, заключающееся в том, что его пишут все (редкий случай, когда Div1 и Div2 полностью совпадали).

        Проблемсет с квалификационных раундов — отличный Div2 problemset, на самом деле. C задачей "сделать хороший Div2" в OpenCup вообще мало кто справляется. У СПбГУ вот с методикой "упрощённых версий Div1" только 2-3 последних ГП стало хорошо получаться. Так что предмет для гордости, как мне кажется, есть.

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

        В Саратове, насколько я знаю, каждый год на основе школьной олимпиады организуют не плохой контест. Просто меняют ограничения в задачах, возможно одну-две заменяют. То же самое могло получиться на основе квалов ваших

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

          Вот стремление вылезти с любым проблемсетом в первый дивизион мне кажется совершенно непонятным. В Division 2 тоже участвует много команд, и к задачам этого дивизиона свои требования, близкие к тем, которые были предъявлены к задачам квалификационного раунда. Хотя в среднем Div2 получается на уровне среднестатистического четвертьфинала (исключив, пожалуй, московский — обычно проблемсет вполне себе на Regional), что всё же для команд из нижней половины таблицы сложновато.

          В том виде, в котором квалификационный раунд есть сейчас, он удовлетворяет этим требованиям практически идеально — только перевести условия на английский и можно было бы давать. А предлагается из идеально соотвтетствующего второму дивизиону проблемсета сделать "какой-то" для первого.

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

Кто-нибудь может указать, откуда в Н следует, что даны перестановки?

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

    "Если в какой-то момент часть материи перетекает из одного мира в другой, то возникающая в первом мире пустота тут же заполняется материей из некоторого другого уголка вселенной. И наоборот, если в какой-то из миров переносится материя, этот мир тут же отдаёт часть своей материи другому миру."

    То есть в каждый мир приходит хотя бы одно ребро. Раз исходит ровно одно, приходит хотя бы одно, то перестановка.

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

      Здесь не указано, что что-то приходит. Может, оно через вход назад лезет?

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

        Кстати, а если это не перестановки, задача решаема еще?

»
2 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
  • " If the number of points N ≥ 12, this set is divided using straight lines.
  • If the number of points N ≥ 12, then this set is divided into the set of 3 and N−3 points. "

Non-deterministic?

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

А как решать "D"? А то 10 мин крутить машину, чтоб потом пихнуть 1 мб ответов — не решение.

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

    Напишем квадратичную динамику. Потом оптимизируем её до линии префиксными суммами.

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

What was case #3 of J and #8 of I?

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

Расскажете как решать А из див2?

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

    Так же, как А из div1.

    P.S. Вот это шутканул — так шутканул.

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

Скажите, как решать задачу Е (о триангуляции Одина) из див2. А лучше дайте глянуть на код. Что ж там за 3 тест? Спасибо.

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

    Переберём треугольники, построим описанную окружность. Проверим попадание вершин соседних (по вершинам) треугольников в эту окружность.

    Даблы получают WA7. Дроби на лонглонгах WA11. Дроби на даблах AC.

    Не для слабонервных

    У меня WA3 было когда сначала неправильно находил серединный перпендикуляр. Потом когда неправильно решал систему.

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

      Написал все в лонгах. на вики есть статья, как легко определить попадает ли точка в описанную окружность

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

        Делал в даблах, делил на sqrt и прочую нечисть, никаких эпсилонов, ОК.

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

    надо проверить свойство, описанное в условии. для каждого треугольника ни одна из вершин всех остальных треугольников не должна лежать строго внутри описанной окружности

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

Как решать A? Мы придумали персистентное декартово дерево, но оно по памяти не заходит.

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

    Построим дерево деления плоскости следующим образом. Разобьем bounding box на два прямоугольных треугольника, а каждый треугольник будем делить рекурсивной процедурой следующим образом: если треугольник не содержт внутри себя других точек множества, то этот треугольник назовем листовым и ничего делать не будем, а иначе выберем случайную из точек, лежаших внутри треугольника, разобьем его на три с помощью этой точки и запустимся от них рекурсивно.

    Таким образом, мы получим дерево из треугольников, в котором листы образуют корректную триангуляцию нашего множества. Имея такое дерево, легко по точке получить треугольник триангуляции, содержащий ее. Из каких-то эмпирических сооображений следует, что глубина такого дерева будет близка к логарифмической.

    Тем не менее, с интересом бы послушал, какие еще решения сдавали.

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

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

      А покажешь свой код? У меня такое зашло в дорешку, но мне не нравится моя реализация :)

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

        Код не очень красивый, потому что в рекурсивной функции построения хотелось уйти от векторов и динамической памяти и сделать все in-place. Еще я заметил, что там есть bounding box (и что на выпуклой оболочке всегда ровно четыре точки) только под конец, поэтому там есть бинарный поиск чтобы найти, в какой из треугольников выпуклой оболочки попала точка :)

        У тебя код гораздо чище и аккуратнее.

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

В условии сказано:

Данные, хранящиеся в KSON, можно представить в виде дерева, в котором промежуточными вершинами являются объекты, а листьями — строки-значения или пустые объекты.

Думаю, что же такое имеют ввиду авторы под пустыми объектами. Наверно, {}. Задаю вопрос жюри:

Что такое пустые объекты упомянутые в условии?

Получаю ответ:

""

Отлично. Какое хорошее жюри, решило не давать такой корнер кейс. Но в восьмом тесте есть {}, и если заменять ссылку на {} на "", то получается WA, а если не заменять — OK. Чем же тогда является {} как не листом в дереве и как его наличие в тестах соответствует с условием? Можно было бы понять ответ жюри, если бы ссылки на {} нужно было бы преобразовывать в "", но нет, их не нужно ни во что преобразовывать.

Призываю жюри ответить, почему был дан такой ответ на вопрос по задаче.

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

    Вопрос был понят скорее как "бывают ли пустые строки" — на него приходилось отвечать много раз.

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

      В вопросе специально было указано "упомянутые в условии".

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

        Судя по всему, корректность 8 теста сомнительна, так как фраза " Этот список ключей указывает путь от корня KSON к некоторому листу, хранящему строку-значение" подразумевает, что если лист есть, то он хранит соответствующее значение.

        Вариант, что лист есть, но он хранит {}, в данной формулировке кажется несколько неестественным. Возможно, что 8-й тест будет удалён.

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

          А можно узнать 10 тест?

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

          Возможно ли, что жюри в будущем будет более формализовывать условия задач, в которых так важен формат входных данных, или, хотя бы, отвечать "I am Groot" на вопросы участников, не вызывая у них неправильного понимания условия?

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

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

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

            Да вроде пофиг. Опенкап — неофициальное соревнование. Тот факт, что Яндекс платит за него деньги, все еще не делает его официальным.

            Но условия, конечно, хлам полный. У нас вчера еще в трети задач ограничения в кларах приходили :)

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

              Просто интересно, а что ты тогда считаешь официальным соревнованием?

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

                Начнем с наличия более-менее внятной регистрации :)

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

                  Свободной (не через секторы) и анонимной регистрации на OpenCup не будет. Соответственно, не будет ни школьных "команд" из одного человека, ноющих на форумах про то, почему не решается самая простая задача из второго дивизиона, ни максиманов-бредоров с 15 аккаунтами у каждого, ни северокорейских команд по 30 человек.

                  Возможные изменения в схеме регистрации скорее уж могли бы быть в сторону какой-то интеграции с baylor-овской базой для команд, участвующих в ACM-зачёте (в частности, в спонсорском), если бы baylor предоставил соответствующий API.

                  А в чём претензии к существующим правилам регистрации секторов? Казалось бы, всё детально расписано.

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

            Вот как-то я предполагал, что если планируется сначала провести онсайт, то условия будут кем-то, кроме авторов, вычитаны. Причём перед этим самым онсайтом.

            А за сутки отменять этап всё-таки уже поздно.

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

          ...удалено (решил ...)

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

      А как Вы отвечали на данные вопросы? "Да, могут"?
      Как минимум, должен был быть общий клар по этому поводу.
      Когда я писал код по этой задаче, я, наоборот, отталкивался от того, что ключи не могут быть пустыми строками (ибо как-то это глупо).

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

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

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

Нету у кого-нибудь крутого теста на K?(WA test #10)

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

    А Вы правильно обработаете Value:key. и Value: ?

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

      Да, обработав второе стал проходить второй тест. После первого 6-ой. А сейчас даже не знаю в чем ошибка =(

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

        У меня еще было что неправильно обработал случай value.key, когда key есть объект kson у которого есть пара "" : "some string".

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

      А что должно в ответе получаться-то? Надо обращаться по ключам нулевой длины?

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

Да вроде никто уже и не удивляется наркоманским условиям уральских контестов.

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

Так как все-же H решать?

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

    Гуглить по словам "алгоритм шраера-симса".

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

      Да, я видел ссылку выше. Так ничего конкретного не находится.

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

      Нам гуглить не помогло — мне кажется это понять и закодить меньше чем за 2-3 часа не выйдет :)

      Помогло только найти опенсорсную библиотеку и заинлайнить её в один файл Егоровским плагином.

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

        Ну ты преувеличиваешь сложность. Мне halyavin минут за пять его полностью рассказал, говорит, что на туре они его придумали за пару часов. Могу вкратце пересказать, если интересно, о чём оно :)

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

          Ну я же написал "понять" — halyavin эту работу сделал за тебя :) Или ты знаешь, где в интернете настолько понятно написано?

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

            Ну я про сложность решения, а не про сложность конкретного изложения :)

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

          Очень интересно, расскажи вкратце, пожалуйста.

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

            Сорри за задержку с ответом. Вот код решения: http://pastebin.com/Rayq5Lfe

            Алгоритм Шраера-Симса для чайников:

            Идея такая. У нас есть некоторая группа, порожденная данными перестановками: . Выделим в ней подгруппу G1, являющуюся стабилизатором единицы: она будет состоять из всех перестановок, которые мы можем породить, которые оставляют единицу на месте. Тогда ответ, очевидно, равен p·|G1|, где p — количество различных мест, где может оказаться единица под воздействием всей G, а |G1| — мощность группы, оставляющей единицу на месте (иными словами, мы сначала ставим единицу на место, а потом дорасставляем остальные элементы). План такой: сначала считаем p, а потом рекурсивно сводим задачу к G1, предъявляя набор перестановок, порождающий G1.

            Сначала посчитаем, где вообще потенциально может оказаться единица под действием нашей перестановки. Будем для простоты считать, что единица может оказаться на местах 1, 2, ..., l. Найдем все этим места простым DFS'ом, используя применения исходных перестановок как ребра. Каждой из этих позиций будет соответствовать какая-то своя перестановка , которая ставит единицу на место i: σi(1) = i, эти перестановки мы тоже посчитаем в DFS'е.

            Утверждение: G1 порождается всеми произведениями вида , где — произвольная образующая группы G, sigmai — любая из сигм, а j выбирается таким образом, чтобы после применения σi и загнать единицу обратно на первое место. Действительно, такое произведение будет лежать в G1, так как оно оставляет единицу на месте. Почему такими произведениями все порождается? Рассмотрим произвольный элемент G1. Он получается произведением каких-то образующих G: , где все — это какие-то образующие G. Перепишем это произведение в виде , нетрудно видеть, что перестановка не изменилась от этого, но теперь очевидно, что она порождается набором перестановок, который я назвал выше.

            Отлично, теперь мы можем совершить рекурсивный переход: ответ на нашу задачу это l умножить на ответ на задачу G1, для которой мы знаем набор образующих (из них всех можно смело выкинуть единицу, так как они все оставляют единицу на месте). Однако, за один такой шаг мы увеличиваем количество образующих в l раз, что приводит к экспоненциальному времени работы.

            Теперь ключевое соображение заключается в том, что если есть огромный набор образующих, то из него всегда можно только n(n - 1) / 2 осмысленных. Это делается некоторым подобием метода Гаусса. Рассмотрим k перестановок. Заметим, что можно оставить максимум одну перестановку, у которой на первом месте 2, максимум одну перестановку, у которой на первом месте 3 и так далее (если σ1 и σ2 обе переводят 1 в x, то σ2 можно заменить на σ1 - 1σ2). Проделаем такую операцию, после чего мы получим n - 1 перестановку с чем-то нетривиальным на первом месте и дофига перестановок, которые оставляют единицу на месте. Проделаем с ними то же самое, и так далее.

            Теперь ход алгоритма понятен: на каждом шаге мы сводим задачу к перестановкам на единицу меньшего размера, а потом фильтруем образующие описанным выше методом. Работает типа за n3, кажется.

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

        У меня он был написан в качестве заготовки для задачи, не вошедшей в прошлогодний Hackercup :)

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

В I же минкост заходит?

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

Покажите этот блог знакомому школьнику, который думает увлечься спортивным программированием. Не дайте ему совершить нашу ошибку

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

    А еще ссылка на обсуждение на официальном сайте соревнования ведет на пост с названием "вертел я такие условия"

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

      А какие будут конструктивные предложения?

      Это ветка обсуждения проблемсета. Другой ветки с обсуждением нет. Не ставить ссылку на обсуждение с официального сайта недопустимо.

      Качество условий действительно оказалось не на высоте, экспресс-попытка это исправить оказалась неудачной (как минимум, не по всем задачам). Всё же авторам стоит давать кому-то из опытных проблемсеттеров доступ к задачам на вычитку до начала онсайт-раунда.

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

where can see the problems?

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

Как насчет задачи J?

Правда ли что ненулевых запросов может быть только 2?

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

    неправда

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

    нет, неправда

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

    Пара хинтов:

    1. Изначальная матрица нам не нужна, в конце просто прибавим ее к ответу. Далее считаем что она нулевая.

    2. Пусть ответ это матрица d, тогда dij = dik + dkj для любых i, j, k.

    3. Из второго пункта следует, что существует такой массив φ, что dij = φj - φi.

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

      Можно узнать, как найти этот массив?

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

        ну нужно решить систему уравнений φt - φs = deltast. Попробуй решить такую систему уравнений, когда граф состоящий из ребер из s в t — дерево.

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

Как доказать, что в В асимптотика ?

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

    Не понимаю, откуда взялось , но там вроде можно за , где f(C) — максимальное число делителей среди чисел от 1 до C.

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

Что с опенкапом в итоге, зачётный этап или нет? "Положение в кубке" на opencup.ru до сих пор не обновилось.

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

    В общем зачёте этап зачётный. Остальное обдумывается (в основном на предмет совместимости задачи H и спонсорского зачёта).

    UPD: Вряд ли четыре балла в спонсорский зачёт, полученные формально законным, но не вполне этичным для команды ACM-зачёта путём, на что-то повлияют, так что этап включён и в спонсорский зачёт. Результаты на сайте обновлены.

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

Что это за тема с отбором "по спонсорскому зачету в Петрозаводск"? Впервые слышу.

»
23 месяца назад, # |
  Проголосовать: нравится -60 Проголосовать: не нравится

thanks Zlobober