Connection Status:
Competition Arena > SplittingFoxes4

SplittingFoxes4

2017 TCO Final · 2017-03-31 · by cgy4ever

2017 TCO Final · 2017-03-31 · by cgy4ever · Dynamic Programming, Geometry
Class Name: SplittingFoxes4
Return Type: int[]
Method Name: construct
Arg Types: (vector<int>, vector<int>)
Problem Statement

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.

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)
{1,2,3}
{4,5,6}
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)
{0,100}
{0,100}
Returns: {100, 100 }

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

Coding Area

Language: C++17 · define a public class SplittingFoxes4 with a public method vector<int> construct(vector<int> x, vector<int> y) · 188 test cases · 2 s / 256 MB per case

Submitting as anonymous