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

×

TRIPS-Editorial

6
4

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.

This question is marked "community wiki".

asked 13 Oct '14, 15:02

djdolls's gravatar image

6★djdolls
2.2k518484
accept rate: 0%

edited 27 Oct '14, 13:51

admin's gravatar image

0★admin ♦♦
19.3k348495534

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

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.

link

answered 15 Oct '14, 07:17

mugurelionut's gravatar image

7★mugurelionut
10.0k266990
accept rate: 18%

link to your solution please.

(15 Oct '14, 15:15) tamimcsedu193★

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

(16 Oct '14, 02:46) mugurelionut7★

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

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

(17 Oct '14, 10:49) antim_patel1★

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.

link

answered 13 Oct '14, 15:54

tamimcsedu19's gravatar image

3★tamimcsedu19
3662711
accept rate: 0%

edited 13 Oct '14, 15:55

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

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

(15 Oct '14, 15:11) neo1tech9_76★

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

link

answered 14 Oct '14, 20:15

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156481
accept rate: 4%

1

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

(15 Oct '14, 15:07) ma5termind3★

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

(15 Oct '14, 15:17) tamimcsedu193★

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

link

answered 13 Oct '14, 19:02

tamimcsedu19's gravatar image

3★tamimcsedu19
3662711
accept rate: 0%

edited 13 Oct '14, 19:16

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

link

answered 13 Oct '14, 23:42

beroul's gravatar image

5★beroul
1313
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★

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

link

answered 14 Oct '14, 22:20

hemantjain75's gravatar image

2★hemantjain75
1
accept rate: 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

link

answered 16 Oct '14, 01:17

super_sonic's gravatar image

2★super_sonic
1
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:

×15,006
×1,161
×319
×227

question asked: 13 Oct '14, 15:02

question was seen: 4,083 times

last updated: 27 Oct '14, 13:51