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

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

Можно прокрутить пост до низу и прочитать доказательство корректности построения суммы Минковского, которе недавно обсуждалось на КФ.

Задача DIV1-A, DIV2-C Поезда.
К этой можно было подойти с двух сторон - как программист и как математик. Рассмотрим оба подхода.

Сначала запишем несколько общих суждений. Поставим на прямой все моменты времени, в которые приходят поезда. Будем относить отрезок между двумя соседними точками к той девушке, к которой идет поезд, соответствующий правому концу отрезка. Также заметим, что вся картина периодична с периодом lcm(a, b). Очевидно, что Вася будет чаще ездить к той девушке, суммарная длина отрезков которой больше.

Программистский подход заключается в моделировании процесса. Если нам надо сравнить длины двух множеств отрезков - давайте их посчитаем. Это делается с помощью двух указателей. Смотрим какой поезд поезд приедет следующим, прибавляем время до прихода этого поезда к одному из ответов, двигаем указатель и текущее время. Остановиться стоит либо когда два последних поезда пришли одновременно, либо когда пришло a+b поездов. Решение за O(a + b),что с запасом укладывается в ограничение по времени. Не забываем, при этом, что lcm(a,b) ~ 10^12, то есть нужен 64-битный тип данных.

Математический подход позволяет получить более изящное и короткое решение, однако придется больше подумать. Кажется очевидным, что чаще Вася будет ездить к той девушке, к которой чаще ходят поезда. Этот факт почти верен. Попробуем его доказать. Сократим периоды a и b на их gcd - от этого, очевидно, ничего не изменится. Пусть для определенности a ≤ b. Посчитаем суммарную длину отрезков, соответствующих второй девушке. Для этого заметим несколько фактов.
1) Все они не превосходят a
2) Все a отрезков различны (из-за взаимной простоты).
3) Все они хотя бы 1.
Но такое множество отрезков - единственное и его длина равна . Причем равенство достигается при b - a = 1. Значит верно следующее. Ответ равен Equal, когда |a - b| = 1, иначе чаще Вася ездит к девушке к которой чаще ходят поезда. Главное не забыть поделить a и b на их gcd.

Задача Div1-B, Div2-D Вася и Типы.
В этой задаче нужно было написать ровно то, что написано в условии задачи, практически за любую сложность.
Предлагается делать это так. Для каждого типа данных будем хранить два значения – его имя и количество звездочек при его приведении к void. Тогда запрос typeof обрабатывается пробегом по массиву определений, в котором мы находим нужное нам имя типа, и количество звездочек в нем.
Тип errtype удобно хранить как void, к которому приписали  - inf звездочек.
Таким образом, выполняя запрос typedef, мы находим количество звёздочек при типе A, добавляем к нему количество звездочек и вычитаем количество амперсандов. Не забываем заменять любое отрицательное число звездочек на  - inf, и создавать новое определение типа B, удаляя старое.

Задача Div1-C, Div2-E Интересная игра.
В этой задаче нужно провести анализ игры. Однако, из-за того что каждым ходом игра распадается на несколько независимых, анализ можно провести с помощью функции Гранди (можно почитать здесь, здесь или здесь). Остается построить переходы для каждой позиции. Можно строить переходы отдельно для каждой вершины, решая O(sqrt(n)) несложных линейных уравнений. Можно построить все разбиения заранее, просто перебирая наименьший член и количество, и вылетая, когда сумма превосходит n. Второй способ лучше, потому что он работает за O(m + n), где m - количество рёбер, а первый - за O(nsqrt(n)), что побольше.

Оценим m в максимальном тесте. Рёбер - не более . Однако на практике их гораздо меньше - порядка 520 тысяч. Соответственно, рёбра вполне можно успеть построить за время O(nk).

