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

×

POSTTREE - Editorial

1
1

PROBLEM LINK

Practice
Contest

CONTEST PANEL

Author: Ildar Gainullin
Tester: Oleksandr Kulkov
Editorialist: Prateek Gupta

PREREQUISITES

Binary Lifting on a tree, lowest common ancestor, depth first search.

DIFFICULTY

EASY MEDIUM

PROBLEM

Given a tree with each node having some value. You need to find the cost of path from each node $v$ to the root of the tree. Cost of each node $u$ in path is the minimum of value of each node lying below u and is in path from $(u,\ v)$.

EXPLANATION

The problem involves using the concept of dynamic programming over a tree while moving from root to the bottom of the tree. Let $DP(x)$ denote the cost of path while moving from vertex $x$ to the root of the tree i.e $1$. While we arrive at node $x$, we have already calculated the DP values for all nodes in path from $1$ to $Parent[x]$. Now, for calculating the answer for node $x$, we need to find the greatest ancestor $y$ of $x$ in path from $1$ to $Parent[x]$, where all the nodes in path from $x$ to $y$ have their values greater than or equal to the given value of the node $x$.

If A[x] denotes the node value of x and cnt[x] denotes the number of nodes in path from $1$ to $x$, then the following equation holds true. $$DP(x) = DP(Parent[y]) + (cnt[x] - cnt[Parent[y])*A[x]$$

The only thing remaining is for each node x to calculate the greatest ancestor where all the nodes from node x to the ancestor have value greater than or equal to A[x]. One of the approaches is to pre-process this while calculating LCA and then apply binary lifting.

We define up[x][i] as the node that is ancestor of x at (2^i)-th distance from x. Then, $val[x][i]$ can be said as the minimum value of all the nodes from $x$ to up[x][i].

   set(up, -1)

   up[x][0] = Parent[x]
   for ( int i = 1 to 19 ) {
      if ( up[x][i - 1] != -1 ) {
          up[x][i] = up[up[x][i - 1]][i - 1]
      }
   }


   val[x][0] = min(A[x], A[Parent[x]]
   for ( i = 1 to 19 ) {
       if ( up[x][i] != -1 ) {
          val[x][i] = min(val[x][i - 1], val[up[x][i - 1]][i - 1])
      }
  }


Now, that we have preprocessed everything, how do we calculate the greatest ancestor of x such that minimum of values of nodes from x to this greatest ancestor in the path has value >= $A[x]$. This can be computed by binary lifting. For more details on binary lifting, check here. Anyways, let's proceed to look at the pseudo code.

    int vertex = x;
    for ( i = 19 to i = 0 ) {
        if ( up[vertex][i] != -1 ) {
            if ( val[vertex][i] >= A[x] ) {
              vertex = up[vertex][i];
            }
        }
    }

Now, up[vertex][0] will be the node having value < A[x]. Hence, all nodes from vertex to x will be affected by A[x] and will use this value as their cost. You might want to look at the above DP equation written which might make a little more sense to you now.

For details on the implementation, have a look at the author or tester's solution.

SOLUTIONS

Author solution can be found here.
Tester solution can be found here.

This question is marked "community wiki".

asked 28 May '17, 11:41

prateekg603's gravatar image

5★prateekg603
20421223
accept rate: 0%

edited 05 Jun '17, 16:22


Solution for this problem with binary lifting is great and the overall runtime is $O(nlogn)$ since you find the vertex $y$ of any vertex $x$ in $O(logn)$. I have a similar solution but I can reduce the runtime down to $O(n)$. You can see the implementation here: c++.

Here is a short explaination. This problem reminds me about the easier version of this problem that when the tree is a segment, the vertex $y$ of any vertex $x$ can be found using stack. My solution using a persistent-like stack. When you DFS to a child, you save the stack of the parent, and when you go back to the parent, just do rollback and continue DFS to another child. In my implementation, the operation push, pop, save and rollback run in $O(1)$. Each vertex you have to push it in the stack 1 time and the number of time you pop a vertex x equals to the direct child of the x. Since sum of direct child of all vertex equals to the number of the edges, that is, $n - 1$, hence overall complexity is $O(n + n - 1) = O(n)$.

link

answered 30 May '17, 15:39

darkkcyan's gravatar image

6★darkkcyan
422
accept rate: 0%

edited 30 May '17, 20:35

1

Yes. Even I was thinking on the similar lines during contest, but wasn't able to design a proper solution. Nice Solution :)

(30 May '17, 16:05) lohit_974★

Please open the problems for practice section! Also please add the link to read about Binary Lifting.

link

answered 29 May '17, 18:22

lohit_97's gravatar image

4★lohit_97
3428
accept rate: 4%

edited 29 May '17, 18:53

1

Hope this one helps

Link
video link

(30 May '17, 16:53) swamicoder4★

In the above equation i think,

it should be DP(x)=DP(Parent[y])+(cnt[x]−cnt[Parent[y])∗A[x].

link

answered 30 May '17, 17:59

hacker_sk's gravatar image

4★hacker_sk
1163
accept rate: 14%

Thanks, corrected.

(05 Jun '17, 16:22) prateekg6035★

In the above code,

val[x][0] = min(A[x], A[Parent[x]])

for ( i = 1 to 19 ) {

if ( up[x][i] != -1 ) {

val[x][i] = min(val[x][i - 1], val[val[x][i - 1]][i - 1])

}

}

I think it should be,

val[x][0] = min(A[x], A[Parent[x]])

for ( i = 1 to 19 ) {

if ( up[x][i] != -1 ) {

val[x][i] = min(val[x][i - 1], val[up[x][i - 1]][i - 1])

}

}

link

answered 31 May '17, 03:33

rmm_0304's gravatar image

4★rmm_0304
111
accept rate: 0%

Thanks, corrected.

(05 Jun '17, 16:22) prateekg6035★

implementation of editorial in C++ given below: https://www.codechef.com/viewsolution/13905914

link

answered 31 May '17, 16:14

shloksingh10's gravatar image

5★shloksingh10
311
accept rate: 0%

maybe the equation above need some fix.

link

answered 29 May '17, 19:24

microcosm2017's gravatar image

0★microcosm2017
1
accept rate: 0%

For those who need a tutorial on binary lifting. I learnt it pretty much from here: https://www.youtube.com/watch?v=kOfa6t8WnbI&t=971s

link
This answer is marked "community wiki".

answered 29 May '17, 19:53

ista2000's gravatar image

4★ista2000 ♦
2.4k722
accept rate: 20%

I too think the same hacker_sk

link

answered 31 May '17, 01:15

atuly's gravatar image

3★atuly
0
accept rate: 0%

Kindly someone please help me in finding the test case for which my code fails. All that i have tested passed but it is getting WA on submission. Link to my solution is https://www.codechef.com/viewsolution/13905563

link

answered 31 May '17, 15:47

the_king_i_am's gravatar image

2★the_king_i_am
111
accept rate: 0%

Kindly someone please help.I am unable to find a bug in my approach.Link to my solution is already posted.If someone can find the test case for which my code fails it would be of great help for finding the failure point in the code.

(01 Jun '17, 22:26) the_king_i_am2★

@darkkcyan This is indeed a good approach. But the worst case time complexity of this solution is O(n^2). Look at this test case:
15
1 2 3 4 5 6 7 8 8 8 8 8 8 8
93 94 95 96 97 98 99 100 1 2 3 4 5 6 7.

The while loop inside the dfs function runs n/2 times for all n>=9 i.e for n/2 times.
Hence the time complexity is O(n+(n/2)*(n/2))=O(n^2). Correct me if I am wrong. Cheers ! :)

link

answered 01 Jun '17, 15:44

rahulladda's gravatar image

2★rahulladda
212
accept rate: 0%

as mentioned in the editorial:

Now, for calculating the answer for node x, we need to find the greatest ancestor y of x in path from 11 to Parent[x]Parent[x], where all the nodes in path from x to y have their values greater than or equal to the given value of the node x.

Is there a constraint that nodes in path from x to y NEED to have their values(which are given during input) greater than or equal to the given value of the node x?

link

answered 04 Jun '17, 21:46

codegod96's gravatar image

0★codegod96
1
accept rate: 0%

why doesn't the setters code work??

link

answered 04 Jun '17, 23:09

drag's gravatar image

3★drag
12
accept rate: 0%

weak test cases , even brute-force is passing the problem with a runtime of 0.06 which is having time limit of 2.0 sec ! my solution: posttree soln

link

answered 10 Jun '17, 17:44

docodon's gravatar image

4★docodon
776
accept rate: 0%

edited 10 Jun '17, 17:48

i tried this but getting WA in the last test case of second subtask.. if possible please help me with my code..

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

link

answered 26 Jul '17, 22:07

sidd845's gravatar image

3★sidd845
254
accept rate: 0%

can anyone please explain a little bit how counts array is built?

i have implemented without this with the help of binary search ! but want to know this !

link

answered 20 Oct '17, 19:34

pk301's gravatar image

2★pk301
62710
accept rate: 16%

https://www.codechef.com/viewsolution/17201285 My solution using simple DP and dfs. I basically created two arrays, one storing all forward node information and the other one storing all backward node info.

link

answered 31 Jan '18, 02:18

shivan111's gravatar image

2★shivan111
101
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,672
×726
×253
×43
×5

question asked: 28 May '17, 11:41

question was seen: 2,701 times

last updated: 31 Jan '18, 02:18