PROBLEM LINK:Author: Sergey Kulik DIFFICULTY:MediumHard PREREQUISITES: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 N^{0.5} are kept in the first class, while the remaining queries are kept in the second class. There is some common preprocessing that we need to do for the queries of both classes. Let us first discuss this preprocessing step. First, we make the tree rooted, and maintain the following information for each node: 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 preprocessing, while the queries of the second class can be handled without any additional preprocessing. 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 preprocessed 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 >= N^{0.5}, number of steps cannot be higher that N^{0.5}. Hence, the complexity of move_up is O (N^{0.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); 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 (N^{0.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 N^{0.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 2^{j} 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 (N^{1.5} lg N) Query time: O (N^{0.5} lg N) AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution will be put up soon.
This question is marked "community wiki".
asked 13 Oct '14, 15:02

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. answered 15 Oct '14, 07:17
link to your solution please.
(15 Oct '14, 15:15)
@tamimcsedu19: The link is already in the post (click on the word "approach"), but it's not too visible.
(16 Oct '14, 02:46)
@mugurelionut
(17 Oct '14, 10:49)

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

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

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 n1 and n total vertices therefore there will be n2 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/wronganswerinchildrentripsincodechefoctoberchallenge answered 14 Oct '14, 22:20

@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 . answered 16 Oct '14, 01:17

Why my program was showing NZEC here,pls help. link to solution : http://www.codechef.com/viewsolution/5128189
link
This answer is marked "community wiki".
answered 13 Oct '14, 15:19

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