Можно попытаться посчитать функцию Гранди по определению - ксоря все нужные значения для каждой позиции. Но такое решение не проходит - слишком много длинных разбиений.
Научимся для длинного разбиения быстро считать ксор функций Гранди. Используем стандартный прием для подсчета функций на отрезке - xor[l, r] = xor[0, r] xor[0, l - 1]. По ходу алгоритма будем поддерживать в xor[i] ксор на префиксе до i. Тогда и ксор на отрезке можно посчитать за O(1). Решение получилось строго за количество рёбер, которое не очень велико.

Задача Div1-D. Красивая дорога.
В этой задаче надо для каждого ребра посчитать количество путей, на которых оно является максимальным. Так как для одного ребра отдельно не кажется  возможным посчитать ответ быстрее, чем за линейное время, решение будет обрабатывать все ребра вместе.
Решим задачу сначала для двух крайних случаев, потом, объединив эти два, получим полное решение.

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

Второй случай – когда веса всех ребер различны. Отсортируем ребра в порядке возрастания веса. Изначально возьмём граф, в котором нет рёбер. Будем добавлять по ребру в порядке возрастания веса, для каждого ребра объединяя компоненты связности, которые оно соединяет. Тогда ответ для каждого нового добавленного ребра – произведение размеров компонент, которые оно соединило.

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

Для того, чтобы посчитать это самое количество рёбер по разные его стороны, поймём, что от старых компонент связности достаточно знать лишь их размеры, и связи между ними - то, как они были устроены нам не важно. Воспользуемся системой непересекающихся множеств: добавляя рёбра в наш лес мы объединяем старые компоненты связности по этим рёбрам. Заметим, что до объединения компонент мы должны посчитать ответ для наших рёбер - а это можно сделать обходом в глубину на нашем сжатом дереве как в первом случае, только вместо количества вершин по разные стороны от ребра мы берём сумму размеров компонент связности по разные стороны от ребра.

Как это аккуратно реализовать:

  • Сжатый граф проще всего динамически создавать на каждом шаге: в нём будет O(E’) вершин и рёбер, где E’ - количество добавляемых рёбер исходного дерева.
  • В новом создаваемом сжатом графе не создаём ненужных вершинок: DFS работает всё-таки за O(V + E), а не за O(E), поэтому незадействованные компоненты связности мы в обход не включаем.
  • Пользуемся 64-битным типом данных. Для хранения ответа порядка (105)2 он подойдет больше чем 32-битный.
  • Не сливаем явно списки смежности при соединении компонент. Это слишком долго.
  • Можно вместо массивов делать всё на vector’ах / map’ах / динамической памяти, чтобы суммарное время обнуления массива пометок для DFS’а занимало O(V). Либо вместо обнуления массива пометок держим вместо булевского флага номер итерации. И вообще, лучше не обнулять лишних массивов. Все таки алгоритм может делать V итераций.
  • Осторожно, решение с map работает на пределе TL, поэтому его надо писать очень аккуратно, лучше использовать вектора + список задействованных вершин. Авторское решение с map укладывается в TL с запасом всего в полсекунды. В то время как использующее вектора имеет четырёхкратный запас по времени.


Задача Div1-E. Идол Могоху-Ри.
В этой задаче надо было проверить, что точка являться центроидом треугольника образованного точками из данных трех многоугольников. Переформулируем задачу. Надо проверить существование трех точек A,B,C, таких, что A принадлежит первому многоугольнику, B – второму, C – третьему, и . Вполне логично, что надо понять какое множество точек задает это , научится его строить и проверять точку на принадлежность ему. Такое множество называется суммой Минковского. Из его свойств нам понадобится только одно: сумма двух выпуклых многоугольников - выпуклый многоугольник, причем стороны многоугольника совпадают, как вектора, со сторонами исходных многоугольников. Докажем это позже.
Как теперь этим пользоваться? Первое что нам дает это свойство - алгоритм проверки на принадлежность. После того как сумма будет построена проверять точку на принадлежность сумме можно стандартным алгоритмом проверки точки на принадлежность выпуклому многоугольнику за логарифмическое время. Кроме того сразу же получается и алгоритм построения. Надо просто сложить координаты самых нижних (из них самых левых) точек всех трех многоугольников. В результате мы получим точку, являющуюся нижней левой для последнего многоугольника. А стороны получаются как отсортированный по полярному углы список сторон исходных многоугольников (вместо сортировки сливать отсортированные массивы).

