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

Codeforces Beta Round #37 (Разбор задач)
Автор vepifanov, 13 лет назад, По-русски

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

B. Компьютерная игра
Ограничения в задаче позволяли решать её следующим образом: будем хранить текущее количество здоровья у босса, и суммарный наносимый урон по нему. На очередном шаге выберем из еще не использованных свитков такой, который можно использовать на текущей секунде. Из всех таких, найдем свиток, который наносит больше всего урона, и применим его. Если в какой-то момент мы не смогли использовать ни один из свитков, и суммарный урон не превышает регенерацию, то выводим, что ответа не существует. Иначе продолжаем итерировать алгоритм, пока количество жизни босса не станет неотрицательным.

C. Древнеберляндский язык
Одно из самых простых для понимания решений в данной задаче выглядит так: отсортируем строки по возрастанию длины, при этом запомнив их номер в исходном списке. Будем последовательно строить наш набор, начиная с самых коротких строк: строками длины один могут быть только строки “0” и “1”. Если количество строк длины один в наборе больше двух, следовательно, ответа не существует. Добавим нужное количество строк длины один в ответ на свои места (для этого мы запомнили их номера), и удалим из текущего списка. Затем посмотрим на строки длины два: каждую из оставшихся строк длины 1 можно продолжить двумя способами (дописав к каждому из них символы 0 и 1). Добавим нужное количество строк длины два в наш набор, и снова увеличим длину оставшихся строк на единицу. Будем продолжать этот процесс до тех пор, пока не составим набор целиком. Можно заметить, что если в какой-то момент число допустимых строк превысило количество оставшихся, то лишние строки можно проигнорировать и таким образом время работы составит O(N * максимальную длину из входного набора).

 

D. Расписание занятий

Эта задача решается методом динамического программирования:

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

 

E. Испытание для вождя

Сперва по данной раскраске построим следующий граф: каждой клетке сопоставим вершину того же цвета, что и сама клетка. Между соседними клетками проведем ребро веса 0, если клетки одного цвета, и веса 1, если разного. Теперь для каждой клетки посчитаем кратчайшее расстояния из нее, до самой удаленной черной клетки (обозначим его D). Нетрудно видеть, что можно построить последовательность из D + 1 перекрашивания приводящую к искомой раскраске:

  • на первом шаге покрасим все клетки на расстоянии меньше либо равном D в черный цвет
  • на втором шаге покрасим все клетки на расстоянии меньше либо равном D - 1 в белый цвет
  • и т. д.

Из всех клеток, выберем ту, для которой это расстояние минимально, и это расстояние увеличенное на единицу будет ответом на задачу.

Разбор задач Codeforces Beta Round 37
  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо за разбор.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Почему в E раскраска, построенная по описанному алгоритму, будет оптимальной?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Доказательство довольно громоздкое, но вкратце выглядит примерно так:

    Сперва сожмем все вершины между которыми расстояние равно нулю в одну компоненту (получим граф компонент связности).
    Заметим, что если мы перекрашиваем какую-то клетку, то можно перекрасить и всю её компоненту, так как в итоге раскраска не изменится.

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

    Поэтому один из оптимальных ответов будет иметь вид описанный в разборе. Если в качестве начальной вершины мы возьмем клетку, лежащую в последнем перекрашивании этого оптимального ответа, алгоритм найдет решению не хуже чем оптимальное.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
In the tutorial of Problem E, the way to paint the cells is brilliant. Meanwhile finding the cell to minimize D is just to optimize the solution in this way.
But how to prove that this method you paint the cells is the best? Thank you very much.
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
    The proof is in short looks like this:

    First, compress all vertices between which distance is equal to zero in one component (get graph of connected components).
    Note that if we repaint some cell, it can be repainted and all its component, as a result coloring will not change.

    1) we can prove that any coloring can be reduced to a form such that each subsequent repainting is a subset of the previous one.
    2) the last repainting will consist of exactly one vertex (possibly the whole monochromatic connected region of the original board).

    Therefore, one of the best answers will be of the form described in the review. If as the initial vertex, we take a cell, lying in the last repainting of the optimal sequence, the algorithm finds the solution not worse than optimal.
    Прослушать
    На латинице

    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I tried to simulate exactly the algorithm described for Problem C, but it obviously times out since it requires a huge memory space. Can anybody tell me how do i optimize it? I've posted my solution here -
http://ideone.com/il8Do
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Хотелось бы чтобы отписались люди, сдавшие эту задачу и имеющие альтернативные решения.
    → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Well, my solution doesn't need any memory at all. Process the lengths of the words in increasing order and try to find lexicographically smallest word at each step. Suppose s is the last word written out, and its length is k. Then all strings that have length k and are lexicographically not larger than s, are 'bad' (each of them has a prefix that is already written out). So, to find out the k-prefix of the next word we need to increase s by 1 (as a binary number). Obviously, if s consists of 1's it's impossible, since we will get a word of length k+1. Now we need to find lexicographically smallest encoding of the next word. To do that, just add zeros to the increased value of s.
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    This is solution of problem C from tutorial:
    http://ideone.com/lHtSZ
    → Ответить