JTREE - Editorial

PROBLEM LINK:

Practice
Contest

Author: Nick
Tester: Praveen Dhinwa
Editorialist: Ajay K. Verma

DIFFICULTY:

Medium

PREREQUISITES:

Skip List.

PROBLEM:

We are given a directed tree, and a set of tickets, where each ticket has a cost associated with it, starts from a particular node, and can be used to traverse a given number of edges. The task is to answer several queries which ask about the smallest cost of reaching root from a given node in such a way that all edges are covered by a ticket, and a ticket is used only for edges forming a path.

QUICK EXPLANATION:

Traverse all nodes of the tree in topological order (root to leaves), and compute the smallest cost for each node using the smallest costs for its ancestors. This will require computing the minimum cost among the nodes lying in a directed path from a node to its ancestor, which can be computed efficiently using skip list.

EXPLANATION:

We are given a directed tree T (edges directed towards root). Each edge can be traversed in its direction and requires having a ticket. The tickets are bought from some of the nodes. Each ticket has a cost, an associated node from where it can be bought, and the number of edges on which it can be used. At any point one can carry exactly one ticket, this means a ticket can be used only on the edges which form a path from a node to one of its ancestors.

The task is to answer several queries which ask computing the smallest amount of the money that one needs to spend in order to reach root from a given node.

Suppose, we want to answer this question for node x. If there are no tickets available at node x, then of course we cannot reach root from x. On the other hand, let us assume that there are k tickets available with cost c1, c2, …, ck, and reach d1, d2, …, dk, then in order to reach root, we need to use one of these tickets. Based on this, we can actually compute the cost F(x) of the cheapest trip from x to root as follows:

F(x) = min1 <= i <= k (ci + min1 <= j <= di F(yj))
where yj is the ancestor of x at a distance j.

Hence, the overall recurrence will look like this.

F(root) = 0
F(x) = inf, if x has no tickets available
F(x) = min1 <= i <= k (ci + min1 <= j <= di F(yj))

Since the computation of F(x) used the values F(y), where y is an ancestor of x, we should compute the values F() for nodes in the order from root to leaves, so that at any point needed values are already computed.

Using this approach, we can compute the value of F() for all nodes in O (NM) time, as for each ticket, we need to look at the values of the ancestors up to distance min(d, h), where d is the reach of the ticket and h is the distance from the root to the origin of this ticket, which is bounded by N. Hence, we need to check at most O (NM) previously computed values. This approach will certainly not work on the large test cases.

If we could somehow the speedup of the computation of
min1 <= j <= di F(yj)
then, the runtime can be reduced significantly, and next we discuss how to do this using the skip list.

We want to associate a value F(x) with each node, so that the minimum of the all F() values along a path from a node to one of its ancestors can be computed fast.

For this purpose, we store a list G[1…lg N] of O (lg N) values at each node, the i-th of these values is the minimum F() value among all nodes which are ancestor of this node, and at a distance < 2i from this node. We also need to store the ancestor which is at 2i distance from this node. These ancestors are stored in another list H[1…lg N] for this node.

Using these values one can easily compute the minimum of F() values on the path from a node x to its ancestor at distance d. Supposed that
d = 2t1 + 2t2 + … + 2tr

We first look at the t1-th element in the list of the current node, which gives us the minimum of all node values which are at most distance 2t1 from this node. We also get the ancestor at 2t1 distance, which will become our new current node, and then we look for the t2-th element of the list of this new current node, and so on. This way, we compute the minimum of all 2t1 + 2t2 + … + 2tr = d values. Since there can be at most lg N terms in the binary representation of a number smaller than N, the value of r must not exceed lg N. Hence, we can compute the minimum of all d values in O (lg N) time.

Next, let us see how to compute the lists G and H for a node x.
Gx[0] = F(x), as there is a single node to consider
Hx[0] = parent(x)

In order to compute Gx[i] and Hx[i], for larger values of i, we use the following observation:

Since 2i = 2i - 1 + 2i - 1

We first look the at the first 2i - 1 ancestors of x. The minimum of F() values of these ancestors is Gx[i - 1]. and the ancestor at 2i - 1 distance is Hx[i - 1]. From this ancestor, we can get the minimum of next 2i - 1 values, which is given by GH[i - 1][i - 1]. Hence,

Gx[i] = min(Gx[i - 1], GH[i - 1][i - 1])
Hx[i] = HH[i - 1][i - 1]

This means the skip list for a single node can be computed in O (lg N) using the skip lists of its ancestors.

Hence, we have reduced the computation of
min1 <= j <= di F(yj)
to O (lg N) time.

This means the F() values of all nodes can be computed in O ((M + N) lg N) time,
which will run in time.

TIME COMPLEXITY:

O (Q + (M + N) lg N)

AUTHOR’S AND TESTER’S SOLUTIONS:

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

2 Likes

“This will require computing the minimum cost among the nodes lying in a directed path from a node to its ancestor, which can be computed efficiently using skip list.” I did this using segment tree in O(logn) per query. :smiley:

1 Like

I have also used a segment tree to find the minimum cost among the nodes from a node to the root. It turned out to be a pretty straight forward application of segment tree.

1 Like

I used jumping to next lower cost node and
distance for optimization. I optimized tickets for the nodes. My Java [solution][1] runs under 0.14 seconds.
Complexity is roughly O(Q+M+N) and in worst case O(Q+N+MlogM)
[1]: https://www.codechef.com/viewsolution/11496266

1 Like

I used the same concept but I saw it is also called jump-pointer’s.

BTW, here is the unofficial editorial which I wrote for the same problem. https://discuss.codechef.com/questions/84978/jtree-unofficial-editorial-2

1 Like

I didn’t understand this line:

Gx[0] = F(x), as there is a single node to consider

Why? and How do we calculate F(x)?

Could somebody please help?

The segtree solution is simply wonderful I randomly discovered it while lying around when contest was ongoing… i believe that’s what competitive coding is all about :stuck_out_tongue:

Hey, your solution is similar to mine. Your pre-processing of jump-pointers will take NlogN pre-processing.

@error_503_404: the jump-pointers doesn’t take NlogN for pre-processing.
every node is visited at most twice or thrice.
see the nextSmaller method in this code for simplicity. once you analyze you will know.

NlogN solution takes at-least 0.30 seconds in Java for N order of 10^5.

1 Like

Am unable to understand one thing. Do we consider all possible cases for the values of t1, t2, t3 … tr, and if not then how do we choose the values of t1,t2,… tr ? If we are to iterate over all possible values of the set {t1,t2,…,tr} then how is the complexity of finding the minimum of all d values equal to O(log n) ?

Implemented the solution as mentioned in the editorial, https://www.codechef.com/viewsolution/11692545 . If anyone else implemented the same in a better way, please do post. Would love to see it.