ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1569. Networking the “Iset”

What is the proper solution? (Got AC with a hack, my solution inside)
Posted by araifr 7 Nov 2018 13:19
Could anyone who solved it share the idea?

My solution was: iterate over all vertices i. Fix each i start bfs, so you get a tree (rooted in i). Find it's diameter (from the farthest node v from root i start another BFS and find the farthest node u from v. The distance from u to v would be the diameter).

Across all the diameters find the minimum, that would be the answer.

This solution got WA 8. After random_shuffle() on adjacency lists I've got WA 17.

Now repeat this solution 100 times and you get AC.

So my question is, what is the solution?
Re: What is the proper solution? (Got AC with a hack, my solution inside)
Posted by decay 7 Nov 2018 16:59
1. Find shortest paths from all vertices with Floyd-Warshall or BFSes
2. Brute force all possible tree centers. Note, that a diameter center can be either a vertex or an edge.

Basically, my solution is exactly yours while I believe you've forgotten to check edges that can form a center.

My solution is completely deterministic.

Edited by author 07.11.2018 17:03

Edited by author 07.11.2018 17:03
Re: What is the proper solution? (Got AC with a hack, my solution inside)
Posted by Harkonnen 15 Aug 2022 06:52
I just tried all vertices and all edges (meaning pushing both neighbors in priority before BFS starts), then checked tree diameter across all vertices, not just to these roots (there is O(N) algo for that). I used no Floyd-Warshall for candidates, just tried all pairs v1 <= v2, besides I am not sure Floyd will help here because original graph diameter can be shorter than that of resulting tree (e.g. see WA17 topic).