XorPuzzle

SRM 686 · 2016-03-02 · by Arterm

SRM 686 · 2016-03-02 · by Arterm · Graph Theory, Math, Simple Search, Iteration

Show categories

Class Name: XorPuzzle

Return Type: int[]

Method Name: find

Arg Types: (int, vector<int>)

Problem Statement

You are given an int k and a int[] a of length n. The value k is positive. Each element of a is between 0 and (2^k)-1, inclusive.

Your task is to find int[]s b and c with the following properties:

b and c must contain n elements each
each element of b and c must be between 0 and (2^k)-1, inclusive.
the elements of b must be distinct
the elements of c must be distinct
for each valid i, a[i] must be equal to (b[i] xor c[i]).

If there is no such b and c, return {-1}. (I.e., a int[] with a single element that is -1.) Otherwise, return a int[] with 2n elements: the concatenation of b and c. If there are multiple valid solutions, you may return any of them.

Constraints

k will be between 1 and 10, inclusive.
a will contain between 1 and 2 ^ k elements, inclusive.
Each element of a will be between 0 and (2 ^ k) - 1, inclusive.

Examples

2
{1, 2, 3}
Returns: {2, 3, 1, 3, 1, 2 }

One can choose b = {2, 3, 1} and c = {3, 1, 2}. 1 = 2 ^ 3, 2 = 3 ^ 1, 3 = 1 ^ 2.

2
{1, 1, 1}
Returns: {1, 0, 3, 0, 1, 2 }

b = {1, 0, 3}, c = {0, 1, 2}. 1 = 1 ^ 0 = 0 ^ 1 = 3 ^ 2.

1
{0}
Returns: {0, 0 }

b = c = {0}

1
{0, 1}
Returns: {-1 }

There is no answer.

10
{123, 23, 32, 21, 12, 123}
Returns: {5, 63, 19, 40, 51, 126, 126, 40, 51, 61, 63, 5 }

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

Coding Area

Language: C++17 · define a public class XorPuzzle with a public method vector<int> find(int k, vector<int> a) · 166 test cases · 2 s / 256 MB per case