MarsHabitats
SRM 812 · 2021-08-31 · by misof
Problem Statement
Elon is planning to colonize Mars.
According to Elon's plans, there should be N habitats on Mars. They are going to be numbered from 0 to N-1, inclusive. Habitat 0 will be the communications center.
Habitats will be connected by (bidirectional) corridors. For technical reasons, each habitat must have exactly three outgoing corridors.
Sometimes, both ends of a corridor may connect to the same habitat. Such a corridor counts as two corridors leaving that habitat.
Each corridor must have a non-negative integer length.
Note that the length of any corridor may be zero. (Self-looping corridors that start and end at the same habitat also may, but do not have to, have length zero.)
Once you build the N habitats and all corridors between them, we can measure distances: the distance between any two habitats is the smallest total length of corridors one has to cross in order to get from one habitat to the other.
Elon has a clear vision how far from the communications center each habitat should be. More precisely, for each habitat i Elon has determined the shortest distance distances[i] from habitat 0 along some corridors to habitat i.
Note that all the distances in distances are finite non-negative values, which implies that Elon wants to have a connected network of habitats.
Determine whether it is possible to design the corridors according to the technical requirements and Elon's wishes: each habitat must have three corridors, and all the distances must be as given in the input.
If it's not possible, return an empty
If it's possible, return a
For each habitat i, look at the three corridors that leave this habitat. For each of them, write down first the number of the habitat at its other end, and then the length of the corridor. The description of habitat i are the six values {number1, length1, number2, length2, number3, length3}.
Return the concatenation of the descriptions of all habitats in your solution. Your solution will be accepted if it produces the correct distances. Additionally, we require that the length of each corridor must be at most 1,000,000. For each habitat, the three outgoing corridors can be listed in any order.
Notes
- The value N is not given explicitly. You can determine it as the number of elements in distances.
Constraints
- distances will have between 1 and 200 elements, inclusive.
- Each element of distances will be between 0 and 1,000,000, inclusive.
- distances[0] will be 0.
{0}
Returns: { }
There is just a single habitat. There is no way to have exactly three corridors leaving this habitat, so we cannot satisfy the technical requirements.
{0, 10}
Returns: {1, 10, 1, 42, 1, 47, 0, 10, 0, 47, 0, 42 }
In the example output, the two habitats are connected by three separate corridors: one has length 10, one has length 42, and one has length 47. The distance from habitat 0 to habitat 1 is the length of the shortest of those three corridors.
{0, 47}
Returns: {0, 10, 0, 10, 1, 47, 1, 10, 0, 47, 1, 10 }
In the example output, the two habitats are connected by a single corridor of length 47. Additionally, each habitat has its own self-looping corridor of length 10.
{0, 47, 42, 25, 10, 22}
Returns: {1, 47, 2, 42, 4, 10, 0, 47, 3, 33, 3, 34, 0, 42, 2, 1234, 2, 1234, 1, 34, 1, 33, 4, 15, 0, 10, 3, 15, 5, 12, 5, 0, 4, 12, 5, 0 }
The sample return value corresponds to the following configuration of habitats: 5 --(12)-- 4 --(10)-- 0 --(42)-- 2 | | (15) (47) | | 3 --(33)-- 1 \__(34)__/ The number in parentheses is the length of the corridor. Numbers outside parentheses represent habitats. There are two self-looping corridors that are not shown in the figure.
{0, 451082, 580533, 475708, 598517, 360154, 269932, 537336, 405334, 411477, 645462, 42895, 833704, 438863, 690620, 24809, 107432, 656, 276621, 988439, 830728, 504944, 759019, 573243, 9579, 961967, 855335, 942395, 330907, 595138, 448475, 241221, 249290, 548687, 538918, 376524, 463702, 253806, 34879, 588194, 392342, 751548, 721002, 370621, 630168, 358522, 584885, 603039, 798908, 205503, 250210, 826916, 881458, 764568, 959398, 980978, 36992, 131595, 350148, 102704, 380463, 606446, 402211, 532997, 566365, 852477, 265116, 101815, 680324, 914300, 923912, 237982, 972044, 733173, 886702, 351125, 229170, 493910, 780328, 115496, 810627, 436899, 634026, 370198, 707636, 914726, 300226, 921855, 810482, 849306, 250591, 848416}
Returns: {17, 656, 0, 0, 0, 0, 36, 12620, 30, 2607, 30, 1000000, 46, 4352, 23, 7290, 46, 1000000, 77, 18202, 36, 12006, 36, 1000000, 47, 4522, 29, 3379, 47, 1000000, 83, 10044, 45, 1632, 45, 1000000, 18, 6689, 66, 4816, 18, 1000000, 34, 1582, 63, 4339, 63, 1000000, 9, 6143, 62, 3123, 9, 1000000, 81, 25422, 8, 6143, 8, 1000000, 68, 34862, 82, 11436, 82, 1000000, 67, 58920, 56, 5903, 56, 1000000, 91, 14712, 20, 2976, 91, 1000000, 30, 9612, 81, 1964, 81, 1000000, 84, 17016, 68, 10296, 68, 1000000, 38, 10070, 24, 15230, 38, 1000000, 79, 8064, 59, 4728, 79, 1000000, 24, 8923, 0, 656, 24, 1000000, 86, 23605, 6, 6689, 6, 1000000, 19, 0, 55, 7461, 19, 0, 12, 2976, 51, 3812, 51, 1000000, 63, 28053, 77, 11034, 77, 1000000, 53, 5549, 41, 7471, 53, 1000000, 2, 7290, 64, 6878, 64, 1000000, 15, 15230, 17, 8923, 17, 1000000, 72, 10077, 54, 2569, 54, 1000000, 52, 26123, 65, 2858, 52, 1000000, 54, 17003, 70, 18483, 70, 1000000, 58, 19241, 86, 30681, 86, 1000000, 4, 3379, 39, 6944, 39, 1000000, 1, 2607, 13, 9612, 1, 1000000, 32, 8069, 71, 3239, 32, 1000000, 50, 920, 31, 8069, 31, 1000000, 64, 17678, 34, 9769, 34, 1000000, 33, 9769, 7, 1582, 33, 1000000, 60, 3939, 43, 5903, 60, 1000000, 3, 12006, 1, 12620, 3, 1000000, 66, 11310, 90, 3215, 66, 1000000, 56, 2113, 15, 10070, 15, 1000000, 29, 6944, 46, 3309, 29, 1000000, 62, 9869, 60, 11879, 62, 1000000, 22, 7471, 73, 18375, 73, 1000000, 73, 12171, 84, 13366, 84, 1000000, 35, 5903, 83, 423, 83, 1000000, 82, 3858, 61, 23722, 61, 1000000, 5, 1632, 75, 7397, 5, 1000000, 39, 3309, 2, 4352, 2, 1000000, 61, 3407, 4, 4522, 4, 1000000, 88, 11574, 78, 18580, 78, 1000000, 76, 23667, 57, 73908, 57, 1000000, 90, 381, 32, 920, 90, 1000000, 20, 3812, 80, 16289, 20, 1000000, 74, 5244, 26, 26123, 26, 1000000, 78, 15760, 22, 5549, 22, 1000000, 25, 2569, 27, 17003, 25, 1000000, 19, 7461, 72, 8934, 72, 1000000, 11, 5903, 38, 2113, 11, 1000000, 49, 73908, 79, 16099, 49, 1000000, 75, 977, 28, 19241, 75, 1000000, 16, 4728, 67, 889, 67, 1000000, 40, 11879, 35, 3939, 35, 1000000, 44, 23722, 47, 3407, 44, 1000000, 8, 3123, 40, 9869, 40, 1000000, 7, 4339, 21, 28053, 7, 1000000, 23, 6878, 33, 17678, 23, 1000000, 26, 2858, 89, 3171, 89, 1000000, 6, 4816, 37, 11310, 37, 1000000, 59, 889, 11, 58920, 59, 1000000, 14, 10296, 10, 34862, 14, 1000000, 85, 426, 74, 27598, 74, 1000000, 27, 18483, 87, 2057, 27, 1000000, 31, 3239, 76, 8812, 76, 1000000, 55, 8934, 25, 10077, 55, 1000000, 41, 18375, 42, 12171, 41, 1000000, 69, 27598, 52, 5244, 69, 1000000, 45, 7397, 58, 977, 58, 1000000, 71, 8812, 49, 23667, 71, 1000000, 21, 11034, 3, 18202, 21, 1000000, 48, 18580, 53, 15760, 48, 1000000, 57, 16099, 16, 8064, 16, 1000000, 51, 16289, 88, 145, 88, 1000000, 13, 1964, 9, 25422, 13, 1000000, 10, 11436, 44, 3858, 10, 1000000, 43, 423, 5, 10044, 43, 1000000, 42, 13366, 14, 17016, 42, 1000000, 87, 7129, 69, 426, 87, 1000000, 28, 30681, 18, 23605, 28, 1000000, 70, 2057, 85, 7129, 85, 1000000, 80, 145, 48, 11574, 80, 1000000, 65, 3171, 91, 890, 65, 1000000, 37, 3215, 50, 381, 50, 1000000, 89, 890, 12, 14712, 12, 1000000 }
Submissions are judged against all 57 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MarsHabitats with a public method vector<int> design(vector<int> distances) · 57 test cases · 2 s / 256 MB per case