×

# TRIPS-Editorial

Author: Sergey Kulik
Tester: Jingbo Shang
Editorialist: Ajay K. Verma

Medium-Hard

# PREREQUISITES:

Lowest Common Ancestor

# PROBLEM:

We are given a tree with edge weights belonging to {1, 2}. We need to handle the queries of the following form: given two nodes u and v in the tree, and and integer c, find the minimum number steps needed to reach from u to v, where in each step a maximum distance of c unit can be covered.

# EXPLANATION:

We divide the queries into two classes based on the value c. The queries for which c is smaller than N0.5 are kept in the first class, while the remaining queries are kept in the second class.

There is some common pre-processing that we need to do for the queries of both classes. Let us first discuss this pre-processing step.

First, we make the tree rooted, and maintain the following information for each node:
1) distance of this node from root (stored in array dist[1..N])
2) number of nodes in the path from root to this node (stored in array ht[1..N])
3) 2k -th successor of this node, for all 0 <= k <= lg N (stored in array pt[1..N][0..lg N])

The three arrays can be computed easily using a depth first traversal of the tree.

void dfs(int u, int **adj, int **pt, int *dist, int *ht) {
// special case for root
if (pt[u][0] == -1) {
dist[u] = 0;
ht[u] = 0;
}

for (int v : adj[u]) {
if (v == pt[u][0]) continue;

// update child's data
dist[v] = dist[u] + wt(u, v);
ht[v] = 1 + ht[u];
pt[v][0] = u;

for (int i = 1 to lg N)
pt[v][i] = pt[v][i - 1] == -1 ?
-1 : pt[pt[v][i - 1]][i - 1];

// recursion
}
}


Using the above information, the lowest common ancestor of two nodes u and v can be computed easily as shown below:

// Assumes that ht[u] >= ht[v]
int lca(int u, int v, int **pt, int *ht) {
// Move from u to its ancestor,
// until it is at the same level as v
for (i = lg N to 0) {
if (pt[u][i] == -1) continue;
if (ht[pt[u][i]] >= ht[v])
u = pt[u][i];
}

// At this point ht[u] and ht[v] must be equal
if (u == v) return u;

// move simultaneously u and v towards root,
// until they merge
for (i = lg N to 0) {
if (pt[u][i] != pt[v][i]) {
u = pt[u][i];
v = pt[v][i];
}
}
return pt[u][0];
}


In order to handle the queries of first type, we need to some additional pre-processing, while the queries of the second class can be handled without any additional pre-processing.

Let us first discuss how to handle the queries of the second class.

## Queries with Large Value of c:

For the second kind of query, compute the lowest common ancestor w of nodes u and v, and then compute the number of steps to reach from u to w, and the number of steps to reach from v to w. This can be done using the pre-processed data computed in the previous section.

// returns the ancestor node of u that will be reached
// in a single step from u.
int single_jump(int u, int c, int *dist, int **pt) {
int st = dist[u];

for (int i =  lg N to 0) {
int v = pt[u][i];
if (st - dist[v] > c) continue;

// move to v, if distance between u and v
// does not exceed c
u = v;
}
return u;
}

// moves up from u to w, returns the following two values:
// 1) the number of steps taken to reach the closest
// successor of w from u, such that the next step will take
// us beyond w.
// 2) the distance between w and this closest successor
// of w.
struct info {
int num_steps;
int dist_remaining;
};
info move_up (int u, int w, int c, int **pt, int *dist, int *ht) {
int num_steps = 0;
int dist_remaining = 0;

while (u != w) {
// Use a single step
int tmp = single_jump(u, c, dist, pt);
if (ht[tmp] > ht[w]) {
// we are still below w
++num_steps;
u = tmp;
} else {
// we cannot take this step, otherwise
// we will move beyond w
dist_remaining = dist[u] - dist[w];
break;
}
}
return info{num_steps, dist_remaining};
}


Note that the complexity of single_jump is O (lg N), while the complexity of move_up depends on the number of steps taken to reach from u to w. Since the value of c is >= N0.5, number of steps cannot be higher that N0.5. Hence, the complexity of move_up is O (N0.5 lg N).

In a similar way, we can compute the number of steps taken to reach from v to w, and the remaining distance that we need to cover to reach w.

I1 = move_up(u, w, c, pt, dist, ht);
I2 = move_up(v, w, c, pt, dist, ht);

Now, we have taken (I1.num_steps + I2.num_steps) steps and we still need to cover (I1.dist_remaining + I2.dist_remaining) distance. This will require ceil ((I1.dist_remaining + I2.dist_remaining) / c) additional steps.

Hence, the queries of the second class can be handled in O (N0.5 lg N) time.

## Queries with Small Value of c:

Unfortunately, we cannot use the above approach for handling the queries of first class, as the number of steps to reach from u to w can be as large as O (N).

However, in this class there are only N0.5 distinct values of c, so we can do some preprocessing that can be used to process multiple jumps in O (1) time.

More formally for each value of c, we create an array P[1..N][0..lg N] such that P[i][j] denote the ancestor node of i that can be reached after making 2j jumps from i.

The array P[][] can be computed using a depth first traversal, in the same way as the array pt[][] was computed. Now using the array P, we can compute the number of steps to reach from u to w in O (lg N) time.

