## North coding contest 2020

posted on April 10, 2020, 8:58 p.m.

Welcome to MOI Arena

```
print "Hello, to NCC!"
```

The first edition of the North Coding Contest (NCC 2020) is going to be held on **Saturday, April, 11** at 20:00 Morocco time.

You will be given between 8 to 10 problems and 4 hours to solve them.

The contest will follow ICPC Rules : The penalty for each incorrect submission until the submission with a full solution is 10 minutes.

This contest will be **RATED**

More info at ECDH website

Stay tuned, and follow us on Facebook

## Comments

Before anything, let's define a pair \((l1,l2)\) to be good iff it's possible to construct two non intersecting paths of lengths \((l1,l2)\)

Now, allow me to throw some random clear observations one could see when thinking about the problem:

Since some of these observations involve the diameter of the tree, and this last observation already covers one of the cases, let's find one of the diameters of the tree and continue to think about our tree as seen below:

Let's quickly cover the case mentioned in that last observation. The maximum length \(max_{l1}\) of some path that doesn't contain any node from the diameter is the maximum among lengths of diameters of all subtrees. We can find all of them in \(O(n)\) time and set \(Ans_i\) to \(diameterlength\) for all \(i\leq max_{l1}\)

So we're left with one remaining case, but before getting into it, let's number the nodes of the diameter from \(1\) to \(diameterlength\) going from left to right, and let's define \(pre_i\) and \(suf_i\) as follows: after removing the edge \((i,i+1)\), we get two trees, the one that contains node \(i\) is \(pre_i\) and the other one is \(suf_{i+1}\)

Now consider a path of length \(l1\) which contains one ore more nodes from the diameter, those diameter nodes make one contiguous segment \([l,r]\) in the diameter, and the path extends in one of the subtrees linked to node \(l\), and one of the subtrees linked to node \(r\). If we were to consider a non intersecting path of length \(l2\), it could either be in \(pre_{l-1}\), \(suf_{r+1}\) or one of the subtrees linked to nodes in \([l,r]\), but we are going to ignore this last possibility because we already covered it in the 1st case. WLOG suppose the second path belongs to \(suf_{r+1}\), and we know that the first path belongs to \(pre_r\), then notice how \(pre_r\) and \(suf_{r+1}\) are disjoint, which means that we can maximize \(Ans[diameterpre_r]\) with \(diametersuf_{r+1}\) and \(Ans[diametersuf_{r+1}]\) with \(diameterpre_r\), meaning that pair \((diameterpre_r,diametersuf_{r+1})\) is good which directly implies that \((l1,l2)\) is also good because of observation 1.

We're almost done, but we still have to find every \(diameterpre_i\) and \(diametersuf_i\) efficiently. Suppose we already found \(diameterpre_i\), there are two possible cases for \(diameterpre_{i+1}\):

After dealing with the two cases, one must not forget to maximize \(Ans_i\) with \(max(Ans_{j>=i})\) because of observation 1, then for each query \((l1,l2)\) we must answer YES iff \(ans_{l1}>=l2\)

Time complexity : \(O(N+Q)\)

Check my implementation for more details : https://ideone.com/vNB3h9