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

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

Итак, начнём разбор.

219A - k-String

Давайте для каждой буквы l посчитаем, сколько раз она встретилась в строке --- массив c[l]. Подсчет осуществляется примерно так: c[s[i]]++. Если количество вхождений какой-то буквы не кратно k, то мы уже сразу понимаем, что составить нужную нам строку невозможно. Теперь построим строку p: добавим в неё букв 'a', букв 'b', и так далее. Выведем полученную строку k раз.

219B - Special Offer! Super Price 999 Bourles!

Переберем количество девяток на конце числа от 1 до 18. Пусть эта величина равна k. В таком случае максимальное число не превосходящее заданное p можно получить так:

  • сотрем последние k цифр числа x:  = p / 10k
  • добавим справа k девяток y:  = x·10k + 10k - 1
  • если значение y больше p, то уменьшим число x (то, что идет до k девяток) на 1 и к результату допишем k девяток y:  = (x - 1)·10k + 10k - 1

Если получившееся y >  = p - d, то обновим ответ значением k.

219C - Color Stripe

Разберём 2 два случая:

  1. k равно 2. Тогда нам подходят только две строки — чередующиеся буквы 'A' и 'B'. Выбираем из них тот, который требует меньшего числа перекрасок.
  2. k больше 2. Возьмем самый левый блок из одинаковых букв. Пусть его длина равна k, тогда надо не менее k / 2 перекрашиваний, чтобы избавиться от соседних одинаковых клеток в этом блоке. Если k нечетно, то можно каждую вторую клетку в блоке перекрасить в любой из цветов, отличных от цвета блока. Если k четно, то можно делать тоже самое, но аккуратнее выбрать цвет: он должен отличаться не только от цвета блока, но и от цвета следующей клетки за блоком. Это всегда возможно сделать, так как количество цветов больше 2.

219D - Choosing Capital for Treeland

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

В задаче были достаточно большие ограничения, поэтому нельзя было просто посчитать все эти значения n обходами в глубину. Авторское решение запускает только два обхода в глубину. Первым обходом в глубину посчитаем ответ для города номер 1. Заметим, что если посчитан ответ для вершины x, то ответ для вершины y, которая соединена с x, можно посчитать за O(1). А именно, ans(y) = ans(x) - direction(x, y) + (1 - direction(x, y)), где direction(x, y) — равно 1, если ребро (x, y) ориентировано не так как во входных данных, и равно 0, иначе.

Пользуясь описанным фактом, можно посчитать все значения ans(v) одним обходом, зная ans(1).

Итоговая ассимптотика решения O(n).

219E - Parking Lot

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

В языке C++, авторское решение использовало set <pair<int,int>> и map <int, set<int>>. Set отрезков и Map из длины отрезка в набор отрезков с заданной длиной. Операция поиска больше либо равного элемента в этих структурах называется lower_bound.

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

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

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

Итоговая сложность решения O(m log n)

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

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

спасибо) хороший контест)

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

А ведь контест и правда отличный) Спасибо авторам) Очень понравилась Д)

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

Я на Д для каждого ребра добавлял по единичке для всех вершин либо в поддереве, либо во всем остальном графе, в зависимости от направления ребра. O(NlogN), правда...:)

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

В C можно было написать двумерную динамику. Где dp[i][j] — минимальное количество перекрашиваний в полоске длины i, оканчивающейся на символ j.
Сложность O(n*k^2). Правда заходит на грани TL :)

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

    Ну можно заметить, что нам из предыдущего столбца нужен минимум только, а если минимум в той же букве что и текущая, то второй минимум, а это за линию предпосчитывать можно, итого O(n*k). 2054589

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

      Я считал минимум на префиксе и минимум на суффиксе. То есть для j-го символа брал минимум из префикса длины j — 1 и суффикса, начинающегося в позиции j + 1. 2059006. Некоторые моменты, конечно, можно сделать попроще.

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

Если я правильно понял пояснение к задаче про цены, то там опечатка. Из пояснения видно, что к — максимальное количество 9 на конце и оно же выводится в ответ "обновим ответ значением k", но в ответ требуется y. Поправьте меня если я не прав.

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

В задаче D:

Итоговая ассимптотика решения O(n).

Асимптотика должна быть O(N log N) из-за сортировки ответа, разве нет? (Опечатка в тексте — асимптотика с одним 'с' )

P.S. Вот я неудачник, у меня она упала как раз из-за того, что забыл sort в конце. И кроме того, мой текущий рейтинг — 1699.

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

    Для поиска минимума в массиве изобретён более эффективный алгоритм. Почитайте Кормена.

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

      "Во вторую строку выведите все возможные способы выбрать столицу — последовательность номеров городов в порядке возрастания."

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

        Для сортировки натуральных чисел от 1 до n изобретён более эффективный алгоритм. Почитайте Кормена.

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

          Уговорил. Читать Кормена вовсе не обязательно.

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

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

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

Классный контест! Мне очень понравился! Очень интересно было, когда у многих (да и у меня тоже) на системном тестировании выпала третья задачка (нужно было просто еще немного подумать).

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

    Кстати, это был личный контест, а не командный :)

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

      Вопрос по задаче D: объясните, пожалуйста, как поиском в глубину из 1-й вершины найти ответ для этой вершины?

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

        Ответ для нее равен количеству ребер, которые во время обхода проходились не в том направлении, в котором они заданы в ориентированном графе.

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

          То есть, я должен делать обход в неориентированном графе и запоминать все ребра по которым я прохожу?

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

            В неоринентированном графе, да. Давайте для каждой вершины посчитаем величину "количество ребер, идущих не в том направлении в поддереве вершины". Тогда ответ для листьев равен 0, для остальных вершин — сумма по всем сыновьям + количество ребер, идущих в сыновей и направленных не в ту сторону.

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

            Их количество

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

            Вы идете как по неориентированному ребру, но, если вы вдруг пошли по ребру не в том направлении, то это ребро надо перенаправить, то есть к ответу прибавляется 1. И dfs возвращает, собственно, ответ для поддерева. Что вы имеете в виду под "запоминать все ребра"?

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

А кто может подсказать способ решение задачи E на Pascal. Какие структуры использовать?