info move_up (int u, int w, int c, int **pt, int *dist, int *ht, int **P) {
int num_steps = 0;

for (int i = lg N to 0) {
int tmp = P[u][i];
if (ht[tmp] > ht[w]) {
// we are still below w
num_steps += 2^i
u = tmp;
}
}
return info{num_steps, dist[u] - dist[w]};


# Time Complexity:

Preprocessing time: O (N1.5 lg N) Query time: O (N0.5 lg N)

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution will be put up soon.
Tester's solution will be put up soon.

This question is marked "community wiki".

6★djdolls
2.2k508484
accept rate: 0%

19.0k348495531

I implemented the approach given in the editorial and got an AC! :D The author's and tester's solution have not been put up yet, in case anyone wants to learn, here is the AC submission

(23 Oct '14, 17:30)

 1 For small value of C , there can be 317 distinct value of c and lg(n) is 17, so total 17 * 317 * 10^5=(538900000*4) , that is 220 Megabyte of storage. Shouldn't that be MLE or TLE or something. I don't see the memory limit option in the contest page. answered 13 Oct '14, 15:54 366●2●6●11 accept rate: 0% 1 Right, but you can sort the queries according to the c values, and handle the queries with the same c at the same time. That means you need to store the array P[][] only for a single c, and not for all 317 values. (13 Oct '14, 15:56) djdolls6★ But still , I have to do 538900000 i.e , const*5.3 * 10^8 operations. Thats very in tight constraints though. Thanks for the nice editorial. (13 Oct '14, 16:10) @tamimcsedu19 the time limit is 8 sec so i think that would pass easily. (15 Oct '14, 15:11)
 1 The queries can be answered online using heavy-light decomposition and precomputing queries less than sqrt(n). This method requires n*sqrt(n) memory. http://www.codechef.com/viewplaintext/5148741 answered 14 Oct '14, 20:15 1.3k●15●63●81 accept rate: 4% 1 @pushkar mishra can you please elaborate the idea behind your solution. (15 Oct '14, 15:07) yes , please . the idea and logic behind binary search. (15 Oct '14, 15:17)
 0 I implemented as above tutorial , but still getting TLE. Any hints to improve my solution ? Thanks in advance submission answered 13 Oct '14, 19:02 366●2●6●11 accept rate: 0%
 0 Any chance to share the test case ? I got NZEC (Java) after 30s...On my PC I tried millions of random cases, and never achieved NZEC... answered 13 Oct '14, 23:42 6★beroul 131●3 accept rate: 6% I had a similar problem with my submissions. Random maxed trees worked like a charm. The test case which caused me trouble was simple: a chain of 100000 nodes (1)--(2)--(3)--(4)--...--(100000). Could that be your bane too? :-) (15 Oct '14, 08:18) spoirier2★
 0 I tried with adifferent logic alltogether but got wrong answer.Can somebody tell me whats wrong with my solution.: as the number of edges are n-1 and n total vertices therefore there will be n-2 vertices with degree two and 2 vertices with degree 1(which will be two end points).What I did is that i created 4 arrays of size n,two of which will store value of next vertex from that vertex,and other two will store the weight on the edges to that vertex .Now I will discover the start and end vertex as they will only have degree 1 by using the input .Once i get start point i will traverse on the only path it has to the end point storing the next vertex and weight of edge .now whenever I get the query i simply have order path stored in the arrays and now i just traverse the array and get my result. link: http://stackoverflow.com/questions/26365543/wrong-answer-in-children-trips-in-codechef-october-challenge answered 14 Oct '14, 22:20 1 accept rate: 0%
 0 @all Can Anyone please have a look on my code . My code is working fine according to me. I have coded it twice but i am not able to get why it is giving WA i have implemented what exactly mention in the editorial. If someone can help me . http://ideone.com/h1h04T answered 16 Oct '14, 01:17 1 accept rate: 0%
 -2 Why my program was showing NZEC here,pls help. link to solution : http://www.codechef.com/viewsolution/5128189 import sys sys.setrecursionlimit(100002) n = int(raw_input()) p = {} g = [{}] for i in range(0,n+1): g.append({}) for tt in xrange(1,n) : x,y,z = raw_input().split() x = int(x) y = int(y) z = int(z) p[y] = x g[x][y] = z g[y][x] = z m = int(raw_input()) for tt in xrange(m) : x,y,z = raw_input().split() x = int(x) y = int(y) z = int(z) path = (y,) while True : if y in p : path = path + (p[y],) y = p[y] else : break if y == x : break if not x in path : pr = (x,) while True : if not p[x] in path : pr = pr + (p[x],) x = p[x] else : break pi = () for each in path : if p[x] == each : pi = (each,) + pi break else : pi = (each,) + pi path = pr + pi days = 1 df = z for each in xrange(len(path)-1) : a = g[path[each]][path[each+1]] if z >= a : z = z-a else : z = df days += 1 if z >= a : z = z-a print days  link This answer is marked "community wiki". answered 13 Oct '14, 15:19 40●1●3 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×14,366
×1,089
×319
×201

question asked: 13 Oct '14, 15:02

question was seen: 4,012 times

last updated: 27 Oct '14, 13:51