# Solution outlines PO-SOI 1

## Och

Consider the following graph: each horse gets its own node and each comparison will be an edge. To handle = comparisons, we will merge all nodes that are equal into one mega-node. Because the measurements are consistent, the new graph will necessarily be a DAG.

The only nodes whose value we can be sure of are those that lie on a path of length $S$. We will compute 2 dps: one that tells us the longest path to each node, from[u], and one that tells us the longest path to the node. All the ones that have from[u]+to[u]+1==$S$ will be uniquely determined by to[u]. (Up to some degree of off-by-one errors)

## Gott nytt år!

First, one can realize that the field is a tree rooted at $(0,0)$. Further, the depth of cell $(x,y)$ is $x+y$. Even further, it turns out that we can compute "which node do we end up on if we go up to our parent k times" in log time. Let $lo(u)$ denote the index of the lowest set bit of a binary number. For example, $lo(1100)=2$ and $lo(0)=0$.

def up(r,c,k):
    if k==0: return (r,c)
    if r==0: return (r,c-k)
    if c==0: return (r-k,c)
    if lo(r)<lo(c):
        steps=min(lo(x),k)
        return up(x-steps,y,k-steps)
    else:
        steps=min(lo(y),k)
        return up(x,y-steps,k-steps)

How do we actually find which node is the optimal one? Let's characterize it. Suppose we are at node x. Let $c(e)$ be the number of children in the subtree of edge $e$. If we cross an edge $e$, the total distance will change by $-c(e)+c(u_1)+c(u_2)+\cdots$, where $u_{1 \cdots N}$ are all the other edges. Thus, a slow solution would be to start at some node and greedily always walk towards the largest subtree, until we reach one where the largest edge has $c(e) \leq \frac{N}{2}$. In some regard, this is very similar to a centroid.

In order to find this node quickly, we will make use of the fact that all node degrees are very small in the tree (at most 4, maybe 3 but I won't bother trying to prove it). This means that in $c(u)>=N/3$ for the optimal node. In turn, if we select a random cow, we have atleast $\frac{1}{3}$ probability of selecting one which is in the subtree of the optimal node. Afterwards, we can find the node using binary lifting-style binary search. At each node, we can count the number of cows that is in the subtree rooted at v each subtree by making each cow $k$ go up $depth[v]-depth[k]$ steps and checking if the node it arrives at is $v$.

When we have found our optimal node, we need to calculate the sum of distances. In a tree, $dist(u,v)=depth[u]+depth[v]-2 \cdot lca(u,v)$. We can compute lca using the binary lifting described earlier. In total, the expected complexity is $O(N \cdot \log(10^9)^2)$.

## God jul

Consider all empty segments created by the Norwegians. Let us call these "root segments". Let $d$ be the length of one such segment. The crucial observation is that it splits into segments of at most $O(\log(d))$ different lengths. Counting the number of times each segment length will appear is left as an excercise for the reader.

Let us sort these in descending order by segment length, tiebroken by distance to seat number $1$. We can now do an offline sweep where we figure out which root segment each swedish person will end up in, in addition to the length of the segment. All that is left is to figure the actual seat they will sit in.

When answering each query, we will first reduce it by the number of subsegments skipped from other root segments. Let $u$ the number left. Now, we only need to consider the root segment our query will end up in. Let right be the direction towards seat $1$. Split the root segment by the rule, and check the total number of segments to the right. If this number is larger than $u$, recurse right. Otherwise, recurse left. This will run in approximately $O(Q \cdot \log(K)^2)$.