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

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

Странно, что никто ещё не написал об этом.

Сегодня проходит (уже заканчивается) заключительный этап Opencup сезона XI (Весна 2012). После окончания предлагаю обсудить задачи здесь.

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

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

какое ограничение на размер посылаемого файла стоит на сервере?

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

Расскажите, пожалуйста, как решать С и D.

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

    C: Построим явно перестановку. Легко за O(n) найти ее порядок[upd:судя по всему порядком называется нечто другое.](просто ищем все циклы, вершины, которые входят в какой-то цикл повторно не обрабатываем.

    Помогло добавление if(n<k) return 1;

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

      Можно подробнее, а то совсем непонятно про циклы и прочее...

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

        Нашли перестановку p(n) ищем такое минимальное k, что p(p(...p(n)..) (k раз) = id.

        Для этого для каждого числа находим такое K и берем НОК по всем. Пока что это o(n^2) на тест. Заметим теперь, что если для x данный ответ k, то для p(x) p(p(x)) итд тоже, поэтому теперь можем искать за О(n) на тест

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

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

        теперь поймем, что если карта стояла на месте i и переходит в позицию p[i], то для позиции p[i] количество действий нужное для ее возврата в позицию p[i] равно количеству действий для i. аналогично для p[p[i]], p[p[p[i]]]...

        т.о. найдем длины всех циклов, найдем их НОК — это и есть ответ

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

      Порядком элемента называется такое минимально k что элемент в этой степени тождетвенный, так что именно это =)

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

        ну я сперва так счтиал, а потом меня смутило определение на википедии, поэтому исправил, все равно ниже формально определил, что хочу

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

      Можете объяснить, почему этот код (задача С) получает RE 2?

      http://pastebin.com/p2mnPxHp

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

        У меня тоже RE2 было на контесте, переписал на BigInteger(java) и зашло.

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

          gcd стек не переполняет, особенно такой)

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

          Потому что надо писать не a*b/gcd(a,b), а a/gcd(a,b)*b

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

            Ну я так и пишу, тем не менее :)

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

              Это я к посту про BigInteger, почти уверен что ошибка была в этом

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

                Интересный факт: если строку 61 заменить на while (x != i) получается TL 2.

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

    D: Изначально мы знаем, что самый нижний диск нужно положить на стержень B и только. Идем с конца строки (то есть по уменьшению размера дисков) и смотрим куда нам нужно положить этот диск(i, индексация с нуля):

    1) Если у нас диск сразу лежит в нужном месте, то логично, что меньший диск (i — 1) нужно кинуть на него и сумма не меняется;

    2) Иначе мы прибавляем к сумме перекладывание, которое будет необходимо для того, чтобы переложить этот диск на нужный стержень + количество, которое нужно для перекладывания всех меньших дисков с оставшегося стержня (считаем, что все они уже там). Это будет (1 + (2^i — 1)), то есть 2^i. Теперь мы знаем что (i — 1) диск должен лежать на оставшемся стержне (Например: перекладываем с А на В — меньший лежит на С).

    Ну и идем так до начала строки, каждый раз решая похожую задачу для меньшего количества дисков. Разница лишь в том, что меняется стержень, на который надо кидать. Как-то так :)

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

Как решать J? Никогда бы не подумал, что такое решается, да еще и не очень адово.

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

    Строим convex-hull за квадрат: берём какое-то ребро выпуклой оболочки (как его найти — отдельный вопрос), ищем 2 грани этого ребра (за проход по всем точкам), для рёбер граней повторяем то же самое.

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

    Я умею инкрементально строить: начинаем с трёх точек, когда добавляем точку, находим, какие грани будут удалены, какие добавлены, и перестраиваем. Не знаю, насколько это адово, но подебагать пришлось.

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

    Совсем не адово. Вот код. Я такое на контесте раза 4 писала, идея как у eatmore.

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

    Мне куда интереснее, как можно за разумное время написать H. J писал первый раз выпуклую оболочку 3D, но достаточно просто вышло.

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

      В H я может быть что-то не так понял, но вроде ничего сложного: сделали для каждого круга события, когда он появился в поле зрения и когда исчез (если этот отрезок углов пересекает ноль, разбиваем его на два), посортили события, прошли. Совсем мало кода. Только WA 2.

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

        Всё правильно. WA2 может получиться, если считать, что длина каждого отрезка меньше половины окружности (а это не так). Ещё один особый случай — когда красный круг касается оранжевого.

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

          А чем выделен случай касания?

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

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

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

        Ой. Мы все трое что ли неправильно поняли условие? Бывает же такое. Из английской версии, сложилось ощущение, что надо считать отношение площадей. Так да. Задача значительно проще.

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

          Please help the museum folks determine the proportion of the circumference of the purple platform from which all of the red gem is visible, completely unobstructed by the orange gems.

          Circumference — окружность.

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

            В русской это значительно лучше прописано. Но и отсюда понимается однозначно. Чисто наш косяк. Даже не спорю.

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

