PermuteTheArray
TCO19 SRM 743 · 2018-12-08 · by boba5551
Problem Statement
Your task is to produce a specific permutation P of the given
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
If no such P exists, return the empty
Notes
- int[] X is lexicographically smaller than int[] Y of the same size iff there exists an index i such that for all j < 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.
{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.
{3, 5, 7, 11, 100}
{0, 2, 1}
{2, 4, 3}
{1, 1, 0}
Returns: {3, 5, 100, 7, 11 }
P[0] + P[2] must be odd, P[2] + P[4] must be odd, and P[1] + P[3] must be even. From these constraints we can deduce that P[2] must be 100 and the other four values may be in any order we like. Thus, the lexicographically smallest valid permutation is {3, 5, 100, 7, 11}.
Submissions are judged against all 87 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PermuteTheArray with a public method vector<int> getPermutation(vector<int> A, vector<int> x, vector<int> y, vector<int> d) · 87 test cases · 2 s / 256 MB per case