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

Автор AGrigorii, история, 6 лет назад, По-русски

982A - Row

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

982B - Bus of Characters

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

  1. Сортируем массив длин рядов по возрастанию
  2. Для каждого интроверта пишем номер очередного свободна ряда и добавляем его в стек
  3. Для каждого экстраверта пишем последнее число из стека и удаляем его оттуда

982C - Cut 'em all!

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

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

982D - Shark

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

982E - Billiard

Если симметрично отражать прямоугольник на плоскости относительно своих сторон, то новая траектория движения шара окажется куда проще. А именно — прямой. Одно из возможных решений такое:

  1. Если вектор направлен под углом в 90 градусов к осям, то пишем if-ы.
  2. Иначе поворачиваем поле таким образом, чтобы вектор удара стал (1, 1).
  3. Выписываем уравнение прямой движения шара:  – 1·x + 1·y + С = 0. Если подставим изначальное положение шара, то найдем коэффициент C.
  4. Заметим, что в бессконечно замощенной плоскости координаты любой лузы представимы в виде (k1·n, k2·m).
  5. Подставим координаты лузы в уравнение прямой шара. Получается диофантово уравнение A·k1 + B·k2 = C. Оно разрешимо в случае, если C | gcd(A, B). В противном случае решений нет.
  6. Из всех решений данного диофантово уравнения нас интересует наименьшее на положительной полуоси.
  7. По найденным k1, k2 легко получить координаты соответствующей им лузе
  8. Повернуть поле обратно, если требуется.

982F - The Meeting Place Cannot Be Changed

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

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

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

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

Теперь нужно отметить все дуги между возвратом-выходом с главного цикла. Для этого будем запускать dfs из всех вершин главного цикла и пытаться вернуться на главный цикл как можно дальше (расстояние измеряется по количеству вершин главного цикла между выходом и возвратом). Как было отмечено выше, циклы, выходя и возвращаясь, не могут перескакивать ответ. Значит все dfs'ы, стартующие между границами ответов, стремятся к какой-то вершине главного цикла, которая является граничной в дуге с возможными ответами. Значит если в одном dfs'е мы выбрали самую удалённую вершину из нескольких вариантов, то в другом dfs'е рассматриваемые варианты не поменяются ролями, и старая самая удалённая вершина так и останется самой удалённой среди тех же вариантов в новом dfs'е. Значит можно запускать все dfs'ы с общим массивом used, в котором кэшировать самую удалённую вершину.

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

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

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

waiting translation~

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

I have a slightly different solution for E. We notice that the movements along the X and Y axis are independent. Therefore, instead of solving a 2D problem, we have to solve two simultaneous 1D problems.

We notice that for the X dimension, if the ball first hits a margin of the table at time x_i (which will be either equal to x or to n - x, according to the direction of the X speed vector), then it will keep hitting the edges at times x_i + t * n, where t is a non-negative integer. We judge the same for Y. The solution of the problem is found when both axis hit an edge at the same time (therefore, a corner). So we need to solve x_i + t_x * n = y_i + t_y * m.

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

    Can you explain how to solve the last equation I am having hard time solving it

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

      It's a classic problem, Linear Diophantine Equation. You then have to bring the solutions to positives, you can check out my submission to see how I did that (there's probably multiple ways).

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

    This is a great way to solve it, thank you very much!

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

Hope that translation will come soon, I have been waiting for the solution that I can understand one day long.

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

I think D requires more explanations.

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

    D has very simple solution required sort O(nLog(n)) and linear O(n) operations:

    1) sort given array with indexes, i.e. sort b[] = pair(a[i], i ).

    2) i = 0 .. N-1, add b[i].second to set of intervals - it's required O(1) operation:

    Let Left[i] - indicated left index of interval which end point is i.

    Let Right[i] - indicated right index of interval which start point is i.

    so when add 'u' element to set of intervals, only required update L[u], R[u], Left[u-1] and Right[u+1].

    ``

    3) Let cur_i - number of intervals, cur_l - length of last interval, max_l - maximum length of interval's, max_i - number of such maximum intervals.

    ` if cur_i == max_i -- so all interval's have identical length.`

    See solution 38374571 (Note: This solution is not my own idea).

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

      please elaborate your approach!! Still not clear

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

        For example:

        We have 7 10 4 5 numbers indexes: 1 2 3 4

        1) build index pair array : (7, 1) (10, 2) (4, 3) (5, 4)

        2) sort (1) array : (4, 3) (5, 4) (7, 1) (10, 2)

        3) we have empty interval set: {}. or imagine no colored line: 0 0 0 0.

        4) take first element: (4,3) index is 3. to color line[ 3 ] position. line: 0 0 [ 1 ] 0 - number of intervals = 1. length of last interval = 1, number of longest intervals = 1. --> update answer.

        5) take second element: (5, 4) index is 4. to color line [ 4 ] : 0 0 [ 1 ] 1 -- as you see, left side of 4 also colored, so colored interval will be: 0 0 [ 1 1 ]. - number of intervals = 1 , length of last interval = 2. number of longest intervals = 1, -- update ans.

        6) take third element: (7,1) index is 1: to color line [1] : [ 1 ] 0 [ 1 1] -- number of intervals = 2, length of last interval = 1. number of longest intervals = 1 (think about).

        7) take last element : (10, 2) index is 2: to color line [ 2 ] : [ 1 ] 1 [ 1 1 ] -- as you see, left and right side also colored, need increase left side and right side, line will: [ 1 1 1 1] - number of intervals = 1. number of longest intervals = 1 --> update ans.

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

Is there anyway to sovle D using Tenary Search. As i did i tenaried the K,but i came into a problem that the graph may have the plain field where alot of K satisfied the answer, so how can we solve this or this way is just invalid ?

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

    You can't apply any searching algorithm, because there is no available convex or covariance function with k from 1 to inf.

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

Can we solve C using DP?

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

Can C be solved using DP?

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

    I think, To find the number nodes in a subtree of a node is a DP.
    Because we use previously computed results and don't repeat it !!
    Which is I guess DP, isn't it?
    Correct me if i am wrong. Or tell, if there is another interesting solution using DP or anything.

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

AGrigorii The tutorial/Editorial is not linked up with the problems.

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

waiting the code link of every problem.

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

I dont get why cant we put a person of left most and right most seats?

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

Can someone explain the question D alomg with the sample test cases?

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

The English contest doesn't link to the announcement or this editorial. I had to switch to Russian to find this blog. Please fix it, thanks.

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

for problem shark ,why can't we take k=1 every-time and hence all conditions are satisfied this way?

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

Can someone explain D problem more clearly and detailed please?

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

if ((double)clock()/CLOCKS_PER_SEC>0.95) break; Why this line is used in prpblem F??

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

can anyone explain.. why selecting any node as root gives the same number of even subtrees? what's the proof?