PermuteTheArray | Topcoder Archive

Problem Statement

Your task is to produce a specific permutation P of the given int[] A.

The permutation P we seek is the lexicographically smallest one among all permutations that satisfy a set of constraints. You are given a description of these constraints in the int[]s x, y, and d. For each valid i, P must satisfy the following constraint: ( P[ x[i] ] + P[ y[i] ] ) mod 2 = d[i].

If no such P exists, return the empty int[]. Otherwise, return the lexicographically smallest P.

Definition

Class:: PermuteTheArray
Method:: getPermutation
Parameters:: int[], int[], int[], int[]
Returns:: int[]
Method signature:: int[] getPermutation(int[] A, int[] x, int[] y, int[] d)
(be sure your method is public)

Notes

int[] X is lexicographically smaller than int[] Y of the same size iff there exists an index i such that for all j &lt i we have X[j] = Y[j], and we have (X[i] < Y[i]).

Constraints

A will contain n elements.
n will be between 1 and 250 elements, inclusive.
Each element of A will be between 1 and 100,000, inclusive.
x will contatin between 0 and 1,000 elements, inclusive.
x and y will contain the same number of elements.
x and d will contain the same number of elements.
For each valid i: 0 ≤ x[i] < y[i] < n.
For each valid i ≠ j: x[i] ≠ x[j] or y[i] ≠ y[j].
Each element of d will be 0 or 1.

Examples

```
{1, 3, 5, 2}
```
```
{0}
```
```
{1}
```
```
{0}
```
```
Returns: {1, 3, 2, 5 }
```
The permutation P = {1, 3, 2, 5} is valid, as ( P[x[0]] + P[y[0]] ) mod 2 = (P[0] + P[1]) mod 2 = (1 + 3) mod 2 = 0 = d[0]. Some other valid permutations are {1, 3, 5, 2}, {1, 5, 2, 3}, {1, 5, 3, 2}, {3, 1, 2, 5}, {5, 3, 2, 1}, but {1, 3, 2, 5} is the lexicographically smallest one among them.
```
{1, 3, 5, 2}
```
```
{0, 1, 0, 1, 2}
```
```
{1, 2, 3, 3, 3}
```
```
{0, 0, 1, 1, 0}
```
```
Returns: { }
```
It can be shown that there is no valid permutation of {1, 3, 5, 2} that satisfies the conditions imposed by the provided x, y and d.

{1, 3, 2, 5}

{0, 1, 0, 1, 2}

{1, 2, 3, 3, 3}

{0, 0, 1, 1, 1}

Returns: {1, 3, 5, 2 }

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

{0, 0, 1, 5, 6}

{1, 2, 2, 6, 7}

{0, 0, 0, 0, 1}

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

{20, 546, 23, 20, 4, 573, 1, 3, 665, 32, 329, 54, 23, 9}

{}

{}

{}

Returns: {1, 3, 4, 9, 20, 20, 23, 23, 32, 54, 329, 546, 573, 665 }

Any permutation of A is valid here.

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.