The questions are still open and you can try them here.
The second question was harder and was about finding the fastest way to do a relay with cyclists having different abilities and starting from different locations. This can be generalized to finding the fastest way to go from one node to another in an acyclic unidirectional graph described with distances and speeds. In each node, there is a cyclist with a speed and a maximum distance. Each edge is associated with a distance. At each node, we have the choice between keeping the current cyclist (current speed and remaining distance) or switching to the one available at this node (new speed and distance). What makes this problem harder is having two dimensions: distance and time. If you don’t remember the question, you can also find it below.
There are multiple ways of solving the second question including:
- Using a modified version of the breadth-first search (BFS) algorithm where we treat each edge as up to two edges: one if we keep the current cyclist and one if we switch cyclists.
- Creating a new graph with times and apply BFS on this graph. To create a new graph with times, we can keep the nodes and create new edges based on which nodes can be reached by each cyclist. We would associate the time taken by the cyclist to each of the edges. For example, if the distance is 100 meters between city A and B and 200 meters between city B and C, and the cyclist of city A can cycle for 400 meters, there would be two edges starting from A, one that goes to B and another one that goes to C.
- Using dynamic programming to track the minimum time to go to each node from the start node
We will describe the first solution since it is one of the easiest solutions to understand.
The first thing we need to do is saving the input into two data structures. We can have a map of cyclists, where each cyclist has an id, distance and speed. We can also have a map of edges, where each edge is associated with a distance.
We can then apply a modified version of BFS algorithm with a queue of paths. Each path contains 4 values: current city id, speed of the current cyclist, remaining distance of the current cyclist and spent time to reach the current city.
As long as there are paths in the queue, we would pop the next one, check that the time spent is smaller than the best time, check whether we have reached the end, and push up to two paths into the queue for each edge. Why up to two? Because we can add one with the current cyclist and one with the cyclist available at the node we just reached. If one cyclist has a better speed and remaining distance than the other one, we can only add the best one of the two cyclists instead of adding both.
In pseudo-code code, it would look like this:
/*
Save the cyclist input into a map of cyclist. Each cyclist contains an id, a distance and a speed.
Save the city input into an edge map with the associated distance. In Java, we could use Map<Integer, Map<Integer, Integer>>.
Initialize a queue of paths. Each path contains a city id, a speed, a remaining distance and a time spent.
Put the start cyclist into the path.
As long as there are paths in the queue,
Pop the path from the queue
Check that the time spent is smaller than the best time
Check where we have reached the end. If it's the case, save the result and continue with the next path.
For each edge starting from the current city id,
Compute the new remaining distance, which is the difference between the current remaining distance and the distance from the current city to the next city
Check that the new remaining distance is positive. If it's not the case, continue with the next edge
Retrieve the information of the cyclist at the next city.
If the current cyclist has either a better speed or a better remaining distance than the next cyclist,
Push a new path with the speed and remaining distance of the next cyclist into the queue
If the next cyclist has either a better speed or a better remaining distance than the current cyclist,
Push a new path with the speed and remaining distance of the next cyclist into the queue
Output the best time
*/
Employees of the TransferWise Singapore office recently met with someone who walked from Estonia to Singapore. As a challenge, they accepted to cycle back from Singapore to Estonia by doing a relay with TransferWise employees from different cities.
We need your help to find what the fastest way is to do the relay. We know how fast each employee is, how far each employee can go and the distance between some employees. It is fine if some employees are not included in the relay.
The first line is the number of employees N. The next N lines contain three integers: the employee id, the speed in meters per second and the distance they can cycle in meters.
The next line is the number of known paths between employees P. The next P lines contain three integers: the id of the first employee, the id of the second employee and the length of the path in meters. Paths are from the first employee to the second employee and are unidirectional. To make things simpler, we guarantee that there is no loop.
The next line contain two integers: the id of the employee who starts the relay, S, and the id of the employee we want to reach, D.
2 <= N < 1000
1 <= P < 10000
Speeds and distances are stricly positive integers. We guarantee that there is no loop in the unidirectional graph.
The best time to go from the employee S to employee D in seconds, rounded up to the closest integer in seconds.
6
1 1 2000
2 10 2000
3 4 2000
4 2 100
5 1 100
6 2 1000
5
1 2 200
1 3 150
2 5 2000
3 4 200
4 5 1000
1 5
400
We want to do a relay from employee 1 to employee 5. Employee 1 can cycle at 1 meter per second for 2000 meters and has two options, going to employee 2 or employee 3.
Let’s focus on the first option. The distance between city 1 (the city of employee 1) and city 2 is 200 meters, which means it would take 200 seconds to go from employee 1 to reach city 2. Employee 2 can cycle at 10 meters per second for 2000 meters. From city 2, we can only go to city 5, which is 2000 meters away. Since employee 1 has already cycled for 200 meters, it can only cycle for another 1800 meters and cannot reach city 5. However, employee 2 can continue the relay and reached city 5 in 200 seconds (2000 / 10). The total time to reach city 5 would be 400 (200 + 200) seconds.
Let’s now focus on the second option. The distance between city 1 and city 3 is 150 meters, which means it would take 150 seconds for employee 1 to reach city 3. Employee 3 can cycle at 4 meters per second for 2000 meters. Since employee 3 is faster and can cycle for a longer distance, employee 3 can continue the relay. The distance between city 3 and 4 is 200, which would take 50 seconds for employee 3 to reach. Employee 4 can cycle at 2 meters per second for 1000 meters. Since employee 3 is faster and can cycle for a longer distance (another 1800 meters), employee 3 can continue the relay and reach city 5 in 250 (1000/4) seconds. The total time to reach city 5 would be 450 (150 + 50 + 250) seconds.
The best time to reach city 5 from city 1 is 400 seconds.