I was trying this Problem — https://codeforces.me/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](https://codeforces.me/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.↵
Especially this part — **All nodes of degree >= 3 should be used completely in bfs**↵
— [Link to the comment](https://codeforces.me/blog/entry/60443?#comment-442943) | [Link to the submission of the folk](https://codeforces.me/contest/1004/submission/40004166)↵
↵
Thanks :D
↵
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](https://codeforces.me/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.↵
Especially this part — **All nodes of degree >= 3 should be used completely in bfs**↵
— [Link to the comment](https://codeforces.me/blog/entry/60443?#comment-442943) | [Link to the submission of the folk](https://codeforces.me/contest/1004/submission/40004166)↵
↵
Thanks :D
