I tried very hard to solve this problem but couldn’t clear all the test cases. I got AC for all test cases except 10th test case. Can anybody help me out?
Here is the link to my code.
use binary search and dfs!(check this give true condition)
Even my obviously wrong solution passed all test cases except the 10th. I have solved a similar problem before but I cannot think of a test case at the moment(Sorry :(, hope someone helps you out with that). Taking just r/2 is wrong(As far as I can think of). Also, dfs does not give the shortest distance between two nodes in a graph, that might also cause WA(I used bfs).
In case you want to consider a different solution what you can do is binary search on the value of r. If taking the current r, you can make the dons stay happily then you can take a bigger(or the same) r, or else you need to lessen your r(All values about this value of r are invalid). The runtime if O(NlogN), O(N) because of each dfs to check if the current r is suitable or not, and O(logN) because of the binary search.
1 Like
Can you tell why taking r/2 is wrong?
l=1 and r=100001 now mid=(l+r)/2 and then check can or not…
goodby
I did it using binary search only, check my solution below 
All I asked is why is taking r/2 wrong(Take a look at his code).
better you change your code and get it clear 
just you need a binary search in main and a dfs and a visited array and a count in dfs for count number of visited if condition finally is true.
if you use clear code …you can find your mistake!
Solved it using multisource BFS. Initialize a visited array for nodes with -1 and add all nodes with dons to a queue and change their visited value to 0. So now for every node in queue add all nodes to queue till you reach a phase where you encounter an already visited node. This means that it was already occupied by other don. So this is the breaking condition. Also while adding a node to queue I’m deleting the edge between the parent node and child node so that we will not travel back to parent from child and also change the visited value of child node to the depth. So the answer will be the number of nodes less than the depth at which the visited node is revisited. I tried to explain my approach. Please comment if you find anything wrong.
6 Likes
@tayal007, your intention was correct but your solution was not. I am surprised your solution passed almost all the test cases. Fortunately, there are only a couple of changes that will make your solution correct 
So the algorithm to be followed is: for each don vertex, find the nearest don vertex; the distance between the closest pair of don vertices is 2 times the answer.
The first mistake is that you are using dfs. Dfs does not guarantee that the shortest path from source will be followed. For example, in the graph below dfs may take the shown path from vertex 1 to 4, which is not what you want. You need to be using bfs instead.
The second problem you will face after implementing bfs is with your visited array. For each bfs you need to reset your visited array otherwise the bfs will not always manage to find the closest don if it encounters a vertex marked visited on the way. You also cannot actually reset your visited array to false each time, because in the worst case that will be \mathcal{O}(N^2). You can overcome this by using a different value to mark the visited vertices for each bfs.
I solved the problem using this approach. Here is my solution. Hope this helps!
The worst case for this solution is below. The dons are marked with orange. Let x be some constant. Then there will be N/x bfs, and each bfs will take \mathcal{O}(N) to reach the closest don. So complexity is \mathcal{O}(N^2/x) \approx \mathcal{O}(N^2). So this should not be able to clear the time limit, but clearly the test cases are weak.
PS: See @sai_rathan’s answer using multisource bfs, it seems that is the most efficient way.
Your solution is also taking indefinite time… to solve worst test case generated by this file https://ideone.com/RVcJyU . Please look into it… Please explain your approach too…
1 Like