А теперь самая вкуснятина:

Доказательство.
Доказывать свойство будем для дух выпуклых многоугольников M1 и M2. Сумму обозначим за M.
Докажем корректность алгоритма для двух многоугольников, для трёх многоугольников доказтельство никак не поменяется. Пусть первый многоугольник - А, второй - B. Пусть сумма Минковского - M.
Докажем, что M - выпуклое множество.
Выберем некоторые . По определению Q,  (здесь и далее точка отождествляется со своим радиус-вектором).
Пусть некоторая точка . Докажем, что .
Т. к. G лежит на [AB], .
Заметим, что первая скобка, очевидно, есть некоторая точка, лежащая на отрезке [PE]. А значит, точка, лежащая внутри многоугольника A, так как тот - выпуклый. Аналогично, вторая скобка лежит внутри B. Значит их сумма, то есть G, лежит в сумме Минковского. А значит, сумма Минковского есть выпуклое множество.

Рассмотрим некоторую сторону XY первого многоугольника. Повернём плоскость так, чтобы сторона XY оказалась горизонтальной и чтобы многоугольник лежал сверху от прямой XY
Рассмотрим самую нижнюю горизонтальную прямую, пересекающую B. Пусть она пересекает B по отрезку PR, где точка P не правее R (понятно, что PR может оказаться вырожденным отрезком из одной вершины). Назовём PR самым низкий отрезком многоугольника. Построим по аналогии самый низкий отрезок UV многоугольника M.
Докажем, что - в противном случае . Понятно, что x и p - самые нижние точки многоугольников A и B - в противном случае одну из них можно сдвинуть на малый вектор d, лежащий в нижней полуплоскости, так, что точка останется внутри своего многоугольника. При этом U сдвинется так же на d, что противоречит тому, что U - одна из нижних точек многоугольника.
Значит, x и p - нижние точки своих многоугольников. Аналогично, x и p - самые левые точки на нижних отрезках своих многоугольников - в противном случае сдвигаем x или p на вектор d, направленный влево, вновь получая противоречие - точка U перестаёт быть самой левой из нижних.
Значит, U = X + P. Аналогично V = Y + Q. Значит, .

Тем самым, последовательность сторон M как векторов в порядке обхода, например, по часовой стрелке, есть как раз объединение сторон M1 и M2 как векторов в порядке обхода по часовой стрелке, что сразу доказывает корректность алгоритма.


Разбор задач Codeforces Beta Round 73 (Div. 1 Only)
Разбор задач Codeforces Beta Round 73 (Div. 2 Only)
  • Проголосовать: нравится
  • +65
  • Проголосовать: не нравится

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

> Можно попытаться посчитать функцию Гранди по определению - ксоря все нужные значения для каждой позиции. Но такое решение не проходит - слишком много длинных разбиений.


У меня самый тупой Шпрага-Гранди(причем рекурсивный) прошол=)

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Оказалось сильно мало переходов. Мы ожидали, что решение без ксора на отрезке будет получать ТЛ, засчет генерации переходов медленной, но это оказалось не так. Обнаружив это сегодня утром, мы решили оставить как есть.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Даже если решение без xor на отрезке было бы медленным, я бы скорее посчитала precalc, чем придумывала бы xor на отрезке :) 
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Пришлось бы долго его вгонять в 64кб.
        У нас была идея ограничить сверху количество кучек в разбиении, чтобы спастись от прекальков. Но тогда ломался xor на отрезке..
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Задача "Вася и типы" была в Div.2 задачей D, а не B
  • 13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Пардон. Буковки-то на одной кнопке оказались :-)
