"Пятёрка за неделю 22" - dfs or bfs ?!

 Задачи пятёрки

1.  A. Пастбищa
2.  B. Графическая маска
3.  C. Электрические провода
4.  D. Сортирующая игра
5.  E. Путь короля
   

Пастбищa

   By Jeffrey Wang: This problem, known as the "minimum dominating set problem" in a tree, has a nice greedy solution. Note that the graph in the problem is indeed a tree because it has V-1 edges. We say a vertex is dominated by a set of vertices if it is either in the set or adjacent to a vertex in the set. The algorithm is as follows:

1. Keep track of a set of vertices S.
2. Root the tree at an arbitrary node.
3. Visit the vertices of the tree with a postorder traversal.
4. At each vertex, if it is not dominated by S, add it and all of its neighbors to S.
5. Once the traversal is done, visit the vertices in S in the reverse order that they were added.
6. At each vertex, if S is still a dominating set when the vertex is removed, then do so.

   The vertices left in S form a minimum dominating set. For a proof of why this works, see here.

   Note that the running time of this algorithm is very good, O(N), since each vertex is visited once in the postorder traversal and each vertex is added to S at most once. Checking whether a vertex can be removed can also be done efficiently by keeping track of how many vertices in S it is adjacent to. An implementation of this algorithm is shown below.

   USA's Michael Cohen writes: There is actually another simple O(N) solution to this problem. The problem states that every vertex has a tower or is adjacent to a vertex with a tower; since the graph is a tree (it is connected and has N-1 edges) this is equivalent to the statement that for any vertex there is a tower on that vertex, its parent, or one of its children.

   If the tree is divided into subtrees, the only connections that exists in the tree as a whole but not the subtrees are those between the root of the tree and the roots of the subtrees. This means that only the roots of the subtrees need to be considered when merging subtrees into the tree as a whole. By this logic, there are 3 possible types of valid subtrees:

• Subtrees without a tower on their root or any of its immediate children. These subtrees are only valid if their parent has a tower on its root.
• Subtrees without a tower on their root but with a tower on at least one immediate child. These subtrees are always valid, but do not give tower coverage to their parent.
• Subtrees with a tower on their root. These subtrees are always valid and are sufficient to cover their parent as well.

   If we know for each subtree the overall smallest number of towers to make that subtree valid, the smallest number of towers to make it valid and of type 2 or type 3, and the smallest number of towers to make it a valid type 3 tower, we can then generate these numbers for the whole tree. The problem can then be solved by recursively subdividing the tree (a valid entire tree is a valid subtree of type 2 or 3), and since each vertex and each edge will be processed only one, it is linear time.

Графическая маска

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

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

Электрические провода

   Построим матрицу смежности графа m. Подсчитаем в переменной Edges общее количество имеющихся проводов (ребер графа): для этого следует подсчитать общее число единиц в массиве m и поделить его на 2 (каждое ребро будет подсчитано дважды, так как имеющийся граф является неориентированным).

   Каждая вершина, подключенная к наружной сети, вместе с вершинами, связанными с ней (даже не напрямую), образуют отдельную компоненту связности. При помощи поиска в глубину выделим эти компоненты. Очевидно, что граф распадется на множество компонент, каждая из которых содержит одну вершину из gridConnections, а также останется некоторое множество вершин, не входящее ни в одну из компонент. Пусть последнее множество содержит LeftVertex вершин. Между вершинами, входящими в разные компоненты связности, провода протягивать нельзя, так как произойдет замыкание. Между двумя вершинами, входящими в одну компоненту, можно добавить провод, если только он не был между ними изначально. Между любыми двумя из оставшихся LeftVertex вершин можно добавить провод. Для максимизации общего числа проводов множество из LeftVertex вершин необходимо присоединить к той компоненте связности, которая имеет наибольшее число вершин. В переменной MaxConnComp будем вычислять величину наибольшей компоненты связности. При помощи глобальной переменной Vertex в функции dfs будем подсчитывать число вершин, входящих в текущую компоненту связности. Если текущая компонента связности содержит Vertex вершин, то максимум она может содержать Vertex·(Vertex–1)/2 ребер (полный граф). В переменной res вычисляем наибольшее число ребер, которое может содержаться во всех компонентах, порожденных вершинами из gridConnections. Присоединяем проводами множество из  LeftVertex вершин к наибольшей компоненте связности: между LeftVertex вершинами можно провести LeftVertex·(LeftVertex–1)/2 ребер, между LeftVertex вершинами множества оставшихся ребер и MaxConnComp вершинами из наибольшей компоненты связности можно провести MaxConnComp·LeftVertex ребер. Остается из общего числа ребер res вычесть количество уже имеющихся Edges, чтобы найти максимальное число проводов, которое можно добавить.

Сортирующая игра

   Задачу будем решать при помощи поиска в ширину. Сохраним исходную перестановку в массиве board и занесем в очередь поиска в ширину. После извлечения очередной перестановки из очереди будем перебирать в ней все возможные k последовательно стоящих чисел, обращать их и класть в очередь.

Путь короля

   Рассмотрим два варианта движения короля:

1. Король направляется к пешке А несмотря на положение пешки В и съедает ее;
2. Король направляется к пешке В, съедает ее и потом двигается к пешке А.

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

   В поля, находящиеся под ударом пешек, изначально поставим значения 1000. Таким образом при поиске в ширину король на них не зайдет. Начальные положения короля и двух пешек занесем соответственно в переменные (kx, ky), (pax, pay), (pbx, pby). Запустим bfs(kx, ky). Занесем в переменные a и b наименьшее число ходов, которыми можно добраться до пешки А и В соответственно: a=m[pax][pay], b=m[pbx][pby]. Если пешка В сбивается, то следует запустить bfs(pbx, pby), найдя таким образом кратчайший путь от пешки В до А. Добавим к b значение m[pax][pay] после второго вызова bfs. Таким образом в a содержится длина кратчайшего пути короля до достижения цели без сбивания пешки В, а в b – со сбиванием. Вычисляем меньшее значение среди a и b.

   Второй подход: задача также решается поиском в ширину (алгоритм волны), но за один проход. Для удобства реализации удобно рассматривать массив 10×10, где внешние строки и столбцы служат для уменьшения проверок очередного допустимого хода. Этот подход описывался ранее в разборах одной из предыдущих "Пятёрок за неделю", а также при разборе задач городской олимпиады в г. Бердичеве в 2010 году.