KIRMEME - Editorial

PROBLEM LINK:

Practice
Contest

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.

2 Likes

kindly upload setters and testers solution.

1 Like

Why 20 testcases with N=50000? Using fewer testcases with a higher number of N would definitely have discriminated asymptotically subotimal solutions far better. I used a different approach (the editorialists’s approach is far better so no need to discuss it) submitting a preliminary version with O(n^2) worst-case behaviour and it easily passed.

3 Likes

@ceilks could you share your approach?

You can see my submission following the same centroid decomposition method described in the editorial: https://www.codechef.com/viewsolution/12097460

And if you want to read more about centroid composition and where you can apply it, you can check my editorial to one of the problems from October Lunchtime here: https://discuss.codechef.com/questions/86796/counties-editorial

3 Likes

Thanks for the editorial.
I have trouble understanding how the merge step is O(n). Combining the counts of all pairs of Ais & Bis is O(n^2) right? (and similarly for all pairs of Ais & Cis and so on.)

1 Like

My approach is quite different from the editorial, but its giving wrong answer and I am clueless where it is wrong.

Code :-

https://www.codechef.com/viewsolution/12095927

I have a similar solution but it is O(N * log N * log N). Extra log N is for BIT. looks like tester’s solution is also the same.

In the editorial it’s claimed as O(N * log N), how is that?

Thanks :slight_smile:

2 Likes

Given Setter’s solution is O(n^2) and it is giving TLE. Can you please check that again.

1 Like

I uset BIT for solving this :wink:
https://www.codechef.com/viewsolution/16007035

it can be done in O(n), let’s say in case of A and C arrays, iterate over all indices of array A, let’s say we are now in index j, then you need to match with all elements in array C with indices in range L-j … R-j, this can be done in O(1) using cumulative sum so overall it’s O(n)