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

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

Div II A — Завидный забор

Задача

Нужно определить, существует ли правильный многоугольник, углы которого равны a.

Решение

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

Время: O(t).

Память: O(1).

Реализация: C++, Java

Комментарий

Задача также решается поворачиванием вектора (1, 0) на угол величины , пока он не вернётся на свою позицию (поворот делаем не более 360 раз), и проверяя, совершили ли мы ровно один полный оборот (пример реализации: C++).

Это также одна из редких задач на Codeforces, у которой всего 1 пример, 1 претест и 1 полный тест.

Div II B — Обсуждения

Задача

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

Решение

Если какой-то ai больше, чем ai + 1, то ясно, что ai точно был перемещён, так как порядок этих двух элементов изменился. Пусть последний такой элемент является ak. Тогда все элементы ak + 1, ak + 2, ..., an могли быть не затронуты операциями, так как их порядок не изменился. Ответ на задачу равен n - k. Если такого ak нет, то порядок не изменился вообще и тогда могло не быть операций.

Время: O(n).

Память: O(n) / O(1).

Реализация: C++, Java

Комментарий

Задача появилась, когда автор зависал на главной странице Codeforces, пытаясь придумать лёгкую задачу для Div II. =)

Div II C / Div I A — Волшебные ларцы

Задача

Нам даны ai квадратов со стороной 2ki. Квадрат разрешено поместить только в больший квадрат, при том никакие два квадрата не дожны перекрываться. Мы должны найти наименьшее p такое, что мы можем поместить все данные квадраты в квадрат со стороной 2p.

Решение

Допустим, что мы можем поместить все квадраты внутри квадрата со стороной 2p. Тогда можно разместить квадраты типа ki независимо друг от друга по сетке так, как показано на рисунке. Никакие два квадрата не будут перекрываться, так как 2x делит 2y, если x < y. Это значит, что мы можем найти наименьший квадрат, который вмещает все данные квадраты со стороной 2ki для каждого ki отдельно. Тогда ответ будет равняться стороне наибольшего такого квадрата.

Чтобы можно было разместить ai квадратов со стороной 2ki внутри квадрата со стороной 2s, должно выполнятся следующее равенство:

(2s)2 ≥ (2ki)2·ai
4s ≥ 4ki·ai
4s - ki ≥ ai

Тогда мы можем найти наменьшее s:

В частном случае, когда s = ki, s увеличиваем на 1.

Время: .

Память: O(1).

Реализация: C++, Java

Комментарий

Задачу также можно решить двоичным поиском по p. Однако, заметим что каждый квадрат со стороной 2k + 15 помещяет в себе любое данное количество квадратов со стороной, меньшей 2k, так как . Поэтому достаточно найти первый подходящий квадрат со стороной от 2max k + 1 до 2max k + 15.

Div II D / Div I B — Теплица

Задача

На прямой даны n точек, каждая одного типа от 1 до m. Мы можем раздеить прямую на m - 1 интервалов и переместить какое-то количество точек так, чтобы каждая точка типа i находилась бы внутри i-того интервала, которые пронумерованы от 1 до m слева направо. Нужно найти минимальное количество точек, которые нужно переместить.

Решение

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

В этой задаче достаточно было реализовать квадратичное решение. Считаем dp[i][j] — длина наидлиннейшей неубывающей последовательности на префиксе [1;i], где j — тип последнего элемента. Переход динамики:

Для лёгкой реализации, хватает завести один массив dp[j], и пропустить обработку второго случая.

Время: O(n2) / .

Память: O(n2) / O(n).

Реализация: C++

Комментарий

С этой задачей мы столкнулись во время работы над проектов, и суть проблемы лежит в размещении границ некоторых прямоугольных таблиц. Наша оригинальная реализация работает за O(nm).

Div II E / Div I C — Неисправный Поток

Задача

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

Решение

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

for all v from 2 to n-1
    f[v] := sum(flow(v,u))/2;
put source in queue
while queue is not empty
    v := pop(queue)
    for all edges (v, u)
        if (v, u) is not directed yet
            direct v -> u
            f[u] = f[u] - flow(v,u)
            if u not sink and f[u] = 0
                push(queue, u)

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

Время: O(n + m)

Память: O(n + m)

Реализация: C++, Java

Комментарий

Очевидное «простое» решение — запустить алгоритм нахождения максимального потока на том же графе, и получить ответ. Однако все такие решения сваливались на претесте #6.

269D - Максимальный водопад

Задача

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

Решение

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

