TruckUnion
SRM 809 · 2021-07-12 · by misof
Problem Statement
There is a country with N cities, numbered from 0 to N-1.
Your company has a warehouse in city 0. You want to distribute your wares from city 0 to all other cities.
In order to do that, you can hire one or more trucks. Each truck will visit some subset of the other cities and then return back to city 0.
You refuse to pay the truckers for useless work, so each of the cities 1 to N-1 must be visited only by one truck and only exactly once.
Additionally, you are limited by a demand made by the truckers' union: each trucker must receive an equal amount of work - more precisely, an equally long list of orders. In other words, each trucker must visit the same number of cities.
You are given the
Calculate and return the minimal total cost of distributing your wares to the entire country.
Notes
- Each trucker may only return to city 0 at the end of their trip.
Constraints
- N will be between 2 and 18, inclusive.
- C will contain exactly N^2 values.
- For each i, C[i*N+i] will be 0.
- Each other element of C will be between 1 and 10^6, inclusive.
5
{0, 1, 1, 1, 1,
1, 0, 9, 9, 9,
1, 9, 0, 9, 9,
1, 9, 9, 0, 9,
1, 9, 9, 9, 0}
Returns: 8
We can send a single truck with wares for all four remaining cities. Regardless of which route we choose (e.g., 0-1-3-4-2-0), the total cost will be 1+9+9+9+1 = 29. We can send two trucks, each with wares for two cities. Again, each schedule (e.g., one truck goes 0-1-3-0 and the other 0-4-2-0) has the same cost: 1+9+1 + 1+9+1 = 22. We can send four trucks. Each will visit a single city and return back. This has the cost 4*(1+1) = 8 and this is the best option.
5
{0, 9, 9, 9, 8,
8, 0, 9, 9, 9,
9, 9, 0, 8, 9,
9, 8, 9, 0, 9,
9, 9, 8, 9, 0}
Returns: 40
Now that the travel costs are much more uniform, the optimal solution is to send a single truck. This time the exact route matters. The optimal truck route is 0-4-2-3-1-0. On this route each movement costs 8 and thus the total cost of the route is 5*8 = 40.
2
{0, 1000000,
1, 0}
Returns: 1000001
5
{0, 9, 9, 1, 1,
1, 0, 9, 9, 9,
1, 9, 0, 8, 9,
9, 8, 9, 0, 9,
9, 9, 8, 9, 0}
Returns: 20
Here's an example where it's optimal to use two trucks. An optimal solution: Send one truck along the route 0-3-1-0 (cost 1+8+1 = 10) and the other one along the route 0-4-2-0 (again, cost 1+8+1 = 10).
5
{0, 1, 1, 1000000, 1,
1, 0, 90000, 80000, 70000,
1, 60000, 0, 1, 50000,
900000, 40000, 1, 0, 1,
1, 30000, 20000, 1, 0}
Returns: 30004
Here the ideal solution would be to send one truck along 0-1-0 and the other along 0-2-3-4-0, only paying 6 for the whole distribution. However, the truck union rules forbid this solution, as the second trucker would have to visit more cities than the first trucker. The optimal valid solution is to send a single truck along the route 0-2-3-4-1-0.
Submissions are judged against all 77 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TruckUnion with a public method int optimize(int N, vector<int> C) · 77 test cases · 2 s / 256 MB per case