Editorial for COI '14 #1 Čvenk


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

In this task, we have to determine the minimum total number of steps necessary in order for all the tourists to meet in the same field of the labyrinth.

According to the image, it seems that the labyrinth is shaped like a tree, and if we set field (0, 0) as the root, field (x, y) has a depth of x+y. This isn't difficult to prove: The case where one of the coordinates is 0 is trivial (father of (x, 0) is (x-1, 0), symmetrical for y). Let's denote the lowest active bit of a positive integer x with lobit(x). Notice that, because x \mathbin\& y = 0, lobit(x) \ne lobit(y). Let's assume that lobit(x) < lobit(y) (the other case is symmetrical).

We can visualize it this way:

  x: ???????????0000...010...000
  y: ???????????1000...000...000

Let's observe numbers x-1 and y-1:

x-1: ???????????0000...001...111
y-1: ???????????0111...111...111

Now it is clear that (x-1) \mathbin\& y = 0 and x \mathbin\& (y-1) \ne 0, so the father of field (x, y) in the tree is field (x-1, y), which matches our expectations. If lobit(x) > lobit(y), the father is (x, y-1). Therefore, it really is a tree. It needs to be noted that something stronger holds. Specifically, for lobit(x) < lobit(y), (x-z) \mathbin\& y = 0 for z from [0, lobit(x)], the argument is similar as for x-1, and this will be useful later for quick calculation of the k^\text{th} ancestor.

The typical next step is to implement the function lca(x_1, y_1, x_2, y_2) that finds the lowest common ancestor of fields (x_1, y_1) and (x_2, y_2). First, we will implement an auxiliary function kth\_ancestor(x, y, k) that finds the k^\text{th} in line ancestor of field (x, y). We can implement it recursively:

kth_ancestor(x, y, k):
    if k == 0: return (x, y)
    if x == 0: return (x, y - k)
    if y == 0: return (x - k, y)
    if lobit(x) < lobit(y):
        return kth_ancestor(x - min(lobit(x), k), y, k - min(lobit(x), k))
    if lobit(x) > lobit(y):
        return kth_ancestor(x, y - min(lobit(y), k), k - min(lobit(y), k))

Using this function, we can implement the function lca using the classical algorithm of jumping on powers of 2, in other words, binary search.

From now on, we will denote the fields with letters, instead of coordinates.

Notice that when we have the function lca we can easily calculate the distance between two nodes a and b in the tree as depth(a) + depth(b) - 2 \times depth(lca(a, b)).

We are left with finding a node where the tourists will meet in. This is a typical tree problem and generally the idea is this: let's assume that we are located in node a. Let node b be the neighbour of a, let's observe the edge a \to b. Let V(a, b) be the number of nodes in the subtree seen from the side of node a (when we are looking at the edge between a and b, image!), and V(b, a) the same for node b. Then b is a better choice for the meeting if and only if V(b, a) > V(a, b). Since V(a, b) + V(b, a) = N, it follows V(b, a) > N/2. It is clear that node a is optimal only if for each of its neighbours b it holds V(b, a) \le N/2. The reader is left with making sure that this condition is sufficient too.

Let's get back to the tree from the task (remember, it's rooted). We will denote the number of tourists in the subtree of node a in our tree with tourists(a). Now we are looking for node a such that tourists(a) \ge N/2 (so that in the part of the tree above a there is no more than N/2 tourists) and tourists(b) \le N/2 for each child b of a. If we take an initial node, we can easily use binary search and the function kth\_ancestor to find the first ancestor a such that tourists(a) \ge N/2. If all of its children have less than or equal to N/2 tourists in their subtrees, we have found the solution. Checking the number of tourists in a subtree can be done in \mathcal O(N \log C) by examining for each node with a tourist if it's a descendant of the node we're considering (by calling the function kth\_ancestor with the depth difference). Given the fact that in the subtree of the optimal node there are at least N/2 tourists, we can randomly choose one of N nodes with tourists as the initial node for binary search. The expected number of initial nodes we will need to check is 2.

After we find the optimal node, we are left with summing up the distances of tourists to our node.

The complexity of function kth\_ancestor is \mathcal O(\log C), where C is the maximal value of coordinates of a field, so the complexity of finding the optimal node is \mathcal O(N \log^2 C), \log C for binary search and N \log C to check the node (and the expected number of tries is 2).

The complexity of function lca is \mathcal O(\log^2 C), \log C for binary search, \log C to call function kth\_ancestor. We have to call it N times in order to calculate all distances, so the complexity of this part, as well as the total algorithm complexity, is \mathcal O(N \log^2 C).


Comments

There are no comments at the moment.