×

# HRACE - Editorial

Practice

Contest

Author: Timothy

Tester: Akshay Venkataramani

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.

This question is marked "community wiki".

52
accept rate: 0%

19.8k350498541

 0 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 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,723
×1,236
×513
×29

question asked: 21 Jan '18, 17:26

question was seen: 405 times

last updated: 24 Feb, 16:58