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

Автор Gerald, 13 лет назад, По-русски
Для решения этой задачи достаточно посчитать для каждой буквы: ac - количество вхождений буквы c в первые две строки инпута, bc - количество вхождений буквы c в последнюю строку инпута. Ответ на задачу "YES", если для , иначе "NO".

Переберем "уровень" 0 ≤ i ≤ 106 , в который предположительно должен попасть камешек, попутно поддерживая наименьший номер квадратика на этом уровне. Далее понимаем, сколько на этом уровне квадратиков один или два. Далее одним или двумя (если на уровне два квадратика) ифами проверяем, попал или нет камешек в соответствующий квадратик, если попал выводим ответ. Если мы не нашли ни одного квадратика, в который попал камешек, выводим "-1".

Отсортируем пары (namei, ai) по возрастанию ai. Если существует такой индекс 0 ≤ i < n, что ai > i, тогда ответ "-1". Иначе ответ существует. Будем идти по массиву отсортированных пар слева направо, поддерживая вектор результата res. Пусть на текущей итерации hi = n - i, тогда текущего человека нужно поставить в текущий вектор на позицию ai. В C++ это можно сделать одной строчкой: res.insert(res.begin() + a[i], man);

Сгенерируем взвешенный ориентированный граф всевозможных переходов. Вершины графа - это важные точки на прямой Ox, т.е. точки 0, L, xi - pi, xi + di. Ребра графа - это возможные переходы, т.е. либо переход из точки xi - pi в точку xi + di, либо переход из вершины в соседние вершины (соседние, в том смысле что мы берем следующую и предыдущую важные точки на прямой). Веса у таких ребер соответственно pi + ti и xv + 1 - xv, xv - xv - 1. В переходах нужно учесть, что нельзя забегать за старт, просто не добавляя такие переходы.

Далее на этом графе нужно найти и вывести кратчайший путь из вершины 0 в L. Это можно сделать, например, алгоритмом Дейкстры для разреженных графов. 

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

В таком дереве всегда будет n - 1 ребро, поэтому если n - четное, ответ "-1".

Давайте удалим из данного нам графа все S-ребра. Пусть теперь в нем будет cnt компонент. Чтобы сделать редуцированный граф вновь связным, нужно добавить минимум cnt - 1 S-ребер, поэтому если cnt - 1 > (n - 1) / 2, ответ "-1". Найдем cnt - 1 S-ребер, которые обязательно придется добавить в граф, чтобы он стал связным, если cnt - 1 < (n - 1) / 2, то будем пытаться добавить в это множество ребер другие S-ребра, так чтобы не получилось цикла по S-ребрам. Все это нужно делать по аналогии с алгоритмом Краскала нахождения минимального по весу остова. Если мы смогли получить множество S-ребер из (n - 1) / 2 элементов, такое что в него входят обязательные cnt - 1 ребер и нет циклов по ребрам, тогда ответ существует. Теперь нужно добавить в это множество (n - 1) / 2 M-ребер так, чтобы получилось покрывающее дерево. Это нужно сделать также по аналогии с алгоритмом Краскала.

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

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

кстати, задача Е?

upd: нет, не она

