## Sunday, November 30, 2014

### UVa Problem 10891 - Game of Sum

Problem:

Solution:

Dynamic programming is applied here. The key is that part of an optimal strategy is also an optimal strategy, so we can build up the optimal strategies with increasing length.

The optimal strategy with just 1 element is deceptively simple. Just pick the value.

The optimal strategy for a subarray with k elements can have 2k - 1 choices. If we left anything for out opponent, he will choose the best strategy, so in that case we have already know what that strategy is, and therefore we know what is the end difference. Just choose the one with the best end difference, that is the optimal strategy.

With that, the code is easy. Note how to loop through the set of sub-sequences.

Code:

#include "stdafx.h"

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

#include "UVa10891.h"

// #define LOG

#include <iostream>
#include <vector>

using namespace std;

struct UVa10891_strategy
{
int start_index;
int end_index;
int strategy_value;
};

int UVa10891()
{
while (true)
{
// Step 1: Input
int number_of_elements;
cin >> number_of_elements;
if (number_of_elements == 0)
{
break;
}

vector<int> elements;
elements.resize(number_of_elements);
for (int i = 0; i < number_of_elements; i++)
{
int element;
cin >> element;
elements[i] = element;
}

// Step 2: Pre compute running sum
vector<int> element_sums;
element_sums.resize(number_of_elements + 1);
int element_sum = 0;
for (int i = 0; i < number_of_elements; i++)
{
element_sums[i] = element_sum;
element_sum += elements[i];
}
element_sums[number_of_elements] = element_sum;

// element_sums[b + 1] - element_sums[a] = sum(i = a to b) elements[i]

// Step 3: Dynamic programming
vector<vector<UVa10891_strategy> > optimal_strategies;
optimal_strategies.resize(number_of_elements);
for (int start = 0; start < number_of_elements; start++)
{
optimal_strategies[start].resize(number_of_elements);
}

for (int length = 1; length <= number_of_elements; length++)
{
for (int start = 0; (start + length - 1) < number_of_elements; start++)
{
int end = start + length - 1;
if (length == 1)
{
// There is only one element - we have no choice but to pick this number
optimal_strategies[start][end].start_index = start;
optimal_strategies[start][end].end_index = start;
optimal_strategies[start][end].strategy_value = elements[start];
#ifdef LOG
cout << "optimal_strategies[" << start << "][" << end << "] = (" << optimal_strategies[start][end].start_index << ", " << optimal_strategies[start][end].end_index << ") = " << optimal_strategies[start][end].strategy_value << endl;
#endif
}
else
{
optimal_strategies[start][end].start_index = start;
optimal_strategies[start][end].end_index = end;
optimal_strategies[start][end].strategy_value = element_sums[end + 1] - element_sums[start];
for (int p = start; p < end; p++)
{
// Consider I am choosing [start, p]
int strategy_value = element_sums[p + 1] - element_sums[start];
UVa10891_strategy opponent_strategy = optimal_strategies[p + 1][end];
strategy_value -= opponent_strategy.strategy_value;
if (strategy_value > optimal_strategies[start][end].strategy_value)
{
optimal_strategies[start][end].strategy_value = strategy_value;
optimal_strategies[start][end].start_index = start;
optimal_strategies[start][end].end_index = p;
}
}
for (int q = end; q > start; q--)
{
// Consider I am choosing [q, end]
int strategy_value = element_sums[end + 1] - element_sums[q];
UVa10891_strategy opponent_strategy = optimal_strategies[start][q - 1];
strategy_value -= opponent_strategy.strategy_value;
if (strategy_value > optimal_strategies[start][end].strategy_value)
{
optimal_strategies[start][end].strategy_value = strategy_value;
optimal_strategies[start][end].start_index = q;
optimal_strategies[start][end].end_index = end;
}
}
#ifdef LOG
cout << "optimal_strategies[" << start << "][" << end << "] = (" << optimal_strategies[start][end].start_index << ", " << optimal_strategies[start][end].end_index << ") = " << optimal_strategies[start][end].strategy_value << endl;
#endif
}
}
#ifdef LOG
cout << endl;
#endif
}

UVa10891_strategy optimal_strategy = optimal_strategies[0][number_of_elements - 1];
cout << optimal_strategy.strategy_value << endl;
}
return 0;
}