PROBLEM LINK:Author: Sergey Kulik DIFFICULTY:Medium PREREQUISITES:Dijkstra's Algorithm, Floyd Warshall, All Pairs Shortest Path Problem PROBLEM:Given is a graph $G$ with $N$ nodes and weighted edges. Out of these $N$ nodes, $K$ are special nodes. We are required to find the minimum distance between any two special nodes. EXPLANATION:Subtask 1 Subtask 2 Subtask 3 Let us start by thinking of an algorithm to solve a simpler version of the given problem wherein all edges are of weight 1. Now we propose the formal algorithm for this problem and then prove its time complexity. The formal algorithm is as follows:
It is pretty intuitive why this algorithm gives the correct answer. But why does it run within the given time limits? What is its time complexity? In the first look the algorithm seems to have a complexity of $\mathcal{O}(NK)$. But in fact it is $\mathcal{O}(N\log N)$. Basically, we show that after each iteration of the BFS, the minimum distance to be searched before which another special node is found  henceforth referred to as the radius of search  becomes half. Let us see why. After the first run of BFS from the randomly chosen special node, we can have two cases:
In the second case, we can clearly see that the search radius for the next BFS will be $\frac{N}{2}$, i.e., half of the current one. This is because we will anyway terminate the search if we don't find a special node in that radius. But what happens in the second case? If $s \geq \frac{N}{2}$, this means that all the other special nodes apart from the one we started our BFS on must all be clustered within a radius of $Ns$. Since $s \geq \frac{N}{2}$, this means that in the next BFS, we will definitely find a special within $\frac{N}{2}$ radius of the one we start on. Therefore, we see that in every iteration of BFS, we half our search radius of the graph. The algorithm therefore is $\mathcal{O}(N\log N)$. We can now go back to our original problem. Since, our original problem involves edges of different weights, instead of performing BFS, we need to perform Dijkstra's algorithm. But how many times? Following the same reasoning as the simpler version of the problem, we get that Dijkstra will be performed $\mathcal{O}(\log S_e)$ times, where $S_e$ is the sum of weights of all edges in the graph. This gives a total runtime of $\mathcal{O}(N\log N\log S_e)$ which is sufficient for the given constraints. Editorialist's program follows the editorial. Please see for implementation details. OPTIMAL COMPLEXITY:$\mathcal{O}(N\log N\log S_e)$ where $S_e$ is the sum of weights of edges. SAMPLE SOLUTIONS:
This question is marked "community wiki".
asked 13 Mar '16, 15:23

Another approach: start a Dijsktra with the marked vertices being the initial set. For each vertex v, let boss[v] and dist[v] be the closest marked vertex to v (pick any one if there are multiple choices) and distance from v to boss[v] respectively (both of these can be found from that Dijsktra). Now for each edge uv such that boss[u]!=boss[v], one candidate answer is dist[u]+dist[v]+len[u][v]. It's easy to see that the answer will be the smallest of these candidate answers. Code: https://www.codechef.com/viewsolution/9751280 I failed this in contest because this:
:( answered 26 Mar '16, 23:09

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: https://www.codechef.com/viewsolution/9755374. 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). answered 27 Mar '16, 13:54
1
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.
(28 Mar '16, 05:53)
@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.
(28 Mar '16, 07:26)

I think,the algorithm wherein all edges are of weight 1 need not give the correct answer. Consider the case :
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. answered 26 Mar '16, 23:54
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
(27 Mar '16, 00:03)
1
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.
(27 Mar '16, 10:41)

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! answered 27 Mar '16, 04:44
Could you please elaborate on the "star graph" test case. Like, could you produce such a test case and provide me the link.
(27 Mar '16, 10:42)
Sure yeah I don't think this is standard terminology :P 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.
(27 Mar '16, 10:56)
@waterfalls can you please share your solution/approach ?
(27 Mar '16, 11:21)
@waterfalls For a test case generated by your generator, author's solution gives "no luck at all". why so
(27 Mar '16, 11:48)
@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)
(27 Mar '16, 12:37)
Thank you :)
(28 Mar '16, 01:31)
showing 5 of 7
show all

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. https://www.codechef.com/viewsolution/9754905 answered 27 Mar '16, 12:26
because using long long increases time consumption so i think your solution got tle
(29 Mar '16, 00:49)

Can anybody explain how does the radius of search become half ? answered 30 Mar '16, 21:28

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? answered 14 Jul '17, 14:31

https://www.codechef.com/viewsolution/9755226 how did this pass? answered 27 Mar '16, 15:01
