TreelandStreetView
TCO21 Algo Semi 1 · 2021-11-12 · by misof
Problem Statement
Treeland has the topology of a tree. There are N locations with labels 0 to N-1.
For each i between 0 and N-2, inclusive, the locations parent[i] and (i+1) are connected by a bidirectional road of length plength[i].
We would like to create a street view map for Treeland.
We have a fleet of cars with cameras. Initially, car j is parked in location carNode[j] and it contains carGas[j] units of gas.
Car movement is continuous. Cars are points. One unit of gas is enough to traverse one unit of distance.
Each car should visit some parts of Treeland in such a way that together they will cover the whole Treeland - not just all locations, but also entire roads between them.
(Some parts of Treeland may be visited by multiple cars.)
Whenever two cars are located at the same point, they may share gas arbitrarily. This includes meeting somewhere on a road between two locations, moving a fractional amount of gas from one car to another, and also having more than the initial amount of gas in a car.
Return "possible" if there is a schedule how to move the cars and share gas between them so that we get the full street view map. Return "impossible" otherwise.
Constraints
- N will be between 2 and 100, inclusive.
- parent will have exactly N-1 elements.
- For all i, element i of parent will be between 0 and i, inclusive.
- plength will have exactly N-1 elements.
- Each element of plength will be between 1 and 10^6, inclusive.
- carNode will have between 1 and 100 elements, inclusive.
- Each element of carNode will be between 0 and N-1, inclusive.
- carGas will have the same number of elements as carNode.
- Each element of carGas will be between 0 and 10^6, inclusive.
5
{0, 0, 0, 0}
{7, 8, 9, 10}
{1, 0, 0, 0}
{34, 0, 0, 0}
Returns: "possible"
This graph is a star with center in location 0. One car with 34 units of gas starts in location 1, all others start in location 0 with no gas. A valid schedule: car 0 will come to location 0. At that point, it has 27 units of gas left. This gas is divided among the other three cars according to the lengths of the other three roads from location 0, and then each of the other three cars traverses one of the remaining three roads. (We did not need three cars in location 0. It would be doable with two, the third road can be traversed by the car that just arrived.)
5
{0, 0, 0, 0}
{7, 8, 9, 10}
{1, 0, 0}
{34, 0, 0}
Returns: "possible"
5
{0, 0, 0, 0}
{7, 8, 9, 10}
{1, 0, 0}
{33, 0, 0}
Returns: "impossible"
5
{0, 0, 0, 0}
{7, 8, 9, 10}
{1, 2, 3}
{47, 1, 2}
Returns: "possible"
5
{0, 0, 0, 0}
{7, 8, 9, 10}
{1, 2, 3}
{46, 1, 2}
Returns: "possible"
2
{0}
{100}
{0, 1}
{51, 53}
Returns: "possible"
Two locations connected by a road of length 100. One car starts in each location. Each car has enough gas to traverse slightly more than half of the road. So, together they have enough gas to visit the whole land.
5
{0, 0, 0, 0}
{7, 8, 9, 10}
{0, 1, 2, 3, 4}
{23, 5, 5, 5, 5}
Returns: "possible"
Each of the cars that start in the endpoints of the star will traverse as much of its only road as it can. The car that starts in the middle can visit everything else if it does so in the right order (i.e., ending in the middle of the longest road).
5
{0, 0, 0, 0}
{7, 8, 9, 10}
{0, 1, 2, 3, 4}
{22, 5, 5, 5, 5}
Returns: "possible"
Wait, what? This is still solvable with one fewer unit of gas? Sure. Remember that cars can swap gas whenever they meet. The schedule shown in the previous example is not optimal.
5
{0, 1, 1, 3}
{1, 1, 100, 100}
{0, 2}
{99, 104}
Returns: "possible"
Car 0 can do the entire trip alone, as follows: come from 0 via 1 to 2 (spent 2 units of gas, has 97), take all the gas from car 1 (now it has 201 units of gas), return to 1 (200 units left), and then travel via 3 to 4 (exactly all gas spent).
5
{0, 1, 1, 3}
{1, 1, 100, 100}
{3}
{297}
Returns: "impossible"
Even though this car has much more gas than the total length of all roads, it is alone to do the job and it cannot do it without traversing some roads twice. It turns out that the amount of gas it has is not sufficient.
6
{0, 0, 0, 3, 3}
{100, 110, 5, 99, 111}
{1, 2}
{215, 215}
Returns: "possible"
Cars from 1 and 2 drive to 0. Car from 1 will arrive there with 115 fuel, car from 2 with 105 fuel. They now have 220 fuel among them. Both cars drive to location 3. Total amount of fuel left: 210. At this point one of the cars part ways again. One car takes 99 fuel and drives off towards location 4, the other car is left with 111 fuel and drives towards location 5. Both make it exactly.
14
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
{0, 7, 11, 6}
{2, 4, 1, 7}
Returns: "possible"
A line with unit distances. Car #3 will start by driving one step right and giving one unit of gas to car #1. At this point car #3 has 5 units of gas left. It drives 5 steps left. Car #0 drives 2 steps right. Cars #0 and #3 meet in location 2. Car #1 now drives from its location all the way to location 13 to cover the rest of the land. Along the way this car picks up one unit of fuel from car #2. Together it spends six units of fuel: four it had from the start, one it got from car #3, and one it got from car #2.
Submissions are judged against all 112 archived test cases, of which 12 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TreelandStreetView with a public method string deliver(int N, vector<int> parent, vector<int> plength, vector<int> carNode, vector<int> carGas) · 112 test cases · 2 s / 256 MB per case