Count Nodes - Editorial

general
, ,
1

Links

[Contest](https://www.codechef.com/INSO2018/problems/CNTNODE)

Author: Adarsh Kumar

Tester: Samarth Joshi

Editorialist: Adarsh Kumar

DIFFICULTY:

Medium

PREREQUISITES:

Segment tree, Dynamic Programming

EXPLANATION:

The maximum value of k can be 2logn. This can be proved intuitively.

For every node representing the range (l,r) we will store three arrays:

pre[i] - number of ranges (l,p) for which cnt = i;

suf[i] - number of ranges (p,r) for which cnt = i;

ans[i] - number of ranges (p,q) for which cnt = i;

where <i>(1 <= i <= k), (l <= p,q <= r)</i>

Then a post order traversal is done to calculate the above values for every node. For merging the child nodes of a parent node:

pre[i][node] = pre[i]

suf[i][node] = suf[i][right]

ans[i+j][node] = sum(suf[i]*pre[j][right])

The answer to the problem is ans[i][1]

Author’s Solution can be found here

Tester’s Solution can be found here

2 Likes
2

Can also be solved like this:

Dp[i][j] denotes the number of segment such that their range starts with the ith node and they cover exactly j nodes including ith node.

Base case:dp[i][1]=1 for all node i(as only 1 segment exists(represented by the node itself))

Recurrence:

Dp[i][j]=sum(dp[k][j-1]) where k is the next node that we can take after we take the ith node(in segment tree of n=5,for node representing range (1,3) we can have k as node representing (4,4))

U’ll see there are atmost logN possible values of k

Complexity:O(nlog^2n)

Solution: https://www.codechef.com/viewsolution/17950616

2 Likes
3

didn’t get the author solution it would be great if he added comment @spj_29

4

somebody just post the other approach or explain it pls and it would be quite wise if they explain the question language

5

I too had solved it like the same way! :slight_smile: