ConnectTheWorld
SRM 821 · 2022-01-07 · by misof
Problem Statement
New teleport technology has recently been discovered.
Each teleport connects two terminals and allows people to travel freely from one to the other and back.
Multiple cities in the world requested to be the part of a new teleport network. Some teleports between those cities have already been built. Your task is to build additional teleports to make the entire network connected: after you are done, it must be possible to travel between any two cities (possibly using multiple teleports consecutively).
The existing teleports are described by the
There may be some cities that want to be in the teleport network but have no teleports yet.
The list of these cities is given in the
Teleports require an awful lot of energy and operating them is expensive.
For each city, let's look at the number of teleport terminals that are already in that city. Let MAX be the maximum of those numbers. No city in the world can afford to have more than MAX teleport terminals.
It is guaranteed that:
- The world isn't connected yet: there is at least one pair of participating cities that isn't connected via teleports (not even indirectly).
- In the already existing teleport network there are no loops. (In other words, there are no unnecessary teleports that could be shut down without affecting reachability between cities.)
Your task is to determine where to build additional teleports in order to connect all participating cities. A valid solution is any collection of new teleports that satisfies the following criteria:
- You can only build teleports between cities that appear in the input.
- Using the existing and new teleports it must be possible to travel between any two participating cities.
- In the resulting teleport network no city has more than MAX teleport terminals (where MAX is the value we already determined above).
- There are at most 100 new teleports. (This is only a technical limit that does not influence whether a solution exists or not.)
If no solution exists, return an empty
Notes
- It is not necessary to minimize the number of new teleports you'll build.
- The condition that there are no loops also implies that for each i, terminalA[i] and terminalB[i] are not the same city (i.e., no given teleport is a self-loop).
- You are allowed to build new teleports that are self-loops (even though this is clearly never useful). If you do, a self-loop counts as two terminals in the city where you built it.
Constraints
- A name is any string of 1 to 6 uppercase and lowercase English letters ('A'-'Z', 'a'-'z').
- Names are case-sensitive.
- Each element of terminalA will be a name.
- Each element of terminalB will be a name.
- Each element of isolated will be a name.
- terminalA will have between 0 and 30 elements, inclusive.
- terminalB will have the same number of elements as terminalA.
- isolated will have between 0 and 30 elements, inclusive.
- No element of isolated will appear in terminalA or terminalB.
- The elements of isolated will be mutually distinct.
- In the already existing teleport network there will be no loops.
- The world will not be connected yet.
{"Paris", "Paris"}
{"London", "NYC"}
{"Dhaka"}
Returns: {"London", "Dhaka" }
We already have two teleports: Paris-London and Paris-NYC. Dhaka isn't connected to the teleport network yet. There are three possible solutions: we can build the teleport Dhaka-London, the teleport Dhaka-NYC, or both of those. (We cannot make additional teleports out of Paris because it already has MAX teleports. We cannot build the London-NYC teleport because then both London and NYC would have MAX teleports and it would be impossible to connect Dhaka to any of the other three cities.)
{"Tokyo", "Prague"}
{"Sydney", "Bern"}
{}
Returns: { }
We currently have MAX = 1, which means that no city can afford more than one teleport terminal. Thus, there is no way to build additional teleports and we have no way to connect the world.
{"Tokyo", "Prague", "Bern"}
{"Sydney", "Bern", "Vienna"}
{}
Returns: {"Tokyo", "Prague" }
Now MAX=2 thanks to Bern and thus each of the other cities can get one additional terminal.
{"Madrid"}
{"Porto"}
{"Bogota", "Lima", "Kigali", "Ottawa", "Manila"}
Returns: { }
We can build a few new teleports without exceeding MAX=1 terminals in any city, but there is no way to build enough teleports to connect all these cities into one connected network.
{"BRNO", "Brno"}
{"Brno", "brno"}
{"brNO", "bRNo"}
Returns: {"BRNO", "bRNo", "brNO", "brno" }
Names are case-sensitive. These are five distinct cities.
Submissions are judged against all 132 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ConnectTheWorld with a public method vector<string> connect(vector<string> terminalA, vector<string> terminalB, vector<string> isolated) · 132 test cases · 2 s / 256 MB per case