PROBLEM LINK:Author: Timothy Tester: Akshay Venkataramani DIFFICULTY:EASYMEDIUM PREREQUISITES:Graph, BFS, Shortest Path Algorithms EXPLANATION:The question requires a reversal of perspective. Trying to find the shortest distance to the finish line(node N) from each of the starting points(nodes 1 to S) gives a TLE. Instead, we can find the shortest distance from node N to nodes 1 to S. This can be done using shortest path algorithms like Dijkstra's or by using a BFS, which is O(N), since the graph is unweighted. Once the shortest distances to all nodes are found, it is just a matter of finding the count of the maximum distances. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. Tester's solution can be found here.
This question is marked "community wiki".
asked 21 Jan '18, 17:26

According to given question, if all horses finish in equal time then none of them should be sold. However, according to test cases all of them will be sold in such case. It seems incorrect to me. answered 24 Feb, 16:58
