ChargingACarFleet
2022 TCO Parallel 2B · 2022-04-14 · by misof
Problem Statement
You have a fleet of electric cars. They all need to be charged, but there is only a limited supply of chargers.
There are N cars, numbered from 0 to N-1. Car x needs to be charged for chargingTime[x] seconds. (Once you start charging a car, you must continue charging it until it's fully charged.)
Different cars have a different level of importance.
This is captured by the
There are M parking spots with chargers. These are numbered from 0 to M-1.
Some of them are currently in use (charging cars that are not ours). Spot y will only become available after spotAvailable[y] seconds. Once a spot becomes available, we are free to use it to charge our cars.
Each parking spot can only fit a single car at any moment in time. (We may charge multiple cars in the same spot, but we have to do it sequentially.)
The final complication is that some cars may be too large for some of the spots. More precisely, car x fits into spot y if and only if carSize[x] <= spotSize[y].
Assume that everything other than charging itself takes zero time. In particular, this applies to getting a car into a spot before charging and then out of the spot once it's ready. Thus, as soon as a car is fully charged, we can start charging another car in the same spot.
Find the minimal total penalty P we'll receive until all our cars are fully charged.
Then, find one specific schedule that has this optimal penalty:
for each car x determine the spot S[x] where we should charge it and also the time T[x] when its charging should start.
Return the following
Notes
- All valid schedules with the smallest possible total penalty will be accepted.
- The last constraint given below implies that each car can be charged somewhere, and therefore a solution always exists.
Constraints
- N will be between 1 and 13, inclusive.
- chargingTime, penalty and carSize will have exactly N elements each.
- Each number in these three arrays will be between 1 and 20,000,000, inclusive.
- M will be between 1 and 30, inclusive.
- spotAvailable and spotSize will have exactly M elements each.
- Each number in spotAvailable will be between 0 and 20,000,000, inclusive.
- Each number in spotSize will be between 0 and 20,000,000, inclusive.
- max(carSize) will not exceed max(spotSize).
{100, 100}
{1, 1}
{5000, 7000}
{0, 0, 1000}
{3000, 6000, 7000}
Returns: {1200, 1, 2, 0, 1000 }
Two cars. Each needs to be charged for 100 seconds and for each car we lose $1 each second until it becomes available. Car 0 is smaller than car 1. Three spots with chargers. Spots 0 and 1 are already available, spot 2 will only become available after 1000 seconds. Car 0 does not fit into spot 0 but it fits into spot 1 and the optimal thing to do is to start charging it there immediately. Car 1 must wait until spot 2 becomes available, as that is the only spot large enough to accommodate this car. The penalty incurred by this solution is $100 for car 0 and $1100 for car 1.
{1000, 9}
{1, 10000}
{7000, 7000}
{0, 10, 10000}
{7000, 7000, 7000}
Returns: {91009, 0, 0, 9, 0 }
Car 1 has a huge penalty, so it seems like we should start charging it as soon as possible. There is no other available spot while car 1 is charging, so car 0 has to wait. The first spot that becomes available is spot 0. This happens exactly 9 seconds from now. The penalty for this solution is $1009 for car 0 and $90,000 for car 1, which gives us the total of $91,009.
{100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100}
{100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100}
{100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100}
{0, 0, 0}
{100, 101, 102}
Returns: {300000, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 100, 200, 300, 0, 100, 200, 300, 0, 100, 200, 300 }
Twelve identical cars and three practically identical spots with chargers. The order in which we charge the cars does not matter, but we must make sure to distribute them uniformly and to leave no gaps between charging.
{4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 4, 5, 6}
{11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 13, 13, 13}
{100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100}
{100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 0, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100}
{100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100}
Returns: {5356, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 8, 22, 39, 52, 67, 4, 17, 33, 45, 59, 0, 12, 27 }
{100, 100, 100, 100, 100}
{100, 100, 100, 100, 100}
{5000, 5500, 6000, 6500, 7000}
{0, 0, 0, 0, 0}
{5300, 7100, 5500, 6666, 6123}
Returns: {50000, 0, 2, 4, 3, 1, 0, 0, 0, 0, 0 }
If we are smart about which car goes to which spot, we can start charging all five immediately.
Submissions are judged against all 196 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ChargingACarFleet with a public method vector<long long> charge(vector<int> chargingTime, vector<int> penalty, vector<int> carSize, vector<int> spotAvailable, vector<int> spotSize) · 196 test cases · 2 s / 256 MB per case