Connection Status:
Competition Arena > DivideJewelry

DivideJewelry

2016 TCO Regional Wildcard · 2016-03-24 · by cgy4ever

2016 TCO Regional Wildcard · 2016-03-24 · by cgy4ever · Brute Force
Class Name: DivideJewelry
Return Type: int[]
Method Name: divide
Arg Types: (vector<int>)
Problem Statement

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

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
0)
{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)
{1,2}
Returns: { }

It is impossible to divide these two pieces evenly. Note that each fox must take at least one piece of jewelry.

2)
{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.

3)
{1,2,4,8,16,32}
Returns: { }
4)
{534,260,643,230,450,560,430,210}
Returns: {0, 0, 0, 1, -1, 0, 1, -1 }

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

Coding Area

Language: C++17 · define a public class DivideJewelry with a public method vector<int> divide(vector<int> x) · 126 test cases · 2 s / 256 MB per case

Submitting as anonymous