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.
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?
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.
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.
@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)
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.
