JTREE - Editorial

djdolls · September 16, 2016, 2:19pm

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 c₁, c₂, …, c_k, and reach d₁, d₂, …, d_k, 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) = min_{1 <= i <= k} (c_i + min_{1 <= j <= di} F(y_j))
where y_j 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) = min_{1 <= i <= k} (c_i + min_{1 <= j <= di} F(y_j))

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
min_{1 <= 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 < 2ⁱ from this node. We also need to store the ancestor which is at 2ⁱ 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 = 2^t1 + 2^t2 + … + 2^tr

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 2^t1 from this node. We also get the ancestor at 2^t1 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 2^t1 + 2^t2 + … + 2^tr = 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.
G_x[0] = F(x), as there is a single node to consider
H_x[0] = parent(x)

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

Since 2ⁱ = 2^{i - 1} + 2^{i - 1}

We first look the at the first 2^{i - 1} ancestors of x. The minimum of F() values of these ancestors is G_x[i - 1]. and the ancestor at 2^{i - 1} distance is H_x[i - 1]. From this ancestor, we can get the minimum of next 2^{i - 1} values, which is given by G_{H[i - 1]}[i - 1]. Hence,

G_x[i] = min(G_x[i - 1], G_{H[i - 1]}[i - 1])
H_x[i] = H_{H[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
min_{1 <= 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.

mightymercado · September 16, 2016, 5:19pm

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

mihassan · September 16, 2016, 6:17pm

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.

ashok1113 · September 16, 2016, 10:40pm

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

error_503_404 · September 17, 2016, 11:51am

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

error_503_404 · September 17, 2016, 11:56am

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

ashok1113 · September 17, 2016, 3:01pm

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

github.com

AshokRajpurohit/karani/blob/master/src/com/ashok/lang/utils/Utils.java

package com.ashok.lang.utils;

import java.util.Arrays;
import java.util.Comparator;
import java.util.stream.IntStream;

/**
 * @author Ashok Rajpurohit ([email protected]).
 */
public class Utils {
    /**
     * Returns array of next higher element index.
     * At index i the array contains the index of next higher element.
     * If there is no higher element right to it, than the value is array size.
     *
     * @param ar
     * @return
     */
    public static int[] nextHigher(int[] ar) {
        int[] res = new int[ar.length];

This file has been truncated. show original

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

bhavesh_munot · September 29, 2016, 9:14am

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?

mjnovice · September 29, 2016, 5:40pm

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

mjnovice · October 3, 2016, 11:48pm

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.

yvetal_1 · March 31, 2017, 7:53pm

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