TheKingsRoadsDiv2
SRM 650 · 2015-01-29 · by Witaliy
Problem Statement
You live in the Kingdom of Byteland. The kingdom has a very interesting history. It has already existed for h years. During the first year of its existence the inhabitants built the first city. During each of the next h-1 years the following procces occurred: For each city built in the previous year, two additional cities were built and the older city was connected to each the two new cities by a bidirecional road. Now, after h full years, the kingdom contains exactly (2^h)-1 cities and (2^h)-2 roads.
Recently the King did two changes to the kingdom. First, he numbered the cities from 1 to (2^h)-1 in an arbitrary way. Then, he added exactly one new road to the kingdom. (The road could have connected two cities that were already connected by a different road. Also, it is possible that the new road connected some city to itself.)
You are given the
Return "Correct" if it is possible that the given list of roads is the current road network in the Kingdom of Byteland. Otherwise, return "Incorrect".
Constraints
- h will be between 2 and 10, inclusive.
- a and b will contain exactly (2^h)-1 elements each.
- Each element of a and b will be between 1 and (2^h)-1, inclusive.
3
{1, 2, 3, 7, 1, 5, 4}
{6, 7, 4, 3, 3, 1, 7}
Returns: "Correct"
City 3 was built during the first year, cities 1 and 7 during the second year, and the other four cities during the third year. Then the King added the road 3-4.
2
{1, 2, 3}
{2, 1, 3}
Returns: "Incorrect"
5
{20, 19, 17, 21, 12, 12, 31, 21, 8, 31, 8, 14, 5, 10, 18, 30, 18, 23, 14, 1, 17, 16, 19, 23, 16, 30, 1, 20, 5, 8, 10}
{2, 12, 10, 23, 24, 26, 4, 20, 13, 6, 29, 8, 30, 14, 27, 1, 13, 11, 31, 28, 5, 9, 18, 3, 22, 16, 7, 25, 21, 15, 19}
Returns: "Correct"
3
{7, 1, 1, 2, 2, 3, 1}
{7, 1, 7, 4, 5, 2, 6}
Returns: "Incorrect"
5
{7, 23, 6, 17, 22, 30, 30, 21, 11, 17, 2, 26, 3, 7, 6, 29, 31, 26, 31, 1, 16, 3, 21, 23, 29, 2, 22, 11, 21, 1, 16}
{10, 9, 3, 14, 11, 19, 25, 16, 31, 15, 5, 21, 27, 8, 29, 28, 7, 6, 30, 2, 20, 13, 23, 12, 24, 18, 26, 1, 15, 17, 4}
Returns: "Correct"
3
{6, 5, 3, 3, 5, 5, 6}
{1, 5, 5, 6, 4, 7, 2}
Returns: "Correct"
Here the road added by the King is obviously the self-loop from city 5 to itself.
Submissions are judged against all 122 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheKingsRoadsDiv2 with a public method string getAnswer(int h, vector<int> a, vector<int> b) · 122 test cases · 2 s / 256 MB per case