Как решать I? (вроде) Свел к тому, что нужно уметь находить 1 любую расстановку, если она есть. Дальше не получилось

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

    Перестановку Куном найти можно же. А как свести к тому что ты написал?

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

    Построим граф исток -k- первая доля -матрица- вторая доля -k- сток, k бинпоиском

    Если в нем нет полного потока, то, очевидно, задача неразрешима.

    Если в нем есть полный поток, то по лемме Холла из него можно восстановить ответ, найдя паросочетания k раз.

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

а как решалось К?

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

    Будем восстанавливать ответ слева направо.

    Ясно, что если у набора зафиксировано первых i символов, а последним стоит символ с номером j, то количество наборов длины n с таким префиксом равно C(n — i, m — j).

    Будем пытаться поставить на i-ую позицию символ j. Если количество наборов с таким префиксом меньше K, то вычитаем это количество из K и переходим к следующему символу. Иначе ставим данный символ на i-ую позицию и переходим к позиции i+1.

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

      спасибо конечно за ответ, но нечего непонял

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

        Могу привести пример, может с ним будет понятнее:

        N = 5, M = 3, I = 8

        1) Пытаемся поставить на 1 место '0'. Количество наборов вида 0.. равно C(5 — 1, 3 — 1) = С(4, 2) = 6, что меньше I -> I = 8 — 6 = 2

        2) Пытаемся поставить на 1 место '1'. Количество наборов вида 1.. равно С(5 — 2, 3 — 1) = C(3, 2) = 3, что больше I -> на 1 месте стоит '1'.

        3) Пытаемся поставить на 2 место '2'. Количество наборов вида 12. равно C(5 — 3, 3 — 2) = C(2, 1) = 2, что равно I -> на 2 месте стоит '2'.

        4) Пытаемся поставить на 3 место '3'. Количество наборов вида 123 равно C(5 — 4, 3 — 3) = C(1, 0) = 1, что меньше I -> I = 2 — 1 = 1

        5) Пытаемся поставить на 3 место '4'. Количество наборов вида 124 равно C(5 — 5, 3 — 3) = C(0, 0) = 1, что равно I -> на 3 месте стотт '4'.

        Таким образом наш ответ — '124'

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

а в В считаем динамику d[i] — покрыть первые i точек, поддерживаем выпуклую оболочку (x[i], d[i — 1] + x[i] * x[i]) и в ней указателем лучшее разбиение находим?

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

    Типа того. Обновление оболочки — выкинуть несколько последних вершин и добавить новую. Поиск ответа — бин. поиском.

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

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

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

В A — стратегия: на каждом шаге строим как можно больше рабочих, на все остальные деньги строим заводы. Если нужны солдаты, то вначале пытаемся делать их вместо рабочих на текущем шаге, если не хватило — то на предыдущем, если всё равно не хватило — fail.

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

    Кстати, а эта стратегия доказуема? Мы это засылали не доказывая, в надежде на вселенский рандом.

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

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

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

      У меня решение без отката назад. Рассматриваем текущий день. Если нам нужны солдаты, чтобы воевать сегодня — делаем их, не можем — fail. Возможно, нужно делать солдат, чтобы воевать завтра. Посмотрим, сможем ли мы их всех сделать завтра. А именно, по текущему дню однозначно определяется, сколько фабрик у нас будет завтра (+количество работников минус количество фабрик). Если этих фабрик хватит, чтобы сделать всех необходимых солдат завтра — не делаем сегодня. Про послезавтра не задумываемся в силу утверждения. Иначе определяем, сколько сделать сегодня.

      Не совсем детальное доказательство, конечно, но мне хватило, чтобы считать решение полностью доказанным :)

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