События сканирующей являются отрезками. Когда встречается новый отрезок, мы хотим найти все такие нижние отрезки, на которые мы можем направить поток с этого отрезка. Такими могут быть только такие отрезки, чьи части находятся в сканирующей и перекрываются с данным отрезком. Затем мы итерируемся по всем таким частям p (найти первую такую часть — операция). Как мы узнаем, можно ли направить поток на p? Заметим, что если какой-то другой отрезок мешает этому, то в сканирующей должна существовать такая его часть q, которая видна с данного отрезка. А так как все три проекции этих отрезков перекрываются, то такая часть может быть только сразу слева или справа от p в двоичном дереве. Поэтому мы просто проверяем, не мешают ли изначальные отрезки таких двух частей рядом с p направить поток с данного отрезка на на изначальный отрезок p.

Затем мы вынимаем все такие части из сканирующей, и кладём новую часть, соответствующую данному отрезку. Если этот отрезок только частично перекрывал какую-то из частей в сканирующей, мы вставляем обратно остальную часть этой же самой части. Таких частей может быть только две — по одной на каждой стороне отрезка. Поэтому при обработке каждого отрезка вставляется не более 3 новых частей и размер сканирующей O(n). Каждая часть обрабатывается ровно один раз перед выниманием, поэтому суммарное время таких операций .

Когда мы узнаём, что можно направить поток по , сразу же обновляем наибольший возможный нисходящий поток из a:

fa = max(fa, min(fb, min(ra, rb) - max(la, lb)))

Когда обработаем верхний отрезок, ftop будет ответом.

Время:

Память: O(n)

Реализация: C++, Java

Комментарий

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

Div I E — Теория Струн

Задача

В этой задаче нам дан прямоугольник n × m. Каждая серединная точка едичного отрезка на сторонах соединена с другой точкой на другой стороне прямоугольника. Разрешено менять порядок рядов и столбцов, но отрезки должны оставаться прикреплёнными к своим точкам. Нужно найти такую перестановку рядов и столбцов, что никакие два отрезка не пересекаются, или же определить, что таковой не существует.

Решение

Всего есть 6 разных типов отрезков, соединяющих стороны:

  1. слева-наверх;
  2. сверху-направо;
  3. справа-вниз;
  4. снизу-налево;
  5. слева-направо;
  6. сверху-вниз;

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

Все справа-вверх отрезки должны находится в левом верхнем углу, и соединять точки (L,i) и (T,i), иначе они бы точно пересекались с какими-нибудь отрезками. Аналогично должны быть расположены все сверху-направо, справа-вниз, снизу-налево отрезки. Все сверху-вниз отрезки же должны быть параллельными. Также заметим, что количество слева-наверх отрезков должно быть равно количеству отрезков справа-вниз, а количество сверху-направо отрезков должно быть равно количеству отрезков снизу-налево. Из этого следует важное наблюдение: картинка прямоугольника после перестановок задана однозначно и может быть получена из входных данных, просто считая количество отрезков каждого типа.

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

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

В данный момент мы действительно находим циклы в обоих прямоугольниках. Есть только два типа циклов:

  1. (слева-наверх) (сверху-направо) (справа-вниз) (снизу-налево);
  2. остальные циклы

Можно легко проверить, равняются ли между собой множества циклов первого вида, так как длина таких циклов 4. Если они совпадают, то мы переставляем соответствующие ряды и столбцы в правильном порядке.

Как сравнить остальные циклы? Рассмотрим следующий пример:

Пусть разница количеств слева-наверх и слева-вниз отрезков равна i, а это число плюс количество сверху-вниз отрезков равно s. Если пронумеровать точки, как показано на рисунке, можно заметить, что кажая точка k сверху соединена с нижней точкой (сверху-направо отрезки продолжаются как соответствующие слева-вниз отрезки). Это можно описать перестановкой

Наши циклы соответствуют циклам перестановки, при том сверху-направо отрезки продолжаются в слева-вниз именно там, где в этой перестановке элемент цикла уменьшается. Известно, что перестановка такого типа состоит из циклов длины , то есть все циклы одинаковой длины. Обозначим каждый тип отрезка одним символом (на рисунке A, B, C). Тогда не только длина, но и строки, соответствующие циклам, тоже равны, но могут быть циклически сдвинуты, когда мы их нашли (именно здесь важно направление циклов). Кроме того, мы уже знаем, как выглядит такая строка из конечного прямоугольника. Поэтому нам нужно сравнить строки всех оставшихся циклов из данного прямоугольника с этой строкой, беря во внимание сдвиги как инвариант. Для каждой строки это можно сделать за линейное время, например, с помощью алгоритма Кнута-Морриса-Пратта. Когда для каждого цикла находим значение циклического сдвига, перестанавливаем ряды и столбцы по соответствию с конечным прямоугольником.

