UPDOTR - EDITORIAL

general
, , , , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: DOlaBMOon
Tester: Hussain
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy-Medium

PREREQUISITES:

DFS or BFS, DP on trees and Binary Lifting.

PROBLEM:

Given a Tree rooted at one, each node having an integer value A[i] associated with it, we need to answer following query.

  • Given a vertex V and a value W, Find Number of times we get the next greater element when W is first element, and we move from root 1 to V.

SUPER QUICK EXPLANATION

  •   Pre-process answer for $W = 0$ for all nodes, say ans array and for every query use binary lifting to reach the node farthest from root on path of root to $V$ such that maximum value on path from root to this node is less than or equal to $W$, say node $X$. Answer is Just $ans[V]-ans[X]$.

EXPLANATION

First of all, let’s solve this problem without queries, that is, Calculate answer for W = 0 for all nodes.

Suppose we have two values for each node, say MX[i] and C[i] - Maximum value from root to node, and Number of times Chef learnt a new dish, that is, number of times the maximum value changes on path from root to node.

Give a try to formulating a recurrence for calculating these two values for a node, when these values for parent are known. Cannot figure out? Refer the secret box :stuck_out_tongue:

Click to view

If Max value up to parent node is less than value associated with current node, then Count for current node is one more than count up to parent, and Maximum value is value associated with current node. Otherwise Maximum value doesn’t change, so count too doesn’t change, thus, is same as parent.

Also, for root 1, MX[1] = A[1] and C[1] = 1

So, now we have solved this problems for all nodes and W = 0.

But about our actual problem?? For that, we need another observation regarding maximum values MX.

Lemma: As we move down from parent to child, the maximum value either remain same or increases.

I know this is a simple statement which is directly understood from definition of maximum. But the real impact of this statement is that it allow us to answer each query in O(log(N)) time, which is fast enough for our need.

From above statement, it follows that if MX[U] \leq W, then for all ancestors X of node U, MX[X] \leq W.

Suppose for query (V, W), we find a node X on path from root to node V such that MX[X] \leq W and MX[C] > W, where C is direct child of X on path to V. Then, we know that Number of times Maximum value changes from W to MX[V] is same as Number of times Maximum changes from root to V less Number of times Maximum changes from root to Node X.

So, now we know that if we can find this node X efficiently, we have solved the problem, Right?

A simple method of checking every ancestor of V will result in O(N) time in worst case (Linear chain), which will time out, due to overall complexity O(Q*N).

How can we utilize the fact that MX[X] \leq W for all ancestors of X. We can use the concept of Binary Lifting.

A brief Description of Binary Lifting using Sparse Table follows, so i hope those who do know binary lifting will let their attention wander freely and feel free to skip this paragraph :smiley:

We create a 2-dimensional array table[N][logN], where table[u][i] store $2^i$th parent of node u. How to fill this table? We know that table[u][0] - 1st parent of u, that is, direct parent of u, is already known from dfs. Now, We fill our table as follows.

Since 2^{i+1} = 2^i + 2^i, which means, that $2^{i+1}$th parent of u is same as $2^i$th parent of node which is $2^i$th parent of u. This means that table[u][i+1] = table[table[u][i]][i]

That’s all about binary lifting. Generally We iterate from LogN-1 to 0, having a test condition which tells us to move 2^i steps or not in ith iteration.

Returning to our problem, we can create the sparse table easily. Then try to formulate Test Condition which will tell us, whether to jump to table[u][i] or not. Here, we will move to node Y such that MX[Y] > W and all ancestors of Y have MX[u] \leq W. Then required node X is parent of Y.

Click to view

Test condition is just that if a node u have MX[u]\leq W, then don’t jump, otherwise jump.

Now that we have found the he node X required answer is just C[V]-C[X]. Degenrate cases can be handled easily. In case MX[V] \leq W, answer is 0 as maximum value never changes. If W < MX[1], answer is simply C[V].

I’ll be updating links/more references soon.

TIME COMPLEXITY

Preprocessing time for sparse Table - O(N*logN), query time O(logN).

So, Overall Complexity O((Q+N)*logN)

REFERENCES:

Binary Lifting
DP on Trees for further reading

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

7 Likes
2

Very nicely explained editorial :)…BTW can anyone help me why my solution gives a TLE , I followed just the editorialist’s approach.

3

I need help in debugging my solution. It get’s WA. Is there a corner case I’m missing?

4

Now that we have found the he node X required answer is just C[V]−C[X]. Degenrate cases can be handled easily. In case MX[V]≤W, answer is 0 as maximum value never changes. If W < MX[1], answer is simply C[V].

What is the difference b/w these two implementations ? First one got WA Second got AC

First One

 int tmp = a;
 for(int  i = LOGN-1;i>=0;i--)
        {
            if(P[tmp][i]!=-1)
            {
                if(MX[P[tmp][i]]>b)
                    tmp = P[tmp][i];
            }
        }
        if(tmp == 0) prev = Cnt[a];
        else if(tmp == a) prev =0;
        else
        {
            int  tmp1 = P[tmp][0];
            prev =Cnt[a]-Cnt[tmp1];
        }

SECOND ONE

        int  tmp =a;
        if(MX[a] <= b)
        {
            prev =0;
        }
        else if(MX[0] > b)
        {
            prev = Cnt[a];
        }
        else
        {
            for(int i = LOGN-1;i>=0;i--)
            {
                if(P[tmp][i]!=-1)
                {
                    if(MX[P[tmp][i]]>b)
                        tmp = P[tmp][i];
                }
            }
            int tmp1 = P[tmp][0];
            prev =Cnt[a]-Cnt[tmp1];
        }

Thanks!!

5

It is better to use iterative DFS, wherever possible, Because it reduces recursive calls time as well as stack memory consumption (especially for java). Rest all seems right.

Glad you liked editorial.

3 Likes
6

Thanks @taran_1407, got it AC’ed with iterative DFS :slight_smile:

7

And in this part of the editorial there is a typo … 2^(i+1) = (2^i) * (2^i) … it will be 2^(i+1) = (2^i) * 2. Please edit that part…

1 Like
8

No problem :slight_smile:
Oh, I actually meant 2^(i+1) = 2^i+2^i. Thanks, I’ll correct it.

9

@taran_1407 can you say is the recursion depth for JAVA < 1e6 , which may be the reason for TLE ?

10

Not excatly recursion depth, but the revursive calls. The iterative version is usually faster, as recursion stack slow down, when too much calls are in stack.

11

First One : CodeChef: Practical coding for everyone

Second One : CodeChef: Practical coding for everyone