а какое ограничение на m в задаче G?

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

    Статического массива на 221 хватило. По идее, там нет кратных ребер. То есть, в худшем случае, не более N(N — 1) ребер (не стал делить на 2, ведь каждое ребро может быть одного из двух цветов).

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

    По-моему, там было написано, что каждое ребро не более 1 раза.

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

А у меня одного был ступор в B и мысль, что требуемое решение должно работать за O(n) ?

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

кто-нибдудь может объяснить, почему в С не получается большой ответ, вылазящий за long long?

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

    гарантируется условием.

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

      где это гарантируется?

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

        В последней строке Output'а: All possible inputs yield answers which will fit in a signed 64-bit integer.

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

          К сожалению, в русской версии условия это предложение любезно опустили.

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

            Вот и какие условия лучше читать? бывали случаи, что и в одной версии условия опускали что-то... и в другой =(

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

              Лучше всегда на языке оригинала. Кэп подсказывает, что для задач Гран-При Америки язык оригинала — не русский ;)

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

                А вот мы читали условия на языке оригинала и по фразе "Output this number with 4 decimal places of accuracy" в задаче J сделали вывод, что достаточно выводить правильно первые четыре цифры числа (чтобы относительная погрешность не превышала 10 - 4). Мы выводили даже 6 цифр, и наше решение не прошло по точности, хотя при изменении формата вывода проходит. Оказывается, что русский перевод "выведите с точностью 10 - 4" больше соответствует чекеру :)

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

                  Первые три нагуглившиеся ссылки (1, 2, 3) говорят о том, что так по-английски всё-таки называются знаки после запятой, а не значащие цифры.

                  Скорее уж условие на русском ("с точностью 10 - 4") можно понять неправильно: абсолютная или относительная погрешность имеется в виду?

                  Ну и, конечно, не очень хорошо, что это не следует из примера.

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

                  В третьей ссылке приводится разница между accuracy и precision. Там есть примеры.

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

                  Да, пример явно указывал на то, что выводить ровно 4 знака после точки необязательно)

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

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

                  Опс, а я не дочитал до этого места, только первую страницу посмотрел. То есть decimal places (авторское понимание) конфликтует с accuracy (ваше понимание), вместо accuracy в правильной фразе должно быть precision или пусто, так?

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

                  Согласно примерам, accuracy измеряется в significant digits, а precision — в decimal places. В условии задачи шла речь об accuracy в decimal places. Поэтому мне честно непонятно, что имели в виду авторы. Почитав документ 3, больше склоняюсь к тому, что они имели в виду accuracy (т.е. относительную погрешность, как и мы).

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

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

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

                  Ответ Gassa: да, если по условию требовались именно 4 знака после десятичной точки, то вместо accuracy должно было быть precision. Это бы исключило двоякое понимание. По крайней мере, у людей, разбирающихся в данном вопросе. Хотя все равно хотелось бы более доходчивого объяснения в условии (например, фразы типа "после десятичной точки" или "отличающийся от правильного не более чем на 10 - 4") для чайников.

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

                  Кроме того, если бы в системе стоял стандартный чекер (rcmp4), проверяющий, что абсолютная или относительная погрешность не превосходят 10 - 4, то решение, выводящее шесть знаков в сумме, прошло бы, потому что в этом случае относительная погрешность была бы меньше. Я скачал тесты с сайта американского полуфинала и проверил. Значит, в системе какой-то другой чекер для вещественных чисел.

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

    Потому что авторы специально составили тесты так, чтобы ответ не вылезал за long long. И написали об этом в условии.

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

А как решать E и G? Выгодно ли в Е присваивать некоторому подмассиву значение его медианы?

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

    В E вроде баянистый факт, что всегда надо брать медиану для подмассива — посчитаем f[i][j] — значение при b[i] = b[i + 1] = b[i + 2] = ... b[j] = медиане подмассива [i..j]

    и dp[K][N] — на сколько уже блоков разбили, конец последнего блока. переход: перебираем конец следующего блока

    надо только быстро считать f[i][j]

    В G: обозначим B — ребра весом 1, R — ребра весом 0, построим минимальный остов, если его стоимость больше, чем k, ответ 0, иначе попытаемся заменить каждое красное ребро на какое-то синие, чтобы граф оставался связным (эту жадность нетрудно доказать)

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

      Чем легче всего быстро считать f[i][j]? Декартовым деревом?

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

        Эта медиана — всегда одно из a[i]. Посортим все a[i], оставим только уникальные, и для каждого подотрезка [L..R] запустим тернарник.

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

          более того, это вроде средний элемент в массиве.

          а за сколько это будет? за N^2 все отрезки, еще за NlogN сортировка, нет?

          или я что-то не понял?

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

            Сортировка один раз в самом начале.

            То, что в первой правке, вроде бы необязательно...

            Да, тернарник найдет средний элемент в массиве, но я не придумал как его считать по-другому.

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

              ааа... все понятно.

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

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

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

        можно и им, можно вроде еще мутить следующую вещь: переберем начало — i, для суффикса [i..n] посчитаем втупую (отсортируем суффикс и возьмем средний).

        теперь заведем двусвязный список по отсорченному массиву и дерево фенвика (или дерево отрезков) для суммы, изначально в дереве фенвика все значения = 1, означает что этот элемент есть в нашем двусвязном списке.

        теперь удаляем элемент j (изначально j = n), переходим к отрезку [i..j-1], поддерживаем для каждого отрезка медиану, при переходе к следующему отрезку медиана может сдвинуться на 1 влево или вправо, дерево фенвика нужно для того, чтобы узнавать сколько элементов на отрезке [0..указатель на текущую медиану], если это значение больше чем номер медианы, сдвигаем влево на 1, если меньше вправо — переход вправо или влево по двусвязному списку.

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

        кто-нибудь может написать, как делать это красиво?

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

          Ну если за n^2*lg(n) решать, то просто декартовым деревом делается. Там, по сути, только добавление же нужно + k-ый элемент, а это сплит один и всё.

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

            нет, все это шлак, мне нужно поистенне изящное решение

            существует подозрение, что для всех отрезков величину f[i][j] можно узнать за N^2

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

    Решение G: вначале проверим, что граф связный, иначе дерева не существует. Пусть в графе n вершин, cr компонент связности по красным рёбрам и cb компонент связности по синим рёбрам. Тогда нужное дерево существует тогда и только тогда, когда cr - 1 ≤ k ≤ n - cb.

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

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

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

        как вообще это в голову может прийти?!

        не говоря уже о доказательстве

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

          Опыт и интуитивное понимание предмета задачи (в данном случае — остовных деревьев).

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

          Остовные деревья — хороший объект. Хорошие объекты обычно существуют, если им ничего так явно не мешает. Например остовное дерево существует если ему не мешает разрез 0 величины.

          Посмотрим что может явно мешать
          1) Слишком много компонент по синим ребрам. Тогда просто не бывает дерева в котором так много синих ребер.
          2) Слишком мало компонент по красным ребрам. Тогда придется брать много синих.

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

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

        Ну, например, вначале построим дерево с k = cr - 1, а потом будем вставлять в него синие рёбра по одному. При вставке ребра смотрим путь между его концами по дереву: если на нём только синие рёбра, то тогда не вставляем новое ребро, иначе выкидываем одно из красных рёбер на этом пути и вставляем синее. В итоге всё, что было связано по синим рёбрам в исходном графе, будет связано по ним и в дереве, значит, в дереве будет n - cb синих рёбер. Поскольку на каждом шаге количество синих рёбер меняется не более чем на 1, любое промежуточное значение также можно получить.

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

      Проверять связность, кстати, необязательно — она дана в условии А так у нас в точности такое же решение