SortArray | Topcoder Archive

Problem Statement

Given is an int N and an algorithm that rearranges elements in an array of length N. The claim is that the algorithm correctly sorts each possible array of length N. Your task is to verify this claim.

The algorithm is a sequence of instructions described by the int[] commands. Each command has the form "sort these elements of the array". More precisely, each element of commands is some N-bit number C representing the instruction "sort the elements of the array whose indices correspond to the set bits of C".

For example, suppose we have the array A = {30, 40, 70, 20, 10} and we receive the command C = 11 = 2^0 + 2^1 + 2^3. This command rearranges the values A[0], A[1], and A[3] into non-descending order. Thus, after the command the new array will be A = {20, 30, 70, 40, 10}.

If the given sequence of commands correctly sorts any array of length N, return an empty int[]. Otherwise, return any permutation of values 0 through N-1 that would not be sorted correctly.

Definition

Class:: SortArray
Method:: verify
Parameters:: int, int[]
Returns:: int[]
Method signature:: int[] verify(int N, int[] commands)
(be sure your method is public)

Constraints

N will be between 1 and 15, inclusive.
commands will contain between 0 and 200 instructions, inclusive.
Each element of commands will be between 1 and 2^N-1, inclusive.

Examples

```
7
```
```
{127}
```
```
Returns: { }
```
The only instruction is "sort the entire array". This program obviously works correctly.
```
8
```
```
{85, 170}
```
```
Returns: {0, 1, 2, 3, 4, 5, 7, 6 }
```
The first instruction sorts the elements at even indices, the second instruction sorts the elements at odd indices. This clearly isn't sufficient. The return value happens to be the lexicographically smallest counterexample, but any other permutation that does not get sorted correctly would be accepted as well.
```
3
```
```
{3, 5, 6}
```
```
Returns: { }
```
Sorting three elements using three pairwise comparisons.
```
10
```
```
{255, 1020}
```
```
Returns: {3, 4, 5, 6, 7, 8, 9, 0, 1, 2 }
```
"Sort elements A[0..7] and then sort elements A[2..9]." This is not a valid sort yet. The permutation given as the example return value would first be rearranged to {0, 3, 4, 5, 6, 7, 8, 9, 1, 2 } and then to {0, 3, 1, 2, 4, 5, 6, 7, 8, 9}.

{255, 1020, 255, 1020, 255, 1020, 255, 1020, 255, 1020}

Returns: { }

... but doing the same thing multiple times in a row seems to work.

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.