FlightReduction
SRM 816 · 2021-10-13 · by misof
Problem Statement
The recent pandemic forced many airlines to downsize.
Our airline is currently serving N airports, numbered from 0 to N-1. We have M bidirectional flights: flight i operates between airports A[i] and B[i].
We want to keep only a profitable subset of airports and stop servicing all others. For the purpose of this problem, the profitability of a non-empty subset S of airports is defined as f(S) / |S|, where f(S) is the number of flights with both endpoints in S, and |S| is the size of S.
Find and return any non-empty subset of airports with the maximum profitability.
Notes
- All optimal answers will be accepted. The order in which you output the airports you want to keep does not matter (but you must output each only once).
Constraints
- N will be between 1 and 60, inclusive.
- A will have between 0 and 150 elements, inclusive.
- B will have the same number of elements as A.
- Each pair (A[i], B[i]) will consist of two distinct airports.
- All unordered pairs (A[i], B[i]) will be distinct.
7
{2}
{5}
Returns: {2, 5 }
We should drop all airports from which we have no flights, and keep only airports 2 and 5.
5
{0, 1, 2, 3, 0, 1, 2}
{1, 2, 3, 0, 2, 3, 4}
Returns: {0, 1, 2, 3 }
Currently we have 7 flights and 5 airports, for a profitability of 1.4. If we drop airport 4, we will have 6 flights and 4 airports, which increased our profitability to 1.5.
1
{}
{}
Returns: {0 }
2
{}
{}
Returns: {0 }
Remember that we need to keep a non-empty subset of airports.
2
{1}
{0}
Returns: {0, 1 }
Submissions are judged against all 80 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FlightReduction with a public method vector<int> reduce(int N, vector<int> A, vector<int> B) · 80 test cases · 2 s / 256 MB per case