Problem Statement | | Fox Ciel has just learned a new skill: she can now split into two copies of herself.
Recently, she practiced this new skill on an infinite horizontal plane.
At the beginning, Fox Ciel was the only fox on the plane, and she was standing at the coordinates (0, 0).
Then, she took a sequence of one or more actions.
Each action looked as follows:
Ciel selected a vector (dx, dy).
Then, simultaneously, each fox on the plane split into two copies.
One copy remained on its current coordinates (x, y), the other moved by the chosen vector to the coordinates (x+dx, y+dy).
Note that after each action multiple foxes may share the same coordinates.
You are given a partial description of the final state of the plane: a list of all positions that contained an odd number of foxes at the end of the above process.
More precisely, you are given the int[]s x and y such that for each valid i the coordinates (x[i], y[i]) contain an odd number of foxes.
Can you recover the vectors chosen during the process?
If there is no valid sequence of vectors that matches the given x and y, return {-1}.
(I.e., the return value should be a int[] with one element: the number minus one.)
If there are multiple valid solutions, you may construct any one of them, as long as it contains 500 or fewer vectors.
It can be shown that whenever a solution exists, a solution with at most 500 vectors exists.
If your solution has k vectors, return a int[] with 2k elements: {dx[0], dy[0], dx[1], dy[1], ..., dx[k-1], dy[k-1]}. Here, each pair (dx[i], dy[i]) is one vector used by Ciel. | | Definition | | Class: | SplittingFoxes4 | Method: | construct | Parameters: | int[], int[] | Returns: | int[] | Method signature: | int[] construct(int[] x, int[] y) | (be sure your method is public) |
| | | | Constraints | - | x will contain between 2 and 500, elements, inclusive. | - | x and y will contain the same number of elements. | - | Each element in x will be between -100 and 100, inclusive. | - | Each element in y will be between -100 and 100, inclusive. | - | (x[i], y[i]) will be distinct. | | Examples | 0) | | | {0,2,3,7,8,10} | {0,0,0,0,0,0} |
| Returns: {2, 0, 3, 0, 5, 0 } | One solution is: we have 3 steps with {dx, dy} = {2, 0}, {3, 0}, {5, 0}.
- After the first step, there are 2 foxes: (0,0), (2,0).
- After the second step, there are 4 foxes: (0,0), (2,0), (3,0), (5,0).
- After the last step, there are 8 foxes: (0,0), (2,0), (3,0), (5,0), (5,0), (7,0), (8,0), (10,0).
There are 6 positions with an odd number of foxes: (0,0), (2,0), (3,0), (7,0), (8,0), (10,0) |
|
| 1) | | | | Returns: {-1 } | We are looking for a sequence of vectors such that there will be exactly three positions with an odd number of foxes.
This is impossible: if there is an odd number of positions with an odd number of foxes, the total number of foxes must be odd.
However, we know that the total number of foxes is a positive power of two, which is an even number. |
|
| 2) | | | {-1,1,0,1,-2,2,3,0} | {0,-2,0,2,-2,-2,0,-4} |
| Returns: {1, 2, -2, -2, 2, -2 } | |
| 3) | | | {0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3} | {0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3} |
| Returns: {1, 0, 2, 0, 0, 1, 0, 2 } | |
| 4) | | | |
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.
|