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

Codeforces Beta Round #33. Разбор D
Автор Edvard, 14 лет назад, По-русски

Разбор задачи "D. Рыцари".

Обозначим количество заборов окружающих опорную точку номер i через cnti. Также обозначим через cntij - количество заборов окружающих и точку i, и точку j. Тогда ответ для запроса (i, j) равен cnti + cntj - cntij. Понятно, что мы можем вычислить все значения cnti за время O(n * m). Проблема в быстром вычислении величины cntij. И тут предполагалось два решения: простое и не очень. Простое заключается в следующем: заведём для каждой точки i битсет, j-й бит которого равен 1 если j-й забор окружает точку номер i. Тогда очевидно cntij = count(zi & zj), где count(a) - количество единичек в битсете a. Теперь другое решение. Добавим ещё один забор с центром в (0, 0) и бесконечного радиуса. Построим граф вершинами которого являются заборы следующим образом: проведём дугу из i в j, если i-й забор это забор минимального радиуса окружающий забор номер j. Очевидно мы получим ориентированное дерево с корнем в заборе бесконечного радиуса. Также для каждой опорной точки найдём idxi - номер забора минимального радиуса окружающего i-ю опорную точку. Тогда cntij = distij + distji, где distij - расстояние от вершины i до наименьшего общего предка вершин i и j. С реализацией проблем не должно было возникнуть, т.к. в первом решении можно было либо самому написать битсет, либо воспользоваться стандартным битсетом (для тех кто пишет на С++), а во втором можно было предподсчитать все lca за O(n2).

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

14 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Пользуясь случаем, спасибо вашей команде за контест.
Второе решение аналогично моему. Но все-таки что-то там не так, на мой взгляд, с формулой (в частности с индексами) для расстояний между LCA и самими вершинами. 
Там вроде если считать просто расстояние, то max(D1 + D2 - 2, 0), где D1 - от LCA до первой вершины количество ребер, D2 - от LCA до второй.
Ну и вот все-таки не понял, зачем предпосчитывать все lca за O(N2), если запросов максимум 105, а пар точек для запросов будет 106...
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    С формулой всё в порядке. Например если взять такое дерево: (1, 2), (1, 3), то расстояние между 2 и 3 равно 2, а между 1 и 2 равно 1. Как раз количество рёбер на пути из одной в другую.
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Все, я понял, в чем идея предподсчета. Извиняюсь, затупил. Если так подумать, то logN ~ 10, а K = 105, N2 ~ KlogN ~ 106. Существенной разницы нет.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
The easiest solution but slowest is:
pre-process the relation between central points and circles(inside/outside a circle) O(N2).
then answer the query in O(M), given 2 points, check which circles contain exactly 1 point outside the circle and 1 point inside the circle.
Total Complexity: O(N2 + QM) which is still ok for 2 sec
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    sorry, for pre-process should be O(NM)
    and total complexity O(NM+QM)
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      I think you may not even need the pre-processing. The complexity can be O(QM). (although there's a risk of exceeding the time limit for calculating too many multiplications).

      For the second approach, we can find LCAs for all queries in O(Q), using Tarjan's offline algorithm. Storing the height of each node, we can compute the length from the LCA to each node. The complexity to answer queries is O(M + Q). Hence we can increase Q to be bigger than the problem statement (of course, we first need to build the tree hierarchy and find the enclosing circle for each knight position in O(NM + M^2)).
      → Ответить
14 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
У самого решение с lca. Сколько комментариев не читал, нигде не видел простой идеи: после формирования дерева просто расчитать расстояния между всеми вершинами N раз прогнав dfs, потом их выводить. По времени тоже получается O(N2)
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да заметно проще и понятней. Чёт даже в голову не пришло. Подумал lca и сразу написал
    → Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

For each query (i, j), count the number of circles such that exactly one of control center i or control center j is inside the circle, and that's the answer.

https://codeforces.com/contest/33/submission/46096711

Why?

If both i and j are within a circle, there is no need to go over the fence. If they are both outside, there is no need. If exactly one of them is outside, they definitely need to go over that fence. O(MK)

→ Ответить