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

×

CHEFPRES - Editorial

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.

This question is marked "community wiki".

asked 15 Dec '14, 19:27

pkacprzak's gravatar image

5★pkacprzak ♦♦
74485097
accept rate: 12%

edited 15 Dec '14, 19:39


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

link

answered 15 Dec '14, 20:39

divyank1's gravatar image

4★divyank1
3013
accept rate: 0%

edited 15 Dec '14, 20:46

(20 Dec '14, 15:59) thechamp1033★

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 :D

link

answered 17 Dec '14, 04:30

Amlesh's gravatar image

4★Amlesh
2393
accept rate: 0%

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.

link

answered 18 Dec '14, 00:16

guptash's gravatar image

3★guptash
1
accept rate: 0%

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.

link

answered 18 Dec '14, 01:56

pranay2063's gravatar image

3★pranay2063
40129
accept rate: 0%

edited 18 Dec '14, 01:58

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

(21 Dec '14, 15:04) amanjain1108934★

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

link

answered 20 Dec '14, 19:19

mansigupta19's gravatar image

1★mansigupta19
431418
accept rate: 0%

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

link

answered 24 Dec '14, 07:45

greendragons's gravatar image

3★greendragons
61115
accept rate: 14%

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?

link

answered 01 Sep '15, 05:40

cri1_rohit's gravatar image

0★cri1_rohit
1
accept rate: 0%

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.

link

answered 15 Jan '16, 21:57

krzysiek_t's gravatar image

3★krzysiek_t
1
accept rate: 0%

edited 15 Jan '16, 21:58

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

link

answered 12 Apr '16, 21:21

totallyred99's gravatar image

0★totallyred99
1
accept rate: 0%

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

link

answered 15 Apr '16, 20:52

tony_hager's gravatar image

5★tony_hager
412
accept rate: 0%

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.

link

answered 02 Apr '17, 15:11

danniel_parker's gravatar image

1★danniel_parker
1
accept rate: 0%

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.

link

answered 02 May '17, 18:52

bhagzi's gravatar image

2★bhagzi
1
accept rate: 0%

edited 02 May '17, 18:55

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

link

answered 04 Jun '17, 16:53

prabalv's gravatar image

3★prabalv
1
accept rate: 0%

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

(04 Jun '17, 16:58) divyansh_gaba74★

Please Help

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

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

link

answered 02 Sep '17, 02:05

kirito1412's gravatar image

2★kirito1412
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,680
×2,595
×726
×708
×228

question asked: 15 Dec '14, 19:27

question was seen: 8,662 times

last updated: 02 Sep '17, 02:05