13 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится
А сколько строк в авторском решении по Е?
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

    У нас есть три решения ровно по 175, 225 и 275 строк.

    Мы не сговаривались о размере, честно :-)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Теперь все авторские решения можно посомтреть в системе, если найдете.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Как-то не выходит, по словам народа. Видимо, нельзя смотреть решения кураторов контеста ну вот совсем.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А ты не прав. Наши решения спокойно ищутся в списке решений задачи (по кнопочке x12 в дорешивании). Только там где много сабмитов надо аккуратно посортировать сначала.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Нет, остальные их просто не видят. Попробуй разлогиниться.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В D можно немного по-другому считать количество вершин по разные стороны от добавляемых ребер.
Можно в каждом ребре найти нижнюю вершину при подвешивании дерева за первую вершину (ту, которая располагается дальше от первой).
И тогда отсортировать ребра в случае равенства веса по глубине этой вершины.
Перебирая ребра с одним весом, мы для каждого ребра сохраняем количество вершин в компоненте нижней вершины (количество вершин ниже ребра). Это количество не изменится при добавлении ребер того же веса, так как следующие ребра с тем же весом будут находиться выше или в другом поддереве.
Тогда добавив группу ребер с одним весом, посчитаем для каждого ребра ответ (пусть A - количество посчитанных вершин снизу, а B - это количество вершин в компоненте с этим ребром): A * (B - A).
B после добавления всех ребер B - это суммарное количество вершин снизу и сверху.
Находить количество вершин в компоненте данной будем искать с помощью СНМ. Для каждого корня храним число элементов его цвета.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У нас по сути то же самое, только вид немного сбоку. Мы называли это выделением нового подграфа и т. д.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      То есть вы не строите на каждой итерации (новой группе ребер с одним весом) новый граф?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Строим. Просто мы не говорим что он подвешенный, а просто запускаем обход в глубину. 
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Я похоже понял....
          Вы считаете те же A и B, только не по ходу добавления ребер в СНМ, а дополнительно строите граф и пускаете каждый раз dfs.
          А что обозначает "динамически строим на каждом шаге?" Мы ведь каждый раз его строим с нуля?
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Мы можем слеплять компоненты связности, образованные ранее, в одни большие жирные вершины, и на них уже делать DFS за O(кол-во компонент) = O(E1), где E1 - количество добавляемых рёбер в группе.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Thanks for your nice editorial. would you please write the English version of D(DIV 1)?
13 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Да, хороший получился тур. Задачи интересные, и все приятно пишутся (включая сложные). Снимаю шляпу перед авторами!

P.S. Не понимаю, почему в C для отсечения решений "в лоб" нельзя было тупо увеличить ограничение на n - ведь если "в лоб" работает медленнее - явно можно было подобрать threshold, при котором эффективные решения проходили с запасом (скажем, за 0.5 сек), а неэффективные - падали...
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Было трудно так подобрать параметры, потому что непонятно было как меняется число рёбер в графе (оценка вида O(n^(3/2)) очень неточная, к сожалению). Оно растёт достаточно медленно, чтобы медленные решения угонялись за быстрыми.

    P. S. Чувствую себя как-то неуютно. Сам оранжевенький, втолковываю что-то красненькому. Ну вот зачем было сливать тур перед своим раундом?)
  • 13 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    Фича в том что т.н. "в лоб" (если его правильно готовить) работает значительно быстрее. Более того, это, похоже, единственный честный способ сдать задачу, например, на питоне.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Но ведь к любому решению "в лоб" можно прикрутить оптимайз с xor'ом на отрезке, который стоит O(n) памяти. Как это может повлиять на возможность сдачи задачи на питоне? Мы говорим об одном и том же лобовом решении?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Неа. Тут выигрыш идет за счет того что можно не считать гранди для ненужных значений.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Тогда можно подробнее? Какие значения функции Гранди можно не считать?
          • 13 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится
            Если писать ленивую динамику и перебирать разбиения только нужных чисел, то для n=100, допустим, мы переберем ответы только для чисел 9..16 и 18..22, ответы для бОльших чисел считать не надо. На этом можно получить значительный выигрыш.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Скорее всего мы бы так и сделали, если бы раньше обнаружили, что медленные проходят. Но в общем-то вышло как вышло. При достаточно объемных по коду D и E простая С не так уж и плохо.
