TRIPS-Editorial

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

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
		dfs(v, adj, pt, dist, ht);
	}
}

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.

6 Likes

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.

1 Like

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.

1 Like

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.

I implemented as above tutorial , but still getting TLE. Any hints to improve my solution ? Thanks in advance submission

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…

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

1 Like

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:

There are better solutions (from a theoretical point of view) than the one presented in the editorial. I implemented (after the contest, since I didn’t participate in this contest) a simple O(sqrt(N)) per query approach with O(N*sqrt(N)) preprocessing time. The idea is quite simple. First I selected a set of special nodes. This is done as follows: choose H=O(sqrt(N)) and then mark as special all the nodes with levels multiples of H (I assumed the root had level 0), as long as the depth of their subtree is at least H (this condition doesn’t need to hold for the root of the tree, which is always selected). With this procedure we selected O(sqrt(N)) nodes of the tree. We denote the special parent of a node as the lowest ancestor which is special (excluding itself). The distance between a special node and its special parent is at least H, i.e. O(sqrt(N)).

The special subtree of a special node consists of itself and all the nodes which have it as the special parent. As mentioned earlier, the depth of such a subtree is O(sqrt(N)). For every node x in a special subtree and every value j up to the maximum length of a path in this subtree (which is at most O(2sqrt(N))=O(sqrt(N))) we compute the lowest ancestor up to which a student with strength j can travel in one day, as well as the highest ancestor at which a student with strength j needs to spend the night on his/her way to the root of the special subtree. Each such value can be computed in amortized O(1) time and there are O(N*sqrt(N)) such values computed for the whole tree.

A query is then answered by simulating the naive LCA algorithm in which we advance with the node which is deeper in the tree. However, this time we can make small jumps (move one level up) or long jumps (move to the special parent directly). Each jump can be handled in O(1) time and there are only O(sqrt(N)) such jumps.

If anyone is interested in reading more about the idea of selecting the O(sqrt(N)) special nodes, I actually wrote a paper about it some time ago.

I am interested in knowing if there are solutions which can do better than O(sqrt(N)) per query (with at most O(N*sqrt(N)) preprocessing time). If anyone implemented such a solution, then please post it.

5 Likes

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? :slight_smile:

@pushkar mishra can you please elaborate the idea behind your solution.

1 Like

@tamimcsedu19 the time limit is 8 sec so i think that would pass easily.

link to your solution please.

yes , please . the idea and logic behind binary search.

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

@tamimcsedu19: The link is already in the post (click on the word “approach”), but it’s not too visible.

@mugurelionut
i have tried to implement same approach.getting wrong answer.can you resolve it.

http://www.codechef.com/viewsolution/5159167

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