»
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Вопрос по задаче Е, в ответе же может быть больше n-1 ребра, если еще добавлять петли? Или я что-то не так понял?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Нет, не может. Если есть петля, то существует 2 пути из вершины в себя:стоять на месте и идти по петле.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Идти по петле же не простой путь?
      • »
        »
        »
        »
        13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Написано должен быть ровно один простой, и не важно сколько не простых.
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
            Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится +11 Проголосовать: не нравится
              А как же пути вида 1-2-1-2?
              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                  Проголосовать: нравится +1 Проголосовать: не нравится
                О да, пожалуй, это еще один путь. Ну все равно это не отменяет правильного понимания условия. 
              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                  Проголосовать: нравится +5 Проголосовать: не нравится
                Я ошибся, везде в комментариях я имел ввиду конечно же третий семпл, а не второй. 
            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Ну это хорошо, что фразу ровно один простой путь вы понимаете именно так. Но было бы неплохо удостовериться, что незнакомые с условием люди поймут ее так же (в чем я сомневаюсь лично).  Я нашел как минимум два варианта как ее понять:
              1) из всех путей (соединяющих две вершины) ровно один должен быть простым (а значит, мы можем использовать и петли)
              2) должен существовать ровно один путь, и он должен быть простым (петли использовать не можем)
              Если бы не третий семпл, без клара бы не обошлось однозначно.
              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                а я, например, сразу понял условие как 1), и даже не думал о другом понимании. не имею привычки разбираться с семплом, если, как мне кажется, я понял условие
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Разве путь из вершины в саму себя считается простым? Судя по условию нет, т.к. в нём есть две одинаковые вершины.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится
        Смотрите семплы, они являются частью условия.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я думаю петли вообще можно было не учитывать, т.к. если их использовать - получается, что это тоже просто путь из вершины i в неё саму, а если так - то у всех вершин должны быть петли, чего в сэмплах нет.
    По-моему лучше было бы вообще исключить наличие петель из условия и тестов.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
ТАКУЮ ерунду я на С послал(АС кстати), что вообще...
Как я до такого простого решения не додумался! туплю..
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А у меня решение в В, не проверяющее попадание на границу в половине случаев прошло претесты...
    Сижу теперь, как дурак с А и С только...
»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
В чем заключается 19 тест к задаче В?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    можно же смотреть какой тест:
    Ввод
    5 -4 2
    Вывод
    0
    Ответ
    -1
»
13 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

спасибо за оперативный разбор

задача Е хорошая, но, имхо, условие не было полноценно понятным

UPD ну вот зачем, зачем добавлять в инпут петли, если их, по условию надо все равно выкидывать?!

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

Отсортируем пары (namei, ai) по возрастанию ai. Если существует такой индекс 0 ≤ i < n, что ai > i, тогда ответ "-1"

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

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

    Потому что если это выполняется, то для любого a[j] (j>i) это тоже выполняется(если числа в a[] различны), "сдвигать" массив a[] мы тоже не можешь, так как это не улучшит ситуацию.

    А если после a[i] идут равные ему, то сдвиг a[i] ничего не изменит.

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

Пусть на текущей итерации hi = n - i, тогда текущего человека нужно поставить в текущий вектор на позицию ai.


Текущий вектор... Я один ничего не понял? Может кто-то чуть подробнее объяснить как это работает и почему это правильно?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Заведем вектор q, куда будем складывать людей в порядке очереди. Т.к. высоты отсортированы по убыванию, то проходя по массиву, высота текущего элемента будет явно меньше предыдущих. Когда ai=0, мы просто складываем элементы  в вектор q в порядке убывания высоты (заметь, у них наибольшая высота из всех элементов). Из этого следует, что если положить в вектор q элемент на место ai, то впереди у него гарантированно будет ai элементов, больше него, что соответствует условию.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Кажется, я уловил идею. Спасибо!
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      По-моему проще для понимания так:
      • заметим, что можно обойтись числами [1..n] и каждое мы возьмём 1 раз
      • заведём структуру данных, из которой можно извлечь k-е по убыванию число с удалением его (можно и массив пометок просто) и запихаем в эту структуру все числа от 1 до n
      • отсортируем пары по неубыванию a[i]
      • идём от от n до 1 циклом и h[i] присваиваем a[i]+1 по убыванию число из тех, что ещё не было
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
double
»
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Гениально! Решение задачи B в четыре строчки 1023920
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