Время: O(n + m).

Память: O(n + m).

Реализация: C++, Java

Комментарий

По части реализации это настоящий гроб. Для нас ушло 5 часов, чтобы каждому написать решение. Ещё раз поздравления kelvin, в момент написания разбора единственному участнику, решившему эту задачу (и конечно же любому, кто сдаст эту сложную задачу в дорешке =) ).

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

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

Вот это разбор! Авторы, огромное вам спасибо за настолько подробный и качественный разбор.

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

I really wish that I didn't see problem like Div1 E , it made me sad.

I think it's harder than IOI problems.

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

It was a little hard to prove the needed algorithm for your problems but that was easy to code them , thanks .

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

Отличный разбор! Спасибо большое! Всегда бы так =)

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

That is true that the anti-maxflow pretest #6 kill my Dinic implementation, however the Push-Relabel of tsfn pass all the data sets, including the anti-maxflow pretest. 3053014

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

    Ahhh! This is much faster than our push-relabel implementation, but also very close to TL (1937 ms).

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

      Could we not solve the Flawed Flow problem just by finding Max flow in graph, and deciding edge direction by direction of flow(value of flow +ve or -ve) ?

      Yes your solution is easy and fast. But just asking about other possibility.

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

for div1 c, is there a proof that as long as you are not finished directing the graph, there will always be a vertex v where f[v]=0?

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

    note that wa have an acyclic graph in problem statement

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

      why does an acyclic graph guarantee that there will always be v s.t. f[v]=0? i.e. that all of v's incoming edges are known

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

        if there's no vertex v that f[v]=0 then we have an cycle in graph, because every vertex in graph have at least one incoming edge. (Consider longest simple path in remain graph, we know that head vertex in path has an incoming edge and the head of that edge is also in path).

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

gen , thanks for writing a very clear editorial!

For div1 B, if we just need to divide the line into m intervals where each interval must only have one type BUT type i can be within each of the m intervals(in contrast to must be inside interval i in the original problem), then how to solve it? For this variant, sample 1 would be:

input

3 2

2 1

1 2.0

1 3.100

output

0

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

    "He is free to place the borders, but in the end all of the i-th species plants must reside in i-th section from the left."

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

      He knows this. He just wonders how to solve it when we change the problem slightly.

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

Другое решение про водопады:

Будем двигаться сканлайном слева направо, события — отрезок открылся/закрылся, попутно в set'е храним все отрезки, которые открылись но ещё не закрылись, упорядоченые по оси y. Когда происходит событие, нужно для этого отрезка найти по ближайшему сверху и снизу. Для отрезка сверху сообщить, что в координате x (координата события) соответственно открывается/закрывается отрезок с таким-то номером, аналогично запомнить информацию для отрезка события о нижележащем. После этого у каждого отрезка будет свой список событий, по сути где может начинаться/заканчиваться водопад, и на какой отрезок он упадёт. Так вот, водопад может падать только если есть два подряд идущих события об одном отрезке. Осталось пробежаться по отрезкам снизу вверх и строить ответ. Но кода получается больше, чем у авторского.

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

For Magical Boxes, I ignored that the box can't fill itself. T-T

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

I wonder the relation of E and Planar graph.Maybe we can use planar embedding of the graph to solve it.Just kidding lol!

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

Почему вот этот код заходит: http://codeforces.com/contest/270/submission/3080881 А вот этот падает: http://codeforces.com/contest/270/submission/3080837 Отличия следующие: В проходящем коде: cin >> data[i] >> tmp; В падающем: scanf("%d %lf", &data[i], &tmp); Причём на локальной машине оба работают.

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

    Такой код тоже падает c MS C++ и вводом 1:

    #include <cstdio>
    
    using namespace std;
    
    int main()
    {
        double x;
    
        scanf("%lf", &x);
    }

    Возможно, это баг в компиляторе или стандартной библиотеке.

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

На задачу А див.1 можно было просто написать моделирование, просто пихая самые маленькие ящики в ящики, размеров в два раза больше.

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

Hello, guys. Can someone explain how can we solve Div1 B in O(NlogN)?

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

A point to note here is that the algorithm used for Div2 E / Div1 C is not a bfs. Though it proceeds like a bfs; it does not guarantee that a vertex is put in the queue when it is first observed contrary to bfs. Also we can use any data structure (not necessarily a queue) to store the vertices for which all incoming edges are known like stack, set, priority_queue, etc.

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

in Div II D / Div I B — Greenhouse Effect, just one question, what is the variabel x (or array x[n]) for? is that 'usefull'? Even the plants are ordered from their initial input