HLPCHF Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Dhananjay Raghuwanshi
Tester: Felipe Mota, Abhinav Sharma
Editorialist: Pratiyush Mishra

DIFFICULTY:

2859

PREREQUISITES:

Trees

PROBLEM:

Chef is the king of the kingdom named Chefland. Chefland consists of N cities numbered from 1 to N and (N-1) roads in such a way that there exists a path between any pair of cities. In other words, Chefland has a tree like structure.

Out of the N cities in Chefland, K (1 \leq K \leq N) are considered tourist attractions.

Chef decided to visit exactly (K-1) out of K tourist attractions. He wishes to stay in the city i (1 \leq i \leq N) such that the sum of distances of the nearest (K-1) tourist attractions from city i is as minimum as possible.

More formally, if Chef stays at city i and visits (K-1) tourist attractions denoted by set S, then, the value \sum_{j \in S} D(i,j) should be minimum.
Here, D(i,j) denotes the distance between cities i and j which is given by the number of roads between cities i and j.

Find the city in which Chef should stay. If there are multiple such cities, print the one with the largest number.

EXPLANATION:

This problem can be divided into two separate problems:

  • Calculate, for each node, sum of distances of tourist locations from it.
  • Calculate, for each node, maximum distance of a tourist location from it.

Assume S' to be the set of all tourist locations.
Lets talk about the first problem now. Assume a function f\_sum , such that:

f\_sum[i] = \sum_{j \in S'} D(i,j)

In order to calculate it we introduce another function f\_subtree where f\_subtree[i] tells us the number of tourist locations in the subtree of i.

We can calculate f\_sum[1] using DFS. For other nodes we can do another DFS and use the following relation

f\_sum[child] = f\_sum[parent] + (k - f\_subtree[child]) - f\_subtree[child]

This concludes with our problem one. Now moving on to the 2nd part of the problem.
Lets introduce another function f\_max such that

f\_max[i][0] = maximum \; distance \; of \; tourist \; location \; within \; subtree \; of \; i.
f\_max[i][1] = maximum \; distance \; of \; tourist \; location \; outside \; subtree \; of \; i.

Now we can run a DFS and for any node and its child, if f\_subtree[child] > 0 then

f\_max[node][0] = max(f\_max[node][0], f\_max[child][0] + 1)

Thus we would get first part of the function. For the 2nd part i.e to calculate f\_max[node][1], we run another DFS, where for any node and its child, let us take another set C which denotes all children of node other than child, then

f\_max[child][1] = max(f\_max[node][1], max(f\_max[c][1], where \; c \in C ))

Now that we solved both these problems individually, we can get back to our original problem. If we assume the required sum of distance for each node i is answer[i], then

answer[i] = f\_sum[i] - max(f\_max[i][0],f\_max[i][1])

Now we can loop through to find the maximum i with minimum value of answer[i].

TIME COMPLEXITY:

O(Nlog(N)) for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

2

How is this O(N\log(N)) and not just O(N) ?

I feel like I did exactly the same thing but using a rerooting approach (compute the answer with the root at 1, then do a DFS to move the root and recompute the answer each time we move the root along an edge).

It passed samples but no test so I wonder what’s wrong, can someone tell ?
https://www.codechef.com/viewsolution/63344312
The code can look a bit big but is actually not so much, only the rerooting has 2 copy paste of 8-lines blocks.

3

Because you can use a multiset for computing the value of the farthest tourist attraction node distance, and insert and erase operations for a multiset take \mathcal{O}(\log N) time.

PS: We can do this in linear time as well by maintaining the parent contribution recursively.

Also there I think in the editorialist’s a multiset should be used instead of a set to handle duplicates My Solution

4

But can’t you do it recursively just storing the value of the farthest tourist for each node and taking max on children (see what I tried in my submission) ?

5

Your solution fails for this.

1
2 1
2
1 2
6

Thanks, I saw where the issue was with this and fixed it, but it still doesn’t pass ^^
But nevertheless why do you think just using max values and updating recursively fail ?

7

It won’t fail if done correctly, I was just highlighting what the editorialist’s solution did, I edited my previous post to clarify that.

Also, your latest submission fails for this.

1
4 2
2 3
1 4
3 2
2 4

Correct output is 3

8

Ok thanks for clarification.

Oh I see I did a very dumb mistake updating the answer only if the index was also bigger than previous answer’s one. Still WA though…
I will try stress testing on my own thanks for the help.

9

Yeah, I edited the previous post, seems like test cases are weak as many solutions which fail this test case also got an AC.

10

Oh that’s bad x) Is the last one you submitted right so I can use it for stress testing ?

11

My O(n) solution : CodeChef: Practical coding for everyone. (If Anyone finds a failing test for it , please do reply to me )

12

Yes, It’s correct you can use this solution for stress testing.

13

Fails for this

1
3 2
1 2
2 1
1 3

The correct answer is 2.

I’m afraid test cases are incredibly weak, I wrote solutions that failed for 100s of trivial test cases and they still passed.

14

Oh, thanks :slight_smile:
Yeah the testcases look really weak.

15

Hi everyone, you can check my O(n) solution:
https://www.codechef.com/viewsolution/63354857
I used re-rooting to find the sum of distances of all special nodes, and to find the furthest special node, I used the same approach of finding the diameter of the tree.

1 Like