А ведь задача B не только как в разборе перебором решалось, можно было найти решение за константное время =)

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Не за линейное, а за константу
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    А ведь задача B не только как в разборе перебором решалось, можно было найти решение за O(1) =)
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      По-моему много людей решало за константу, хотя перебором написать программу было бы быстрее. Я тоже решал за О(1), но забыл одно условие, из-за чего меня похакали на предпоследней минуте :)
»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
It would be nice to see a proof why does such an algorithm work for problem E.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    It's easy to prove as well.
    If this algorithm outputs -1 then there are three ways:
    1) odd number of edges in the tree, that works correct
    2) () then there doesn't exist edges of first color that doesn't make a cycle
    3) You can't connect the graph with second type of edges, then you can't connect it at all, so it's correct
    So if output is -1, then answer doesn't exist.
    Why if output is not -1, then answer exists and correct?
    So you get cnt components, then you add cnt - 1 edges of second type, then you just add remaining second type edges (all counted as ), that all second type edges doesn't make a cycle.
    But you say there are the cycles that contains, two types of edges, when cycle appears you just remove one first type edge from the cycle. So the graph that you built is correct and it contains everything asked in the problem statement.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      This is not complete, there is also another situation when you output -1. Let's say: we added all M-edges and got a spanning tree (none of your 1), 2), 3) conditions applies), but there is still a possibility for the answer to be -1.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ah.. Yes
        I have to change 3)
        You can't connect graph with second type of edges or you can't get second type of edges that doesn't make a cycle.
        Then it's -1 and it's correct.
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          Ok, but it is not clear if the algorithm checks this condiction correctly. I mean it chooses some S-edges which make the M-forest into a spanning tree and then until there are less then (n-1)/2 s-edges it adds new s-edges in such a way that no s-cycle appears. But why the success of such a procedure doesn't depend on the chosen (at the beginning) s-edges? Etc., etc. It's not as obvious as you say.
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится
            OK, what you say it's mistake when answer exists, but algorithm doesn't find it. And it's 3). (it outputs -1)
            Firstly, if you can't connect the components, but the answer exists.
            So if you add all the s-edges, then the components will stay the same, so if you can't connect the graph, then you can't connect it at all.
            Secondly, if you have m-edges, that doesn't make a cycle, you certainly will find and add them, because you firstly connect components, it doesn't matter what edges to connect with, since it's matroid (there will always exist and edge, that doesn't make a cycle, if there's larger set of edges, that doesn't make a cycle)
            so you just add the edges one by one until there are  m-edges. so you get m-edges set and s-edges set, you can remove some edges from s-edges set to get the tree.
            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Ok, now it looks much better. The keyword here is "matroid". Thank you.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Подскажете, можно ли узнать 19 тест по задаче В? Могу ли я выставить свое решение в комментариях, чтобы пользователи нашли ошибку?
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
can someone explain solution for problem C ?
sorry, but it is very unclear from the tutorial
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    OK, lets do it in English.

    Make vector q, where we will place people in right order, that will be an answer. Sort input people by decreasing of a, give them height from n to 0, place them in array m and go from begining of this array to the end. When m[i].a=0, just place them in vector q by decreasing of h. Notice, that they are the highest people. It means, that if we place some element in vector q on place ai, before him will be ai people, higher than he, that meets the problem.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Я в С написал такую логически корректную ересь: сортируем пары по возрастанию ai, заполняем массив ответов единицами и для каждого ai выполняем следующее: в промежутке [0..i) увеличиваем на 1 все ответы, отличные от единицы, а также крайние правые ai - ai - 1 единиц. Если  ai - ai - 1 = 0, то ничего не увеличиваем :). Вот код, логика в нем соответствует описанию, но реализована несколько иначе.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо за разбор!  правда D, E слишком долго кодить! Идеи крутые :)
»
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Решается ли задача D жадным алгоритмом?
Я отсортировал все трамплины по увеличению x+d, затем пока позиция < L проверял, как добраться до точки xi + di быстрее - используя трамплин или без него. Из-за неправильного условия решение не прошло 7 претест. Прошло бы оно системное тестирование?
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

"Мсье знает толк в извращениях" (с) - это о моем решении задачи D

