DivideJewelry | Topcoder Archive

Problem Statement

Fox Ciel and Fox Jiro just found a box of jewelry. There are n pieces of jewelry in the box. The pieces are numbered 0 through n-1. You are given a int[] x with n elements. For each i, the value of piece i is x[i].

Ciel and Jiro want to divide the jewelry in a fair way. Each fox must take a non-empty subset of the jewelry. Obviously, the two subsets must be disjoint: each piece of jewelry can only be taken by at most one fox. The total value of jewelry taken by Ciel must be exactly the same as the total value of jewelry taken by Jiro.

If there is no valid solution, return an empty int[]. If there are multiple valid solutions, you may choose any of them. Return a int[] res with n elements. For each i:

res[i]=1 denotes that Ciel should take the piece number i
res[i]=-1 denotes that Jiro should take the piece number i
res[i]=0 denotes that piece number i should be left in the box

Definition

Class:: DivideJewelry
Method:: divide
Parameters:: int[]
Returns:: int[]
Method signature:: int[] divide(int[] x)
(be sure your method is public)

Constraints

x will contain between 2 and 1,000 elements, inclusive.
Each element in x will be between 1 and 1,000,000, inclusive.

Examples

```
{1,2,3}
```
```
Returns: {1, 1, -1 }
```
One fox should take pieces 0 and 1, and the other fox should take piece 2. The total value of jewelry taken by each fox will be 3. You may return either {1, 1, -1} or {-1, -1, 1}.
```
{1,2}
```
```
Returns: { }
```
It is impossible to divide these two pieces evenly. Note that each fox must take at least one piece of jewelry.
```
{1,1,2,4,8,16,32}
```
```
Returns: {1, -1, 0, 0, 0, 0, 0 }
```
Here, one easy solution is that one fox takes piece 0 and the other fox takes piece 1. This is a fair division because both pieces have the same value.
```
{1,2,4,8,16,32}
```
```
Returns: { }
```

{534,260,643,230,450,560,430,210}

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

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.