13 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

Sorry, I can't quite catch up with your editorial with Div1 C, I will appreciate it if you give some more hint, thanks a lot!
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можна для входного примера задачи E(или какого-то другого примера) показать, какой будет многоугольник после вычисления суммы Минковского?
  • 13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    http://pastebin.com/YmH8mnum - вот мое решение. Вы можете с его помощь посмотреть любые промежуточные значения. Еще можно посмотреть любое другое решение проходящее на ОК.

    Для примера: (5 2), (7 2), (8 3), (8 4), (8 8), (6 8), (5 7), (2 4), (3 3), (4 2).

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Но если така сумма, то ей не принадлежать точки (1 1), (2 1), но у выходном примере для них написано YES.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Я кажется понял: когда считать сумму Минковского, получаеться необходимый многоугольник, умноженый на 3.
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится


13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а кто такой "Могоху-Ри" ? один из персонажей очевидно Винни Пух, а второго никак не подберу. Кроха-Ру не подходит.
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
QUOTE
"Thus, the sequence of sides M as vectors in the, for instance, counterclockwise order, is nothing other than the union of sides of A and B as vectors in the clockwise order, that immediately proves the correctness of the algorithm.”
Im confused about the "vectors in the clockwise order".Shouldn't it be "counterclockwise"?
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Yes, you're right. Fixed.

    ===

    Well, there exist at least one human, who read that up to the end :-) Great.

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

thank you for good editorial. can you say what do you mean by position in problem Div1-C? Do you mean the size of each pile or some piles together?

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

    Like in all problems that are solved using Grundy function, here position means "One pile of fixed size". It is true that if we have some piles of different sizes then games on each of them are independent — that's also the explanation why xoring of Grundy functions works correctly.

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

For Div 2 C — Trains, is there a proof for the fact that the segment lengths will be different (as mentioned in the editorial)?

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

    Yes, this can be proved by using the basic concepts of number theory. Let b > a, After dividing a and b by their gcd let new a = a/g, and new b = b/g, where g = gcd(a,b)

    Now gcd(a,b) = 1. Let's calculate for each instance b, 2*b,.....a*b, the length of the segment.

    For a*b the length of the segment will a. For i * b, i < a the length of the segment will be (i*b)mod a.

    Let for two different instances i, j < a, the length of the segment is the same.

    so i*b ≡ j*b mod a => i ≡ j mod a, as gcd(a,b) = 1, which is not possible as i and j are two different instances.

    Thus the contradiction proves, for two different instances, the length of the segment cannot be the same.

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

I understand everything, but why Vasya has two girlfriends?

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

For problem C div 1 I found another solution. First of all the divisions are in the following form:

  • (1 2), (2, 3), (3, 4), ... and these segments increases the sum of its elements by two.
  • (1, 2, 3), (2, 3, 4), (3, 4, 5) .... These segments increases the sum of its element by three.
  • And for a segment of length $$$l$$$ the sum increases by $$$l$$$.

So, we iterate over the lengths of the segments and then iterate over the sum of its elements by just adding the large of the segment (this takes n log(n) of time because it is the armonic sum) to the sum of the element we add an arist in the form {init_segment, init_segment + length — 1}. For example, we have (2, 3, 4) with sum 9 so to nine we add the segment (2, 4).

Now, we iterate over all the numbers in the range $$${1, \dots, n}$$$ and we iterate over its segments that we precomputed in the armonic sum. To get the xor of the segment we can use a segment tree and just query the segment that has and we make a xor, then we update the grundy number in the segment tree of the current element. With this we just get the grundy number of each number.

Finally, if the grundy number of $$$n$$$ is 0 then first player lost and if the grundy number is greater than 0 then we get the segment with shortest length which has grundy number 0.

With this code you can solve the problem in $$$O(n log(n)^2)$$$ because the sum of the edges are at most $$$n log(n)$$$ and we make a query in the segment tree over each segment that is $$$n log(n)^2$$$ :).