Ну почему я не догадался построить граф? А вместо этого выдумал какую-то дикую фигню с эмуляцией движения слева направо и с помощью дерева отрезков справа налево. Я раз 5 переписывал решение, причем восстановление пути появилось только в третей версии, когда я наконец нашел ответ :) Прежде чем писать, надо хорошо подумать, это сэкономит время, а не потратит. В B тупой баг - забыл  унарный  минус. Хорошо хоть раунд для меня нерейтинговый.

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В задаче E Большая чистка у меня прошло решение с наихудшей сложностью n^3. Я начал его писать около часа ночи, когда был искренне убежден, что 10^3=100 ;)  Дописал только утром, и оно прошло. Мое решение должно было умереть на случае, когда все домики соединены длрожками и Дед Мороз хочет их чистить один.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А как решалась бы С, если надо было бы найти решение с минимальное суммой h[i]?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я почти полностью уверен, что мое решение, описанное несколькими постами выше, выдает ответ как раз с минимальной суммой. Попробуйте доказать или опровергнуть, если Вам интересно :).
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
There are n - 1 edges in this tree, because of it if n is even then the answer is "-1".
That would normally be correct, but here we can have roads that start and end at the same hut, so we can add such a road without changing the connectivity, can't we?
2 2
1 2 S
1 1 M
For this case, isn't the solution to clear both roads?
  • »
    »
    13 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    "between any two huts should exist exactly one simple path along the cleared roads". That case results in 2 paths from 1 to 2. Hence, we can't clear roads which connect the same hut.

    UPD: I misunderstood it. Your opinion seems correct based on the problem statement.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I think, there is a path 1-1 which is not simple, therefore answer is -1.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      There are always paths that are not simple: 1-2-1. Edges are bidirectional
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        The problem statement states that there is exactly 1 simple path. 1-2-1 is not simple so we don't need to count it.
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ye, that was my point. 1-2-1 and 1-1 are not simple paths so they do _not_ invalidate the conditions.

          Either the author of the problem meant to say something else or the official solution is just wrong. I am betting on the second possibility.
          When I read that you can have a road starting and ending at the same hut, I was sure that this was added just to make it a little more tricky. Otherwise, what's the point?
          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            I think the roads which begin and end in the same hut are useful to adjust one nearly right answer to a right one.

            for example, if I got S=10 M=9, and one road 2->2 is M, I can choose this road so that S=M=10.

            between any two huts should exist exactly one simple path along the cleared roads

            and the rule above is satisfied, too. because 2->2 is never used, for when it's used nd 2 appeared twice. so whether to choose 2->2 is not important.

            To conclude, the solution for problem E is wrong || the problem statement needs change.

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

все задачи понял, кроме 3. поясните дураку, что и как... не врубаюсь

  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    • заметим, что можно обойтись числами [1..n] и каждое мы возьмём 1 раз
    • заведём структуру данных, из которой можно извлечь k-е по убыванию число с удалением его (можно и массив пометок просто) и запихаем в эту структуру все числа от 1 до n
    • отсортируем пары по неубыванию a[i]
    • идём от от n до 1 циклом и h[i] присваиваем (a[i]+1) по убыванию число из тех, что ещё не использовано как h[i]
  • Код
  • Например a[] = 0 0 1 1 2:
    1. 1 2 3 4 5
      _ _ _ _ 3
      3 - (a[5]+1 == 3-е) число из имеющихся
    2. 1 2 3 4 5
      _ _ _ 4 3
      4 - 2-е из оставшихся
    3. 1 2 3 4 5
      _ _ 2 4 3
    4. 1 2 3 4 5
      _ 5 2 4 3
    5. 1 2 3 4 5
      1 5 2 4 3
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

На С можно было спокойно поставить ограничение 105 - вот решение за nlogn.

UPD. Ошибочка: решение работает за nlogn, я не учел сложность сортировки.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Можно, но зачем?
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Лично мне было довольно интересно устранить квадрат, используя из структур данных только банальный стек.
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Подскажите пожалуйста, какая итоговая сложность получилась в E, просто я решил совсем по-другому и у меня N^2 + M, и работает оно быстрее всех уже сданных

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

    В решении Е из разбора итоговая сложность как у алгоритма Крускала, т.е. O(m * log(m)), что вполне может работать медленнее Вашего решения.