Автор RussianCodeCup, история, 8 лет назад, По-русски
A. Прямоугольник и квадраты

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

Число n несложно вычислить. Оно равно частному A·B и C2 округленному либо вверх, либо вниз. Осталось выбрать из этих ответов наиболее выгодный и не забыть учесть, что нужно использовать хотя бы один квадрат C × C.

B. Нули и единицы

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

Из этого факта следует простой жадный алгоритм: будем идти по первой строке слева направо и поддерживать ее текущее состояние. Если, находясь в i-м символе, s1[i] ≠ s2[i], тогда следует применить инверсию к символам i, i + 1 первой строки. Если в конце s1[n] ≠ s2[n], то нужной последовательности инверсий не существует и ответ равен  - 1.

C. Новая трасса

Это задача на конструктивное построение примера.

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

Чтобы получить ровно k нужно взять 2l отрезков, что l(l - 1) ≥ 2k > (l - 1)(l - 2), и построить максимальный пример, правда, возможно, заранее завершив последний отрезок. Оставшиеся же n - 2l отрезков добавим в начало трассы, разместив вокруг по спирали. Пример приведён на рисунке при n = 17 и k = 9.

Ограничение на k взято не просто так. Это максимальное число пересечений при фиксированном n. Желающие могут доказать это самостоятельно, подсказка: рассмотрите число пересечений пары отрезков n и n - 1 с парами n - 3 и n - 4, n - 5 и n - 6, ..., 2 и 1 (или просто отрезка 1, если n — чётное).

D. Дерево

Сделаем дерево взвешенным и изначально установим у всех ребер вес 1. Теперь заметим, что если вместо удаления вершины изменять на 0 вес ребра, которое из нее идет в ее родителя, то ответ на запрос на поиск расстояния будет равен расстоянию между вершинами из запроса по взвешенным ребрам в исходном дереве.

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

Тогда расстояние между вершинами можно найти так: dab = da + db - 2·dlca, где lca — это наименьший общий предок a и b, а dv — это расстояние от корня до v.

E. Варвары

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

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

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

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

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

I kinda don't agree with "This way the time for such BFS would be proportional to the size of the smaller component.". It is not explained how we run them in parallel in details, but since sizes of components are mentioned I suspect authors meant alternately doing "take vertex v from on of queues and process its neighbors". This approach is O(n2), because that vertex can have O(n) neighbours and indeed on a star graph it runs in such complexity. I processed edges one by one which ensures it works fast enough, but is a bit tricker to implement. Very standard problem.

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

    Another nice way for that,

    https://www.hackerrank.com/contests/101hack37/challenges/tree-splitting/editorial

    bool bdfs(int v, int from, int &rem) {
      --rem;
      if (rem < 0)
        return false;
    
      for (int to : g[v]) {
        if (to != from)
          bdfs(to, v, rem);
        if (rem < 0)
          return false;
      }
    
      return true;
    }
    
    int getSmallest(int u, int v) { // u and v in diff components
      int k = 1;
      while (true) {
        int temp;
        int ua = bdfs(u, 0, temp = k);
        int va = bdfs(v, 0, temp = k);
        if (ua)
          return u;
        if (va)
          return v;
        k *= 2;
      }
    }
    

    I don't know it's popular but I learnt it recently and I think it's more simpler than parallel bfs.

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

      Nice trick :). However it take some guts to initialize reference with "temp = k" :D