SPCWAR IUPC Editorial

editorial
, ,
1

PROBLEM LINK:

SPCWAR The Space War IUPC Plinth 2020

Author: Kabeer27

Editorialist: Kabeer Seth

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Connected Components, BFS, Diameter of Tree

PROBLEM:

Optimally place source points of information in each of the connected components to obtain minimum time.

EXPLANATION:

Find all the connected components and then in each connected component place your source node as the center of the diameter, the time taken to spread will be diameter/2 for each connected component, now just compute the maximum of all the diameter/2.

The center of the diameter will be the most optimal point as the longest possible path in any connected component will be the diameter, if we choose any other points it will take more than diameter/2 time.

AUTHOR’S SOLUTION:

Author’s solution can be found here .

2 Likes
2

It was bad to inform late that the resulting graph didn’t have cycles. We knew that finding center for graphs can be O(n^3), so we left such a straightforward problem till it was resolved. Surprisingly, some teams solved it before resolving :joy:

1 Like
3

Yeah that was unfortunately missed out, later resolved sorry for the inconvenience.

1 Like
4

got TLE using exactly same approach in java
https://www.codechef.com/viewsolution/28761873
were time multiplier applicable ?

5

I think you meant \left\lceil diameter / 2 \right\rceil everywhere.

1 Like
6

i am unable to submit my solution

7

Why is my code giving WA ??

Thanks :slight_smile:

8

It is not optimal to start with the node with the highest outdegree.

Counter Case:

10 9
1 2
1 3
1 4
1 5
4 6
6 7
7 8
8 9
9 10

2 Likes