HRACE - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice

Contest

Author: Timothy

Tester: Akshay Venkataramani

DIFFICULTY:

EASY-MEDIUM

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.

2

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.