## Monday, November 10, 2014

### UVa Problem 562 - Dividing coins

Problem:

Solution:

Set partition problem, classic. To make the problem simpler, we know one of the person must take at most half of the value, and the other take at least half of it. So let's determine which coin the former person takes.

Suppose the coin sequence is something like

2, 5, 3

The person can only achieve a value of 0 before considering any coin.

Considering 2, the person could choose to take it or not, so he can now achieve {0, 2}.

Considering 5, the person could choose to take it or not, so he can now achieve, {0, 2, 5, 7}, this set is computed by copying the previous set (achievable by not taking it) union with the set {0,2} + 5.

But in this case, we do not worry about the value 7, since it is larger than half, the first person is not allowed to take more than half, so the set becomes { 0, 2, 5 }

Moving on consider 3, the person can now achieve, {0, 2, 5} union {3, 5, 8} = {0, 2, 3, 5, 8}.

Now the first person can achieve exactly half, so will the another person, in this case the difference is 0.

The algorithm is correct, but expanding like this in a recursion would lead to exponential size. The trick is to leverage the fact that there are at most 100 * 500c = 50000c, and half of it is just 25,000. Instead of dealing with sets, deal with values. When considering any coin, loop through the existing achievable values, plus the current coin value, and mark it as achievable. That will make us loop at most 500 x 25,000 times, enough for acceptance.

Last but not least, beware of the problem statement that $n$ can be a non-negative integer, which could be zero. I just make it a special case. Feeling bad about WA, now I learnt to test for special cases.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=503

#include "UVa562.h"

#include <iostream>
#include <vector>

using namespace std;

int UVa562()
{
int number_of_test_cases;
cin >> number_of_test_cases;
for (int c = 0; c < number_of_test_cases; c++)
{
int num_items;
cin >> num_items;
if (num_items > 100)
{
throw 0;
}
if (num_items == 0)
{
cout << 0 << endl;
continue;
}
vector<int> item_values;
item_values.resize(num_items);
int item_value_sum = 0;
for (int i = 0; i < num_items; i++)
{
int item_value;
cin >> item_value;
if (item_value < 1)
{
throw 0;
}
if (item_value > 500)
{
throw 0;
}
item_values[i] = item_value;
item_value_sum += item_value;
}
if (item_value_sum < 1)
{
throw 0;
}
if (item_value_sum > 50000)
{
throw 0;
}

int best_lower_value = item_value_sum / 2;

vector<bool> last_achievable;
vector<bool> achievable;

last_achievable.resize(best_lower_value + 1);
achievable.resize(best_lower_value + 1);

// Initialization - with no coin at all, the only achievable value is 0
for (int v = 0; v <= best_lower_value; v++)
{
last_achievable[v] = (v == 0);
}

for (int i = 0; i < num_items; i++)
{
int current_item_value = item_values[i];

// Initialization - before we consider the coin, we can already achieve what was achievable
for (int v = 0; v <= best_lower_value; v++)
{
achievable[v] = last_achievable[v];
}

for (int v = 0; v <= best_lower_value; v++)
{
if (last_achievable[v])
{
int next_achievable_value = v + current_item_value;
if (next_achievable_value <= best_lower_value)
{
achievable[next_achievable_value] = true;
}
}
}

for (int v = 0; v <= best_lower_value; v++)
{
last_achievable[v] = achievable[v];
}
}

int achievable_best_lower_value = -1;
for (int v = best_lower_value; v >= 0; v--)
{
if (achievable[v])
{
achievable_best_lower_value = v;
break;
}
}
cout << item_value_sum - achievable_best_lower_value - achievable_best_lower_value << endl;
}

return 0;
}