Hello,
I have implemented the algorithm mentioned in the editorial.
I have a solution, in which I am using int64_t to store the distances, but I am getting TLE with that solution, on the other hand, If I use int32_t in place of int64_t I am getting AC.
Why is that ?
https://www.codechef.com/viewsolution/9754905
https://www.codechef.com/viewsolution/9754870
Alternate solution that I find pretty cool:
We want to find shortest paths with a variety of starting points. This brought to mind the multiple source shortest path problem, which is basically the same as single source, except you add all starting points to your queue/priority_queue with distance 0.
Now, this doesn’t work since your path will just go from like special->not_special->same_special which is not allowed since the start and end must be distinct.
The next idea is to only choose some of them as starting points. Then, if the optimal pair is (a,b), you need exactly one of (a,b) to be chosen as a starting point, and then you will find the answer as the shortest distance from a starting special point to a nonstarting special point.
How do we decide which to choose as starting points? Here’s a nice step - we win if we choose exactly one of the starting points. Notice if we choose a RANDOM set of starting points, there’s a 1/2 chance that we chose exactly one as a starting point. Now, if we iterate choosing a random set of starting points enough times, we will find the answer with high probability.
I chose MAGIC=20 (1/2^20 chance of failing a single test), here’s the implementation: CodeChef: Practical coding for everyone.
Complexity is O(nlogm) per iteration, and a bit of math can help choose a good number of iterations (or just until time runs out).
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.
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.
@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.
