I think,the algorithm wherein all edges are of weight 1 need not give the correct answer.
Consider the case :-
2 - 3 - 4 - 5 - 6 - 7
|
8
|
9
|
10
where 2,4,6,7,10 are special nodes.
Let in the first BFS we choose 2,then answer will be updated with 2 when 4 is found.
In the second BFS if we choose 10 then we will not find any special node in range of 2,thus algrithm will terminate.So,it will output 2 as answer.But the actual answer is 1(6 and 7).Please correct me if I’m wrong.
I don’t see how the editorial’s solution works.
Just testing with CF custom invocation, the editorialist’s solution seems to TLE (>10s) on, for example, a “star” graph with 1e4 arms of length 9 with one center node. The tester’s solution is the same. The author’s solution doesn’t take in the correct input and output but seems to be fine (same as AnonymousBunny’s solution).
I think the problem with the editorial’s reasoning is that the halving process, while true for one iteration, does not hold past the first. The process does not make a “smaller” version of the problem, since the number of nodes remains the same.
I really like the problem: interesting to think about, the author’s solution is great, and I also thought of my own totally different solution which I find pretty cool 
I do think the long armed star graph is a pretty natural test for this problem though and it looks like a lot of bad solutions passed.
I might have missed something, if so please let me know!
changing “long long” by “int” make accepted within time limit 
In Editorialist Solution,
for (int j = 1; j <= n; j++) d[j] = 1e9, vis[j] = 0;
The maximum value of K = 10^4 and of N = 10^5 which gives complexity O(N*K) which is 10^9 so how does it pass the test cases.
Thanks in advance!!!
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)
