PROBLEM LINK:
DIFFICULTY:
Medium-Hard
PREREQUISITES:
divide and conquer, trees, DFS
PROBLEM:
Given a tree of N vertices and two integers L and R, i-th vertex of the tree has value ai, you are required to count the number of simple paths v1, v2, …, vK such that the number of indices j with 1 < j < K with avj-1 < avj and avj > avj+1 is at least L and at most R.
SHORT EXPLANATION:
let’s call a triple of 3 consecutive vertices in a path such that avj-1 < avj and avj > avj+1 by “interesting triple”
We will use divide and conquer on tree to solve this problem, first we find the centroid node of the tree then try to count the required paths which passes through the centroid node then we delete it and solve the same problem problem on every sub-tree created after deleting.
to count number of paths required which passes through the centroid, first we do DFS from the centroid to count the paths which start at the centroid itself, then we need to consider the case when the centroid is in the middle of the path, in other words that path consists of two sub-paths plus vertex V, so we maintain 3 arrays A, B, C,
Ai means the number of paths which have i interesting triples and start at neighbor of V and that neighbor have value less than V
Bi means the number of paths which have i interesting triples and start at neighbor of V and that neighbor have value bigger than V but second vertex at this path is less than that neighbor
Ci means the number of paths which have i interesting triples and start at neighbor of V and that neighbor have value bigger than V but second vertex at this path is not less than that neighbor
then we count the number of pairs of those paths which will make a path passing through vertex V and having between L and R triples
EXPLANATION
let’s call a triple of 3 consecutive vertices in a path such that avj-1 < avj and avj > avj+1 by “interesting triple”
Special Case: Counting only paths which starts from a particular vertex
This special case will help us to solve the problem in O(N^2) and thus get partial score, and also it’s a part of the approach of the full solution.
To count the paths which starts at a given vertex V, we root the tree at the vertex V then do a recursive dfs and hold some parameter how many interesting triples found so far, here’s pseudo code for it:
dfs(int v,int count){
ans = ans + count
for each child u of v{
if(A[parent[v]] < A[v] && A[v] > A[u]){
dfs(u,count+1)
} else {
dfs(u,count)
}
}
}
General description of full solution
The full solution to this problem is called divide and conquer on tree, if we pick some vertex V from the tree then all paths will either pass from V or will be completely contained in one of the sub-trees which will be formed if we delete vertex V
so the idea would be to select some node v then count all interesting paths which passes through it then delete that vertex and solve the problem recursively for each sub-tree remained after deleting V, selecting best vertex V is critical in order to make the complexity of our solution faster than O(N^2)
paths which pass through vertex V have two cases, first vertex V is the first node on that path then we can count them just like what is described in previous paragraph, second for paths in which vertex V is in the middle of it then we notice that the path will start at one sub-tree then reach v then go again to another sub-tree, in other words those paths consist of two sub-paths plus vertex V, so the idea is count those sub-paths then we count how many pairs of sub-paths can be paired in such a way the number of interesting triples is between L and R, we have 3 types of sub-paths so we obtain 3 arrays:
Ai means the number of paths which have i interesting triples and start at neighbor of V and that neighbor have value less than V
Bi means the number of paths which have i interesting triples and start at neighbor of V and that neighbor have value bigger than V but second vertex at this path is less than that neighbor
Ci means the number of paths which have i interesting triples and start at neighbor of V and that neighbor have value bigger than V but second vertex at this path is not less than that neighbor
they can be obtained by DFS similar to one above, now we should look at possible pairing of the sub-paths
-
two sub-paths of type A having i and j interesting triples, this will result in a path having i+j+1 interesting triples
-
two sub-paths of type B having i and j interesting triples, this will result in a path having i+j+2 interesting triples
-
two sub-paths of type C having i and j interesting triples, this will result in a path having i+j interesting triples
-
one sub-path of type A and one of type B having i and j interesting triples, this will result in a path having i+j+1 interesting triples
-
one sub-path of type A and one of type C having i and j interesting triples, this will result in a path having i+j interesting triples
-
one sub-path of type B and one of type C having i and j interesting triples, this will result in a path having i+j+1 interesting triples
Choosing the best vertex V
if we choose the vertex V in such a way that every remaining sub-tree after deleting vertex V will have size at most half size of the current tree then our recursion will have at most O(log N) layers each, layer will take O(N) time so in total complexity would be O(N log N)
but how to find such a vertex? it can be proved that such a vertex always exists for any tree the description of the algorithm to find it can itself work as a proof and this vertex is call centriod vertex
Let’s start at an arbitrary vertex V, and make it the root of the tree then we compute the size of every sub-tree in that tree, now let’s check is there a child of vertex V having in its sub-tree more than half of vertices of sub-tree of V? if no then we are done because vertex V is the centriod vertex
if no then there would be at most one such child, so we visit that child and repeat until we find the centroid
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.
