The two dimensional problem can be solved by two separate one dimensional subproblems.

The one dimensional problem is: Given ~N~ code numbers and a sequence of ~N~ region signs (each of which is ~+~ or ~-~), produce a sequence of ~N~ signed code values ~\{x_i\}~ so that the sign of ~\sum_{i<k} x_i~ matches the ~i^\text{th}~ region sign.

We do this by first sorting the ~N~ input code numbers into increasing order, and then assigning alternating signs to them so that ~|x_i| > |x_{i+1}|~, though ~x_i > 0~ iff ~x_{i+1} < 0~. The key observation is that if we have used a segment ~(x_k, \dots, x_m)~ of the data, then ~0 \le \left| \sum_{k \le i \le m} x_i \right| \le |x_m|~, and the sign of the sum matches that of ~x_m~. If the next code is to reverse the sign, we simply use ~x_{m+1}~, which guarantees the invariant of the last sentence still holds. A similar argument guarantees that using ~x_{k-1}~ retains the sign of the sum.

The next important issue is where to start. Recall that keeping the sign of the sum the same requires taking a new value from the right. So count the number of sign changes in the input sequence of region signs. If this value is ~c~, give ~x_c~ the first input sign, thus determining the alternation. The output can now be produced in a fairly straightforward manner.

Hence there is an ~\mathcal O(N \log N)~ solution that can be coded (if not discovered) quite easily. It is also quite reasonable to solve the problem by backtracking. This leads to an acceptable solution on smaller test cases (up to 8, or with care to 9 or even 10).