How to solve this problem using bfs?

Revision en3, by hitman264, 2021-05-14 18:47:17

I was trying this Problem — https://mirror.codeforces.com/contest/1004/problem/E and am getting a WA on Test-6.

My approach for solving this problem was to use —

  • Binary Search — For each prospective max possible distance max_, we check how many nodes we require in our path such that the max distance from this path to other non-selected nodes is <= max_. If the number of selected nodes for the path is <= k in the problem, we mark our prospective answer as a possible and return the min out of all possible answers.

The idea seems quite simple, but I am having a hard time writing the correct implementation, especially the BFS part. Here is my submission, which WAs on Test-6 — Link

I tried reading the editorial and saw that one of the folks had a binary search approach, but I am not able to understand how did he implement the bfs part. Especially this part — All nodes of degree >= 3 should be used completely in bfs — Link to the comment | Link to the submission of the folk

Thanks :D

Tags #bfs, # dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English hitman264 2021-05-14 18:47:17 94 add the part of confusion
en2 English hitman264 2021-05-14 18:44:27 1065 Tiny change: 'o use - \n* **Binary ' -> 'o use - \n- **Binary ' (published)
en1 English hitman264 2021-05-14 07:13:12 452 Initial revision (saved to drafts)