TheKingsRoadsDiv1

SRM 650 · 2015-01-29 · by Witaliy

SRM 650 · 2015-01-29 · by Witaliy · Brute Force

Show categories

Class Name: TheKingsRoadsDiv1

Return Type: String

Method Name: getAnswer

Arg Types: (int, vector<int>, vector<int>)

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 three new roads to the kingdom. (After the addition there may be multiple roads connecting the same pair of cities. Also, some of the new roads may connect some city to itself.)

You are given the int h and two int[]s a and b with (2^h)+1 elements each. For each valid i, there is a road between the cities a[i] and b[i].

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.

Examples

3
{1, 3, 2, 2, 3, 7, 1, 5, 4}
{6, 5, 4, 7, 4, 3, 3, 1, 7}
Returns: "Correct"

One possibility is that city 3 was built during the first year, cities 1 and 4 during the second year, and the other four cities during the third year. Then the King added the roads 3-5, 2-7, and 7-3.

2
{1, 2, 1, 3, 3}
{2, 1, 2, 3, 3}
Returns: "Incorrect"

3
{1, 3, 2, 2, 6, 6, 4, 4, 7}
{2, 1, 4, 5, 4, 4, 7, 7, 6}
Returns: "Incorrect"

2
{1, 2, 2, 1, 1}
{1, 2, 2, 1, 2}
Returns: "Incorrect"

3
{6, 3, 2, 3, 7, 4, 4, 1, 2}
{7, 1, 5, 6, 1, 2, 3, 6, 7}
Returns: "Correct"

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

Coding Area

Language: C++17 · define a public class TheKingsRoadsDiv1 with a public method string getAnswer(int h, vector<int> a, vector<int> b) · 126 test cases · 2 s / 256 MB per case