Can anybody explain how does the radius of search become half ?
Can we transform the initial graph into minimum spanning tree and using dynamic programming to figure out the minimum distance between two special nodes?I’ve tried that but get WA and I cannot think of any test case that can prove my idea is wrong.Can you guys please help me?
Editorialist’s program gives 1 as output. Please refer to it as it follows the editorial closely. if you still dont understand, i shall try to explain
Ok, I shall explain. When we BFS from 10, we don’t find anything within range of 2. But that doesn’t mean we terminate the algorithm. We start from another special node, say 4. The best answer remains 2 so we will still search a range of 2. When we do it from 6, we find a better answer, i.e., 1.
1 Like
Could you please elaborate on the “star graph” test case. Like, could you produce such a test case and provide me the link.
Sure yeah I don’t think this is standard terminology 
Basically a tree with k chains of length 9, with the root being 90001. Also this is unweighted basically. Tell me if there’s anything wrong with this generator.
Sorry, the wrong version of editorialist’s program was uploaded. Please click on the editorialist link again to view the updated version.
Yeah, that’s was the needed one!!
@waterfalls For a test case generated by your generator, author’s solution gives “no luck at all”. why so
@pushkarmishra probably because the author’s solution seems to be using a different input/output than the final problem? This is probably due to a revision of the problem. I think the int aa overflowed to a negative hence aa<2. Try another accepted solution? (like AnonymousBunny)
Thank you 
The first part of the solution is really nice. I think you can leave out the random part by choosing the sets appropriately. log(k)+1 should be enough by e.g using the ith special point for the starting set in round j if the jth digit in the binary representation of i is one.
1 Like
@ceilks Yeah, that’s true, good point! I’m not sure why I defaulted to random, but I guess it’s kind of nice since you could see it as log(# of tests) with the full feedback.
That is because handling of 64 bit integers is slower than 32 bit integers. Thus, you should avoid long long whenever you don’t really need it.
1 Like
because using long long increases time consumption so i think your solution got tle
Nice one man
Nice one!!!