TheKingsRoadsDiv2 | Topcoder Archive

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 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".

Definition

Class:: TheKingsRoadsDiv2
Method:: getAnswer
Parameters:: int, int[], int[]
Returns:: String
Method signature:: String getAnswer(int h, int[] a, int[] b)
(be sure your method is public)

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, 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"
```

{7, 1, 1, 2, 2, 3, 1}

{7, 1, 7, 4, 5, 2, 6}

Returns: "Incorrect"

```
2
```
```
{1, 3, 3}
```
```
{2, 1, 2}
```
```
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.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.