## 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

• medk  commented on April 14, 2020, 4:50 p.m.

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:

• if $$(l1,l2)$$ is good, then obviously all pairs $$(l1,i)$$ where $$1\le i\le l2$$ are also good
• that means that if we could find for each length $$l1$$ the maximum $$l2$$ such that $$(l1,l2)$$ is good and store them in some array $$Ans$$ then we can answer each query in $$O(1)$$
• if $$l1>diameterlength$$ then any pair $$(l1,l2)$$ is bad
• Suppose that we were to construct a path of length $$l1$$ which doesn't contain any node from some diameter, then pair $$(l1,diameterlength)$$ is good

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}$$:

• the diameter of $$pre_{i+1}$$ doesn't contain node $$i+1$$, in that case $$diameterpre_{i+1} = diameterpre_i$$
• otherwise, the diameter of $$pre_{i+1}$$ passes through node $$i+1$$ and extends in one of the paths in $$pre_i$$ that starts with node $$i$$, as well as in one of its subtrees. The maximum for these two is path $$1,2,...,i$$ and the max depth from all subtrees of $$i+1$$, respectively. Which means that $$diameterpre_{i+1} = max( diameterpre_i , i+1+maxsubtreedepth_{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