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

×

JTREE- Unofficial Editorial

27
10

PROBLEM LINK : Practice , Contest

PREREQUISITES : dfs , Segment trees , dp

PROBLEM : Given a tree with edges directed towards root and nodes having some ticket information which allows you to travel k units towards the root with cost w . Answer Q queries i.e output the minimum cost for travelling from a node x to root .

OBSERVATIONS: Consider the tree to be rooted at 1 , so now every node has a directed edge towards its parent except the root , which means there is a unique path from every node to the root 1. So if we solve the problem for one unique path or one node, we can extend it for other paths as well .

EXPLANATION: Lets try to solve the problem for a node X at depth H from the root 1 . So for now forget the tree and think of it as a 1D vector V where you have all the H-1 nodes that are between root and node X . The nodes inside the vector are sorted in the order of increasing depth . Lets just denote DP[x] to be the minimum cost of travelling from node X to the root .

So now for the given node X , lets just iterate over all the tickets present at node X and DP state will be like this :

for(int i=0;i<total_tickets;i++) // loop 1
{
     K=current_ticket_jump_info; 
     W=weight_ticket_info;
     for(int j=V.size()-1;j>= max(0,V.size()-1-k);j++) //loop 2
     {
        DP[X]=min( DP[X] , DP[V[j]] + W );
     }
}

Code Explanation : Loop 1 simply iterates over the tickets at x and for a given ticket we can move at max K steps upwards towards the root and as we have already stored those nodes in our vector V , we can iterate over it . so the inner loop moves over those K steps to find the minimum cost .

But how can we calculate vector V for every node x ? Here comes DFS in action :

 void dfs(int u,int p)
{
         V.push_back(u);
         for(int i=0 ; i< adj[u].size() ; i++)
         {
            if(adj[u][i]==p)continue;
            dfs(adj[u][i],u);
         }
         V.pop_back();
}

Code Explanation : what we are doing over here is pushing a node u to the vector V when we haven't discovered the subtree of u and pop it when the whole subtree is discovered . Its obvious that u will always lie between the path of any node which is in subtree of u and root . And this also take cares of the sorted depth order . If you aren't getting this , try to draw a few trees .

So the final code :

void dfs(int u,int p)
{
         V.push_back(u);
         for(int l=0 ; l< adj[u].size() ; l++)
         {
            if(adj[u][l]==p)continue;
            int x =adj[u][l];
            for(int i=0;i<total_tickets;i++) // loop 1
           {
               K=current_ticket_jump_info; 
               W=weight_ticket_info;
               for(int j=V.size()-1;j>= max(0,V.size()-1-k);j++) //loop 2
               {
                    DP[x]=min( DP[x] , DP[V[j]] + W );
                }
             }
            dfs(adj[u][l],u);
         }
         V.pop_back();
}

