CHEFPRES - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Kamran Maharov
Tester 1: Minako Kojima
Tester 2: Shiplu Hawlader
Editorialist: Pawel Kacprzak

DIFFICULTY:

MEDIUM

PREREQUISITES:

Trees, dfs

PROBLEM:

You are given a tree of N nodes and a special node B. Each node v has asocciated an unique integer, let’s denote this integer by f(v). Your task is to provide an answer for each of q following queries. A single query consists of two integers, A and P. Let D(v) denotes the minimum distance between the unique path from A to v in the tree i.e. the minimum distance between A and any node on the path. The answer for a single query (A, P) is a node v for which f(v) = P and D(v) is minimum among all such nodes. If there is more than one such node, you should return the one with minimum number.

QUICK EXPLANATION:

Root a tree in B using dfs. During this dfs compute dp[v][c] := minimum node u in v’s subtree for which f(u) = c or INF if there is no such node.

Using second dfs, for each v and c, compute ans[v][c] := dp[u][c] where u is the first node on the path from v to B for which dp[u][c] != INF or -1 if no such node exists

For each query (A, P), return ans[A][P].

EXPLANATION:

The method mentioned in quick explanation is straightforward, but let’s take a look why it works.

Consider a single query (A, P). Let dist(u) be a distance from node u to the root of the tree, i.e. to node B. Let’s assume that the result for this query is a node v. Then D(v) <= dist(A), because A is the first node of the path to v. Since we are looking for a v for which D(v) is maximal, the best thing we can do is to search for it in A’s subtree, because if there exists a v in that subtree for which f(v) = P, then D(v) = dist(A) and we cannot do better. If there is no such v in A’s subtree, we search (based on the same argument) for the next greatest value of D(v) in a subtree rooted in the parent of A. We continue this process unless we find v, for which f(v) = P or we reach node B. If we reach B and doesn’t find a node v for which f(v) = P, the answer is -1.

In order to do that, we compute dp[v][c] := minimum node u in v’s subtree for which f(u) = c or INF if there is no such node.

If implemented naively, that method has O(n^2) running time, which may pass here, but we can do better.

Using the second dfs, for each v and c, compute ans[v][c] := dp[u][c] where u is the first node on the path from v to B for which dp[u][c] != INF or -1 if no such node exists. This is similar to path compression in union-find data structure.

Using ans table, we can answer any query in O(1) time.

Time Complexity:

Time complexity is O(N * K) because for each K, we visit every edge a constant number of times during precomputational phase and we answer each query in constant time.

AUTHOR’S AND TESTER’S SOLUTIONS:

To be uploaded soon.

RELATED PROBLEMS:

To be uploaded soon.

2

We can also use a simple observation that value of G(i) while going from city u to v will be always equal to the distance of LCA(u,v) from the root of the tree(king city) which can be precomputed using BFS from root.

So while going from city u to buy a product P we will store all possible values of G(i).
The target_G(i) will be the maximum amongst all G(i)'s.

So if target_G(i) appears multiple times we’ll simply print the city with lowest index otherwise the one that is contributing to target_G(i)

C++ Implementation

3 Likes
3

Alternatively any sub-quadratic implementation of precomputing the LCAs of the tree (rooted at B as mentioned above) suffices. Here’s an awesome article on all the different ways this can be achieved: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

Going for simplicity, the < O(N log N), O(log N) > implementation (i.e. O(N log N) pre-computation and O(log N) query) easily suffices for the given bounds.

Great problem btw :smiley:

1 Like
4

Can someone find the error in this code
http://www.codechef.com/viewsolution/5611889.
The approach is very similar to the one given in the editorial above.

5

My soultion is based on finding BFS from the root and then finding distance of LCA of chef city and other city ,from the root.This is giving TLE.

Here is my solution.

But, a similar got accepted as commented by divyank above.
What can be wrong in my code? Both the solution are nearly same.

6

My C++ implementation is :
http://www.codechef.com/viewsolution/5575749

7

I don’t know why so many DP based solutions this time in the challenge! :confused: Our editorialist must be great at it.

8

Similarly, I can’t understand why my O(n*n) solution is getting TLE
http://www.codechef.com/viewsolution/5625973

9

Gives good running time without 2nd DFS, just use the union-find path compression trick per query… performs better in amortize terms.

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

10

Hey, in the test case of the problem “Chef Under Pressure” the last input is “8 4” , which means that the chef will stay in the city number 8 and want product number 4. The city 8 itself has product 4 so he need not move to any other city to get it. But the output states that he should go to city number “4” to get it. Why is it so?

11

Can you provide data set for the first test?

I’m getting WA for this case and really don’t know how can it be. I have correct results for all other tests in the first group and time-limit-exceeded for all tests in the second group.

12

@krzysiek_t -same here;

could anyone please provide what could be the first test case;

and also I’m getting time limit exceeded in the second sub task, could anyone please elaborate how it could be?

Thanks!

13

I looks like no one has a solution that gets the first test case right?

14

can You please write full forms of all uncommon abbriviations like dp[][] and INF and so on.
Sorry if it’s basic but i am a bt new.

15

Hi All,

I think there is an ambiguity in the question given and the problem explained above:

PROBLEM EXPLANATION GIVEN ABOVE:

“Let D(v) denotes the minimum distance between the unique path from A to v in the tree i.e. the minimum distance between A and any node on the path.”

QUESTION GIVEN IN THE ACTUAL PROBLEM:

suppose Chef will be living in the city A. For each city i, let G(i) be the smallest distance between B and any city on the unique path connecting cities A and i.

The question talks about the minimum distance between B and any city on the unique path. Whereas the explanation above says minimum distance between A and any node on the path.

I would like to know where the error is. In the question or the explanation provided above. As answer depends a lot on the comprehension.

@pkacprzak it would be great if you clarify on the same. Thanks in advance.

16

Can anyone please provide the first test case, I am getting wrong answer for it?

17

I don’t think they give out test cases for problems. If you can’t figure out the problem, post your code and ask your queries here :https://discuss.codechef.com/questions/97820/i-want-to-ask-a-question-ask-them-all-here

18

Please Help

i hv a solution for this problem which i think is right but when i submit it,codechef says it is wrong :confused:

my code : https://www.codechef.com/viewsolution/15204266

my Approach : i used a bfs to find the shortest path between any 2 nodes,then for all nodes which have the required product i retrace its path to ‘A’ . while retracing i calculate the shortest distance of tht unique path from the capital,then i compare all such distances and output the path with max distance from capital

please Help

P.S i got the example question right