Codeforces Solution | 1472B: Fair Division

Problem Description:

The first line of input contains one integer t \((1≤t≤104)\) — the number of test cases.

The first line of each test case contains an integer n \((1≤n≤100) \)— the number of candies that Alice and Bob received.

The next line contains n integers \(a_1,a_2,…,a_n\) — the weights of the candies. The weight of each candy is either 1 or 2.

Now we have to divide all candies so that the total weight of Alice's candies is equal to the total weight of Bob's candies. But, candies are not allowed to be cut in half. If it is possible to divide fairly, then output will be ‘YES’. ‘NO’ otherwise.

Ideological Analysis:

• If the total weight is odd, then it is impossible to divide in two parts equally. So, the output will be ‘NO’.
  For example,
  \(n = 3\)
  \(a_1 = 2\), \(a_2 = 1\), \(a_3 = 2\)
  \(a_1 + a_2 + a_3 = 5\)
  5 is odd and it is impossible to divide in two equal part as candies are not allowed to cut in half.


• If the total weight is even, but number of candies is odd and weight of every candy is same, then it is impossible to divide in two parts.
  For example,
  \(n = 3\)
  \(a_1 = 2, a_2 = 2, a_3 = 2\)
  Though total weight is even, we can not divide them equally as we can not cut a candy in half. So, the output will be ‘NO’.


• In every cases except these two, the output will be ‘YES’.

Click here for Source Code.