{"trustable":true,"prependHtml":"\u003cstyle\u003e.statText pre { font-size: 12px; }\ntable {display:block !important; width:100%; }\ntable tbody {display:block !important; width:100%; }\ntable tbody tr { width:100% !important;display: block;}\ntable tbody tr td.statText { margin-left: 5px; display: inline-block; width: fit-content; }\ntable tbody tr td.statText br { display: block; content: \" \";line-height: 12px;margin: 12px 0;}\ntable tbody tr td.statText table table pre {\n white-space: pre-wrap;\n text-overflow: ellipsis;\n word-break: break-all;\n}\u003c/style\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\n \u003ch3\u003eProblem Statement\u003c/h3\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003eFox 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. \u003cbr\u003eAt 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. \u003cbr\u003eYou are given a partial description of the final state of the plane: a list of \u003ci\u003eall\u003c/i\u003e positions that contained an \u003ci\u003eodd\u003c/i\u003e number of foxes at the end of the above process. More precisely, you are given the int[]s \u003cb\u003ex\u003c/b\u003e and \u003cb\u003ey\u003c/b\u003e such that for each valid i the coordinates (\u003cb\u003ex\u003c/b\u003e[i], \u003cb\u003ey\u003c/b\u003e[i]) contain an odd number of foxes. Can you recover the vectors chosen during the process? \u003cbr\u003eIf there is no valid sequence of vectors that matches the given \u003cb\u003ex\u003c/b\u003e and \u003cb\u003ey\u003c/b\u003e, return {-1}. (I.e., the return value should be a int[] with one element: the number minus one.) \u003cbr\u003eIf 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. \u003cbr\u003eIf 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.\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u0026nbsp;\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\n \u003ch3\u003eDefinition\u003c/h3\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003eClass:\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003eSplittingFoxes4\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003eMethod:\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003econstruct\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003eParameters:\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003eint[], int[]\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003eReturns:\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003eint[]\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003eMethod signature:\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003eint[] construct(int[] x, int[] y)\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e(be sure your method is public)\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u0026nbsp;\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\n \u003ch3\u003eConstraints\u003c/h3\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" valign\u003d\"top\" class\u003d\"statText\"\u003e-\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\u003cb\u003ex\u003c/b\u003e will contain between 2 and 500, elements, inclusive.\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" valign\u003d\"top\" class\u003d\"statText\"\u003e-\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\u003cb\u003ex\u003c/b\u003e and \u003cb\u003ey\u003c/b\u003e will contain the same number of elements.\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" valign\u003d\"top\" class\u003d\"statText\"\u003e-\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003eEach element in \u003cb\u003ex\u003c/b\u003e will be between -100 and 100, inclusive.\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" valign\u003d\"top\" class\u003d\"statText\"\u003e-\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003eEach element in \u003cb\u003ey\u003c/b\u003e will be between -100 and 100, inclusive.\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" valign\u003d\"top\" class\u003d\"statText\"\u003e-\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e(\u003cb\u003ex\u003c/b\u003e[i], \u003cb\u003ey\u003c/b\u003e[i]) will be distinct.\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u0026nbsp;\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\n \u003ch3\u003eExamples\u003c/h3\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" nowrap\u003d\"true\" class\u003d\"statText\"\u003e0)\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003e{0,2,3,7,8,10}\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003e{0,0,0,0,0,0}\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003eReturns: {2, 0, 3, 0, 5, 0 }\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003eOne solution is: we have 3 steps with {dx, dy} \u003d {2, 0}, {3, 0}, {5, 0}. \n \u003cul\u003e\n \u003cli\u003eAfter the first step, there are 2 foxes: (0,0), (2,0).\u003c/li\u003e\n \u003cli\u003eAfter the second step, there are 4 foxes: (0,0), (2,0), (3,0), (5,0).\u003c/li\u003e\n \u003cli\u003eAfter the last step, there are 8 foxes: (0,0), (2,0), (3,0), (5,0), (5,0), (7,0), (8,0), (10,0).\u003c/li\u003e\n \u003c/ul\u003e There are 6 positions with an odd number of foxes: (0,0), (2,0), (3,0), (7,0), (8,0), (10,0)\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" nowrap\u003d\"true\" class\u003d\"statText\"\u003e1)\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003e{1,2,3}\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003e{4,5,6}\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003eReturns: {-1 }\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003eWe 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.\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" nowrap\u003d\"true\" class\u003d\"statText\"\u003e2)\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003e{-1,1,0,1,-2,2,3,0}\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003e{0,-2,0,2,-2,-2,0,-4}\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003eReturns: {1, 2, -2, -2, 2, -2 }\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" nowrap\u003d\"true\" class\u003d\"statText\"\u003e3)\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003e{0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3}\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003e{0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3}\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003eReturns: {1, 0, 2, 0, 0, 1, 0, 2 }\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd align\u003d\"center\" nowrap\u003d\"true\" class\u003d\"statText\"\u003e4)\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003e{0,100}\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003e{0,100}\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003cpre\u003eReturns: {100, 100 }\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd class\u003d\"statText\"\u003e\n \u003ctable\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n\u003c/table\u003e\n\u003chr\u003e\n\u003cp\u003eThis 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)2023, TopCoder, Inc. All rights reserved.\u003c/p\u003e"}}]}