You are not logged in. Please login at www.codechef.com to post your questions!

×

HRACE - Editorial

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.

This question is marked "community wiki".

asked 21 Jan '18, 17:26

accelmage's gravatar image

4★accelmage
52
accept rate: 0%

edited 05 Feb '18, 13:57

admin's gravatar image

0★admin ♦♦
19.8k350498541


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.

link

answered 24 Feb, 16:58

i_satyavrat's gravatar image

4★i_satyavrat
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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