Link to the problem on UVa Online Judge
There are a few key points in the problem statement that can guide you to the solution. We want to calculate the worst case scenario of putting three people in random intersections and calculate the time they arrive at a common intersection. So no matter where they are located initially they will find an intersection and meet each other there. It's not the best choice, and that's the point, we have to calculate how long a live TV broadcast must last to cover their journey.
First question : From the three persons who is the worst walker and will take longer to get to the destination? The person with the slowest speed.
Next question : Which path is the worst for the slowest person to traverse? Actually which two intersections as start and end is the worst for the slowest person of the group? The two intersections that are farthest from each other.
So we have to calculate shortest path between each two pairs of intersections. Which algorithm you know that is asymptotically optimal for this job? The answer is Floyd-Warshall algorithm. After calculating all pairs shortest path using this algorithm, find the two farthest intersections and calculate how long does it take for the slowest person to get from one of them to the other.
As you know X = V.T so T = X / T. If we want to round up a division operation instead of X / T we can use (X + T - 1) / T, think about this, why this rounds up the division?
There are a few key points in the problem statement that can guide you to the solution. We want to calculate the worst case scenario of putting three people in random intersections and calculate the time they arrive at a common intersection. So no matter where they are located initially they will find an intersection and meet each other there. It's not the best choice, and that's the point, we have to calculate how long a live TV broadcast must last to cover their journey.
First question : From the three persons who is the worst walker and will take longer to get to the destination? The person with the slowest speed.
Next question : Which path is the worst for the slowest person to traverse? Actually which two intersections as start and end is the worst for the slowest person of the group? The two intersections that are farthest from each other.
So we have to calculate shortest path between each two pairs of intersections. Which algorithm you know that is asymptotically optimal for this job? The answer is Floyd-Warshall algorithm. After calculating all pairs shortest path using this algorithm, find the two farthest intersections and calculate how long does it take for the slowest person to get from one of them to the other.
As you know X = V.T so T = X / T. If we want to round up a division operation instead of X / T we can use (X + T - 1) / T, think about this, why this rounds up the division?
No comments:
Post a Comment