You are not logged in. Please login at www.codechef.com to post your questions!

×

UPDOTR - EDITORIAL

6
2

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 :P

View Content

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 :D

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$.

View Content

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. :)

This question is marked "community wiki".

asked 23 Sep '18, 12:36

taran_1407's gravatar image

5★taran_1407
4.0k31105
accept rate: 22%

edited 25 Sep '18, 02:15


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

link

answered 25 Sep '18, 01:32

aman_robotics's gravatar image

6★aman_robotics
1217
accept rate: 6%

edited 25 Sep '18, 01:38

3

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.

(25 Sep '18, 01:43) taran_14075★

Thanks @taran_1407, got it AC'ed with iterative DFS :)

(25 Sep '18, 02:10) aman_robotics6★
1

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

(25 Sep '18, 02:13) aman_robotics6★

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

(25 Sep '18, 02:14) taran_14075★

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

(25 Sep '18, 02:28) aman_robotics6★

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.

(25 Sep '18, 02:44) taran_14075★
showing 5 of 6 show all

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

link

answered 26 Sep '18, 12:39

ninja_69's gravatar image

4★ninja_69
192
accept rate: 0%

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

link

answered 04 Oct '18, 19:58

ksskreddy2015's gravatar image

4★ksskreddy2015
11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,723
×729
×115
×69
×65
×10

question asked: 23 Sep '18, 12:36

question was seen: 1,547 times

last updated: 04 Oct '18, 20:01