Connection Status:
Competition Arena > ConnectingAirports

ConnectingAirports

TCO09 Round 2 · 2009-02-24 · by misof

TCO09 Round 2 · 2009-02-24 · by misof · Graph Theory, Greedy
Class Name: ConnectingAirports
Return Type: String[]
Method Name: getSchedule
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

In the kingdom of Absurdistan there are N airports, and in the far away country of Utopia there are M airports. Currently, there is no air traffic on any of these airports. Each airport has some capacity - i.e., a limit on the number of flights it can handle. Capacities may be different for different airports.

The citizens of the two countries would like to connect them by new flights. The schedule must follow these rules:

  • Each flight is a two-way service that directly connects an airport in Absurdistan and an airport in Utopia.
  • No pair of airports can be connected by more than one flight.
  • Together, the flights must exactly meet the capacities of all airports. That is, for each airport the number of flights scheduled from it to another airports must be exactly the same as the capacity for this airport.
  • If there are multiple schedules that satisfy the previous rules, the lexicographically smallest one (definition follows) must be chosen.

Each possible schedule can be represented as a matrix with N rows and M columns. The rows correspond to airports in Absurdistan (in alphabetical order), the columns to airports in Utopia (again, in alphabetical order). The cell at (r,c) contains the number 1 if the two airports are connected by a flight and 0 otherwise.

To compare two schedules, find the first row in which they differ, and in that row find the first column in which they differ. The one that contains a zero in this cell is lexicographically smaller.

You are given two int[]s: capacityA and capacityU. The int[] capacityA contains the capacities of all the airports in Absurdistan in alphabetical order. The int[] capacityU describes the Utopian airports in the same way. If there is no valid schedule, return an empty String[]. Otherwise, find the lexicographically smallest valid schedule and return it formatted as a String[].

Notes

  • The exact formatting of the output: A zero-one matrix A with M rows and N columns is encoded as a String[] X with M elements, containing N characters each. Character c in element r is '1' if A(r,c)=1, and it is '0' if A(r,c)=0.

Constraints

  • capacityA will contain between 1 and 50 elements, inclusive.
  • capacityU will contain between 1 and 50 elements, inclusive.
  • Each element in capacityA will be between 0 and 50, inclusive.
  • Each element in capacityU will be between 0 and 50, inclusive.
Examples
0)
{1,2,3}
{3,1,2}
Returns: {"100", "101", "111" }

In this case there is only one way to schedule the flights.

1)
{3,2,1,1}
{1,3,1,2}
Returns: {"0111", "0101", "0100", "1000" }

In this case there are multiple valid schedules. Make sure that you output the lexicographically smallest one.

2)
{1,2,3,4}
{5,6,7,8}
Returns: { }

The capacities of airports in Absurdistan are too small.

3)
{47,47}
{47,40,7}
Returns: { }

Each pair of airports can only be connected by a single flight.

4)
{5,5}
{1,1,2,1,1,1,1,1,1}
Returns: {"001001111", "111110000" }
5)
{0,0,0,0}
{0,0,0,0,0,0}
Returns: {"000000", "000000", "000000", "000000" }

Zeros may occur in the input.

Submissions are judged against all 200 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ConnectingAirports with a public method vector<string> getSchedule(vector<int> capacityA, vector<int> capacityU) · 200 test cases · 2 s / 256 MB per case

Submitting as anonymous