How to solve this problem using bfs?
Difference between en1 and en2, changed 1,065 character(s)
Prelude-↵

Before people start bashing me, I just wanted to say that the problem is highly rated(2400), so would be too much for me to solve.↵

However, after spending a day on it :p , I figured out that I can binary search on the answer by taking a prospective number as the maximum and check if we can form a path using <=k nodes as the path, while the Mac distance from this path would be <= prospective answer.
I was trying this Problem &mdash; https://codeforces.net/contest/1004/problem/E and am getting a WA on Test-6.↵

My approach for solving this problem was to use &mdash; ↵

-  **Binary Search** &mdash; 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 &mdash; [Link](https://codeforces.net/contest/1004/submission/116194105)↵

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. &mdash; [Link to the comment](https://codeforces.net/blog/entry/60443?#comment-442943) | [Link to the submission of the folk](https://codeforces.net/contest/1004/submission/40004166)↵

Thanks :D

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)