Edvard's blog

Codeforces Beta Round #33. Разбор D
By Edvard, 14 years ago, translation, In English

Analysis for problem "D. Knights".

Denote the number of fences surrounding the control point number i through cnti. Also denote cntij - the number of fences surrounding point i and point j. Then the answer to the query (i, j) is cnti + cntj - cntij. Clearly, that we can calculate all the values cnti with time O(n * m). The problem is the fast computation of the values cntij. And then suggests two solutions: a simple and not very much. Simple is as follows: create for every point i a bitset, j-th is equal to 1 if the j-th fence surrounds the point number i. Then, obviously cntij = count(zi & zj), where count(a) - the number of ones in bitset a. Now another solution. Add another fence with a center at (0, 0) and infinite radius. We construct a graph whose vertices are the fences as follows: we draw an arc from i to j, if the i-th fence is a fence with the minimum radius surrounding the fence number j. Obviously we get a directed tree rooted at the fence of infinite radius. Also, for each control point will find idxi - number of the fence with minimum radius  surrounding the i-th control point. Then cntij = distij + distji, where distij - distance from vertex i to the lowest common ancestor of verticex i ans j. With the implementation problems should not arise, because in the first solution could write bitset himself or use the standard bitset from STL (for those who write in C++), while in the second solution we could preprocess all the lca with time O(n2).
  • Vote: I like it
  • +10
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    sorry, for pre-process should be O(NM)
    and total complexity O(NM+QM)
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      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)).
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        yea.. for sure LCA is better but I just give some other options to solve D
        → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.net/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)

→ Reply