Complexity: : Well the complexity is simply O(N+M*N) , Damn :( ! we need optimisations :P

OBSERVATIONS: if we look at the inner loop of the code which goes up to K times and we find the minimum of DP , this can be done using any data structure that supports RMQ + Point updates in O(logn) time . Which will make the total complexity to be O(N + MlogN) and that is cool :P .

So what we can do is build a segment tree that supports two operations . First : find the minimum element in range L,R and Second: update an element's value to VAL. And obviously as we need to query for the minimum element between [H-K , H] so we will build the tree over height H .

//consider segment tree has already been built with every element to be infinity apart from element 1 , which will be 0 because at height 1 , root is present .
void dfs(int u,int p,int h)
{
         updatetree(0,1,n,h,DP[u]); // update the tree element at position h with its DP value . remember , node u is at height h and tree is built on height so we will update h position in the tree and not u .
         for(int l=0 ; l< adj[u].size() ; l++)
         {
            if(adj[u][l]==p)continue;
            int x =adj[u][l];
            for(int i=0;i<total_tickets;i++) // loop 1
           {
               K=current_ticket_jump_info; 
               W=weight_ticket_info;
               DP[x]=query(0,1,n,max(1,h-K),h)+W;
             }
            dfs(adj[u][l],u,h+1);
         }
         updatetree(0,1,n,h,INFINITY); // update the tree at with element h with Infinity as we are done with its subtree . 
}

Now just print DP[x] for every query . AC :D . For the actual code refer this .

For example : This is the given tree . alt text

So this will be our segment tree before DFS . alt text

Now , we see for the given tree the longest path between any node and root is of 4 nodes and for computing DP[x] we just need all the DP values of the nodes which lie between x to root i.e for a given height there will be only one DP value . example : for calculating DP[7] , we need DP[1] , DP[2] , DP[4] and DP[1] is at height 1 , DP[2] is at height 2 , DP[4] is at height 3 . So during dfs and updations , at node 7 our segment tree will look like this :

alt text

Now at node 7 let there be a ticket with k=2 , w=1 . So now we will query for minimum value between height [2,4] and compute our DP[7] . Now 7 has no children and dfs starts rolling back , and we update height 3 in segment tree with infinity . now at node 5 DPs we require are only DP[1] , DP[2] . The scenario of segment tree will be like this :

alt text

Now Let the ticket available at node 5 be k=3 , w=7 . So now we query over segment tree between [1,3].

asked 15 Sep '16, 19:51

arunnsit's gravatar image

6★arunnsit
1.0k1611
accept rate: 27%

edited 12 Feb '17, 21:32

Awesome explanation with the images, just give a link in official editorial as different approach to the problem

(18 Sep '16, 08:06) likecs6★

Awesome Soln Man!

link

answered 15 Sep '16, 21:43

kainthabhishek's gravatar image

5★kainthabhishek
61
accept rate: 0%

Great examples! @arunnsit

link

answered 16 Sep '16, 21:19

achlomanziony's gravatar image

4★achlomanziony
511
accept rate: 0%

I cannot understand this part - "So what we can do is build a segment tree that supports two operations . First : find the minimum element in range L,R and Second: update an element's value to VAL. And obviously as we need to query for the minimum element between [H-K , H] so we will build the tree over height H ."

After finding minimum, we should add that value to the front of array. Then again find minimum using this array. But you didn't add any new value?

link

answered 15 Sep '16, 20:06

dushsingh1995's gravatar image

4★dushsingh1995
98314
accept rate: 11%

@dushsingh1995 , we don't need the array this time , we are handling this with the segment tree . See for calculating solution for a node x , we have already updated our tree with DP[all nodes between the path from 1 to x] and thats all what we require . If you will be more specific , i can explain it in more details !

(15 Sep '16, 20:22) arunnsit6★

I have split the tree into parts of length $sqrt(N)$. Since the tree is "static", now usual RMQ in 3*O(sqrt(N)) will pass yielding total complexity $O(Nsqrt(N))$. I dont understand how did u build that segment tree, what does over height H mean?

link

answered 15 Sep '16, 20:12

nidzulandz's gravatar image

6★nidzulandz
15318
accept rate: 0%

Give me a few mins , i will update it with an example :)

(15 Sep '16, 20:25) arunnsit6★

@nidzulandz , updated :)

(15 Sep '16, 21:12) arunnsit6★

@arunnsit Got it immidietly with examples! Amazing solution :D

(15 Sep '16, 22:04) nidzulandz6★

Or we can do a bit easier: to take a minimum with binary lifting. So 1 get instead of update and get of segment tree. (A bit less to write).

link

answered 15 Sep '16, 21:55

simb4's gravatar image

4★simb4
1
accept rate: 0%

Or we can do the same with bin lift, which is for me a bit easier to implement.

link

answered 15 Sep '16, 21:57

simb4's gravatar image

4★simb4
1
accept rate: 0%

I used Sparse Table for calculating the minimum. It supports:- Get minimum for range l-r in O(1) time. Update the table in O(logn) time. Not for this question but for strict time limits, I would recommend sparse table.

Accepted solution:- https://www.codechef.com/viewsolution/11382852

link

answered 15 Sep '16, 22:07

kqr45j's gravatar image

5★kqr45j
6117
accept rate: 0%

What is wrong with my code? Getting WA on some cases...

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define NMAX 1000056
#define TMAX 5000056
using namespace std;

typedef long long ll;

ll n, m;
vector<ll> adj[NMAX];
vector< pair<ll,ll> > tick[NMAX];
ll seg[TMAX];
ll dp[NMAX];

ll max(ll x, ll y) {
    return x > y ? x : y;
}

void update(ll node, ll start, ll end, 
                    ll idx, ll val) {
    if(start == end) {
        seg[node] = val;
        return ;
    }
    ll mid = start + (end - start) / 2;
    if(idx <= mid)
        update(2*node+1, start, mid, 
                        idx, val);
    else
        update(2*node+2, mid+1,
                    end, idx, val);
    seg[node] = min(seg[2*node+1], seg[2*node+2]);
}

ll query(ll node, ll start, ll end, 
                        ll left, ll right) {
    if(start > right || end < left)
        return INF;
    if(left <= start && end <= right)
        return seg[node];
    ll mid = start + (end - start) / 2;
    ll q1 = query(2*node+1, start, mid, left, right);
    ll q2 = query(2*node+2, mid+1, end, left, right);
    return min(q1, q2);
}

void dfs(ll u, ll h) {
    for(const auto p : tick[u])
        dp[u] = min(dp[u], 
                p.second + query(0, 0, n, 
                                max(0, h-p.first), h));
    update(0, 0, n, h, dp[u]);
    for(ll v : adj[u])
        dfs(v, h+1);
    update(0, 0, n, h, INF);
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(ll i=0;i<n-1;i++) {
        ll u, v;
        cin >> u >> v;
        adj[v].push_back(u);
    }
    for(ll i=0;i<m;i++) {
        ll v, k, w;
        cin >> v >> k >> w;
        tick[v].push_back(make_pair(k, w));
    }
    memset(seg, INF, sizeof(seg));
    memset(dp, INF, sizeof(dp));
    dp[1] = 0;
    update(0, 0, n, 0, dp[1]);
    dfs(1, 0);
    ll q;
    cin >> q;
    while(q--) {
        ll s;
        cin >> s;
        cout << dp[s] << endl;
    }
    return 0;
}

SOLVED : INF was too small. Cost me 75 pts.

link

answered 16 Sep '16, 00:34

trojan1996's gravatar image

2★trojan1996
1
accept rate: 0%

edited 16 Sep '16, 02:02

Aaah. That was harsh!

(16 Sep '16, 02:12) lohit_974★

Mine is also similar to this one but, Insted of doing a segment tree to find out minimum in among the k parents , i am using binary ascent, i store the parents at level 1,2,4,8,16,32,64 like that and minimum cost till then,

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

link

answered 16 Sep '16, 02:09

geek_geek's gravatar image

4★geek_geek
43914
accept rate: 16%

@kqr45j
Can you please explain how to update sparse table in O(Log(n)) time?

Or Any link through which we can learn the update part?

Thanks

link

answered 16 Sep '16, 11:02

vishveshcoder's gravatar image

4★vishveshcoder
18729
accept rate: 0%

Similar solution but used the segment tree storage for as the dp table instead of creating a separate one. :)

link

answered 16 Sep '16, 11:25

pseudopenggy's gravatar image

2★pseudopenggy
1
accept rate: 0%

Awesome solution bro.Respect _ / \ _ :)

link

answered 16 Sep '16, 14:54

aloochaat1998's gravatar image

5★aloochaat1998
995
accept rate: 16%

edited 16 Sep '16, 14:55

Thanks alot :)

(16 Sep '16, 21:01) arunnsit6★

@vishveshcoder Hi,I will try to explain on how the updation works in case of sparse table.

If you don't know about sparse table I would recommend you to go through topcoder tutorial first. It is quite easy to understand everything related to sparse table.

Still If you are having trouble in understanding then I will explain the main idea behind sparse table-

For each index 'i' in the array we store the minimum of all continuous subarray of length 2^k(k belongs to whole number {0,1,2,...} ) which start at index 'i' till (i+2^k) is less than n(size of array).

Representation is table[i][k] where i is the index and 2^k is the length of the continuous subarray.arr[] is the array containing the elements.

For eg: if we are index i = 5 and lets say the size of array is n = 22, then for index i = 5 we will store the following information(this information is only for index i=5, we have to store such type of information for every node) :-

For k = 0, length = 2^k => length = 1, we store the minimum of subarray of length = 1 starting at index i = 5, which means minimum of index i = 5 only. So we have only one element and minimum of it will be itself only. => (table[5][0] = arr[5])

For k=1, length = 2^k -> length = 2, we store the minimum of subarray of length = 2 starting at index i = 5, which means minimum of index i = 5 and i = 6. => (table[5][1] = min(arr[5],arr[6]) )

For k=2, length = 2^k -> length = 4, we store the minimum of subarray of length = 4 starting at index i = 5, which means minimum of index i = 5,i = 6,i = 7 and i = 8.=> (table[5][2] = min(arr[5],arr[6],arr[7],arr[8]) )

For k=3, length = 2^k -> length = 8, we store the minimum of subarray of length = 8 starting at index i = 5, which means minimum of index i = 5 till i = 12 (from index 5 to 12 we have 8 elements). => (table[5][3] = min(arr[5], ..... ,arr[12]) )

For k=4, length = 2^k -> length = 16, we store the minimum of subarray of length = 16 starting at index i = 5, which means minimum of index i = 5 till i = 20 (from index 5 to 20 we have 16 elements). => (table[5][4] = min(arr[5], ..... ,arr[20]) )

For k=5, length = 2^k -> length = 32, we store the minimum of subarray of length = 32 starting at index i = 5, which means minimum of index i = 5 till i = 36 => (from index 5 to 36 we have 32 elements).

But for the last case k = 5, we can't go till index 36 since size of array is n = 22 only, so we will store the minimum till 22 only for k = 5. => (table[5][5] = min(arr[5], ..... ,arr[22]) )

Now must be wondering on how to store these values, right? Before that, Please understand that for each value of k, we will store answer for each element in the array and then we will increase our K, meaning, for k = 0 I will store the answer for each element and then only I will move on to k = 1. Similarly after I have stored the value(for k = 1) for each element, then only I will increment my k. So with that in mind, now you can move on to an example which will do 90% of the work itself.

Let's say you are at index i = 5 and you need to calculate minimum for k = 4(length = 16, from index 5 till 20). Also, we know the answer for k=3 for each element in the array (How? please read the above paragraph once again). So now I will use the value stored for k = 3 to calculate the value for k = 4(which is a basic DP too).

For index i=5 and for k=4, the value will be MINIMUM of table[5][3] and table[13][3] . Because table[5][3] stores the minimum for elements from arr[5] till arr[12] and table[13][3] will store the minimum of arr[13] till arr[20] (since from index 13 to 20 we have 8 elements or length = 2^3). So for minimum of arr[5] till arr[20] we can directly use the previous values quite easily and update our value of table[5][4] in O(1) time .

In other words we divide our current target subarray (5 - 20) in two parts and use the previously computed values, since if we are calculating for length = 16 then, we must have computed for length = 8 before.

Now for this problem, as we move down the tree from root to some node, I already have the minimum stored for the nodes which come in the path from root to the current node. So for current node we repeat the same procedure as we did above and update the minimum values for each length for current node.

If you still have any doubt, then feel free to ask.

link

answered 17 Sep '16, 00:13

kqr45j's gravatar image

5★kqr45j
6117
accept rate: 0%

Great logic! (y)

link

answered 18 Sep '16, 05:53

az1az10_1995's gravatar image

3★az1az10_1995
1
accept rate: 0%

@arunnsit Great explanation. Thanks for that.

But I had one doubt which I hope you will be able to clear. The complexity you told is O(Nlog(n) + M). What I think is, since log(n) time is spent for each ticket and there are M tickets, it should have been O(N + Mlog(n)). Correct me if I am wrong.

link

answered 20 Sep '16, 11:20

kishu18_agar's gravatar image

4★kishu18_agar
21
accept rate: 0%

precisely , yes you are right . i mixed variable M with Q . thanks for the correction :)

(21 Sep '16, 00:02) arunnsit6★

I didn't understand the calculating the vector V.

what we are doing over here is pushing a node u to the vector V when we haven't discovered the subtree of u and pop it when the whole subtree is discovered .

And what is p in dfs(u,p)? Could you elaborate? Thanks.

link

answered 22 Sep '16, 22:50

fanatik's gravatar image

2★fanatik
11
accept rate: 0%

p is parent of u . And discovering means if we have already visited the node or not . I meant that if we havent visited any node in the subtree of u , then u should remain in the vector and once all the subtree nodes are visited , we have to pop u .

(24 Sep '16, 04:59) arunnsit6★

I solved it using heavy light decomposition.

Link to my solution : https://www.codechef.com/viewsolution/11338980

link

answered 22 Sep '16, 23:38

vipsharmavip's gravatar image

6★vipsharmavip
3229
accept rate: 23%

I would like to say that this is one of the most well written editorials I have ever seen. It was really clever to build the segment Tree on the basis of height and not node. No need for topological sort now.

link

answered 30 Oct '16, 17:34

siddharths067's gravatar image

1★siddharths067
8027
accept rate: 4%

thank you :)

(31 Oct '16, 01:20) arunnsit6★
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:

×2,212
×1,768
×129

question asked: 15 Sep '16, 19:51

question was seen: 4,788 times

last updated: 12 Feb '17, 21:32