Connection Status:
Competition Arena > SortArray

SortArray

TCO19 SRM 761 · 2019-06-21 · by misof

TCO19 SRM 761 · 2019-06-21 · by misof · Dynamic Programming, Math, Search, Simulation, Sorting
Class Name: SortArray
Return Type: int[]
Method Name: verify
Arg Types: (int, vector<int>)
Problem Statement

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.

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
0)
7
{127}
Returns: { }

The only instruction is "sort the entire array". This program obviously works correctly.

1)
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.

2)
3
{3, 5, 6}
Returns: { }

Sorting three elements using three pairwise comparisons.

3)
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}.

4)
10
{255, 1020, 255, 1020, 255, 1020, 255, 1020, 255, 1020}
Returns: { }

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

5)
15
{ 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767, 32767 }
Returns: { }

The largest possible input, in some sense: a 15-element array and 200 instructions to sort the whole thing.

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

Coding Area

Language: C++17 · define a public class SortArray with a public method vector<int> verify(int N, vector<int> commands) · 99 test cases · 2 s / 256 MB per case

Submitting as anonymous