PROBLEM LINK:
Author: Nick
Tester: Praveen Dhinwa
DIFFICULTY:
Medium
PREREQUISITES:
PROBLEM:
Given an diredted tree of “N” nodes, such that from every vertex we can reach vertex “1”, the capital city.
For every vertex, we are also given the cost of travelling from the vertex to any vertex which is within a distance of “k” from it.
You are given “Q” Queries. For every query, output the minimum cost to reach from the given vertex to vertex “1”.
QUICK EXPLANATION:
First preprocess the lca. Store the minimum value of path for every path of length {2}^{i} using jump pointers-technique.
Formulate the dp states and use imformation from the pre-calculated values to get the optimal answer for all vertices.
Once, the answers for all vertices is calculated, queries can be done in O(1).
EXPLANATION:
Assuming 1-based indexing everywhere.
Let us first solve a simpler version of the problem. Consider the problem in 1-D array, instead of a tree.
Now suppose, you want to calulate the answer of every index, where from index i, you can go to index max(1, i - k).
This is a standard DP problem with following recurrence:
for(int i=1; i<=n; ++i) {
dp[i] = INF; //some large value
for(int j=i-1; j>=max(1, i-k); --j) {
dp[i] = min(dp[i], dp[j] + cost[i]);
}
}
Presently, this “dp” calculation takes O({n}^{2}) complexity. Let us first try to optimise this calculation.
For every index, we need to find the minimum value of dp[i] in the range [max(1, i-k), i-1].
This thus can be done using a segment tree or using the concept of Jump-pointers.
Basically for every index before doing the calculation, we preprocess all the minimum at index “i” of array, such that the length of the interval is {2}^{x} for some possible values of x.
The concept is similar to the pre-procesing done while building the spare table or lca table.
For calculating the {2}^{x} minimum from index “i”, we consider 2 cases:
- Either the minimum lies in {2}^{x-1} range from index “i”.
- Or the minimum lies in {2}^{x-1} range of index which is at a distance of {2}^{x-1} from index “i”.
Thus to find the minimum in a length of {k}, we use the concept of jump-pointers or binary-jumping. We find the answer for the {2}^{x} bit which is set in {k} and jump to the {2}^{x} index from the present one. We continue this process till we process the the bits which were set in k.
Now, moving towards the original problem.
We store the transpose of the graph as given in the problem. First of all we pre-process the depth of every vertex from the node “1”. Then we do the pre-processing for LCA. This will be used to jump to a vertex at a distance of {2}^{x} from the given vertex.
Now consider the dfs traversal of the tree starting from vertex “1”. For every node, we first find the minimum starting at that node and having a path pf length {2}^{x}, for possible values of x.
Then for that vertex we consider all the tickets available at that vertex. Then 2 cases arise :
- The depth of the vertex is less than the maximum distance we can travel by using the ticket. In such a case the answer is simply “cost[ticket]”
- The depth of the vertex is more than the maximum distance we can travel by using the ticket. In such a case, using the “dp” relation similar to the 1-D array case we, find the minimum value of “dp” of all the nodes which lies at a distance of “k” form it. This can we done using jump pointers and lca as explained before. The answer for this will be min({dp[i]}_{for all possible i's}) + cost[ticket].
Thus we get the best cost of all vertex “i” from the minimum of the above 2 cases for all the tickets present at that vertex.
PseudoCode :
dp[v] = INF, for all v.
dp[1] = 0, base case
dfs(vertex u) :
for every vertex v directly reachable from u :
update the minimum array for vertex v, for every possible 2^x
for all tickets :
if depth[v] < tickets.distance :
dp[v] = min(dp[v], ticket.cost)
else :
dp[v] = min(dp[v], dp[max(1, i-k)] ... dp[i-1]) + ticket.cost)
//max is calculated using jump pointers & lca
dfs(v)
If you have any doubts, you can ask below.
TIME COMPLEXITY:
LCA pre-processing is O(n logn) where {n} is number of vertices in tree.
Jump pointer’s, minimum processing during DFS is O(n log n).
Ticket’s answer calulation is O(m log(n)), where m is number of tickets, and log(n) due to the pointer jumping which can be {n} in worst case (Linear tree).
Overall : O((n + m) logn)