## Sunday, November 30, 2014

### UVa Problem 910 - TV game

Problem:

Solution:

Typical path counting problem, just keep the path count on the node and iterates, just like in project Euler problem 15 (my solution).

Code:

#include "stdafx.h"

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

#include "UVa910.h"

#include <iostream>
#include <vector>

using namespace std;

int UVa910()
{
while (true)
{
int number_of_nodes;
cin >> number_of_nodes;
if (cin.eof())
{
break;
}
vector<bool> mode;
mode.resize(number_of_nodes);
for (int i = 0; i < number_of_nodes; i++)
{
char from;
char to1;
char to2;
char mode_char;
cin >> from;
cin >> to1;
cin >> to2;
cin >> mode_char;
adjacency_list[from - 'A'][0] = to1 - 'A';
adjacency_list[from - 'A'][1] = to2 - 'A';
mode[from - 'A'] = (mode_char == 'x');
}
int steps;
cin >> steps;

// Step 2: Dynamic programming
vector<int> old_ways;
vector<int> new_ways;
old_ways.resize(number_of_nodes);
new_ways.resize(number_of_nodes);

for (int i = 0; i < number_of_nodes; i++)
{
old_ways[i] = 0;
}
old_ways[0] = 1;

for (int s = 0; s < steps; s++)
{
for (int n = 0; n < number_of_nodes; n++)
{
new_ways[n] = 0;
}
for (int n = 0; n < number_of_nodes; n++)
{
}
for (int n = 0; n < number_of_nodes; n++)
{
old_ways[n] = new_ways[n];
}
}

int win_ways = 0;
for (int n = 0; n < number_of_nodes; n++)
{
if (mode[n])
{
win_ways += old_ways[n];
}
}
cout << win_ways << endl;
}

return 0;
}

### 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;
}

### UVa Problem 10243 - Fire! Fire!! Fire!!!

Problem:

Solution:

This is a minimum vertex cover on tree problem. .

For each node v, we wanted to compute two counts. The minimum vertex cover size for the subtree rooted at v, and the minimum vertex cover size for the subtree root at v if v has to be in the cover.

Pick an arbitrary node as root, we have two cases, for leaf and for internal nodes. For leaf, this is easy, if the leaf has a parent, and the parent is in the cover, then the leaf is not in the cover, otherwise the leaf has to be in the cover.

For internal node, there are two possibilities, either it is in the cover or not. If it is in the cover, then all the children node can be free to include itself in the cover or not. Otherwise, all children must be in the cover.

That's the crux of the algorithm, the code is short, dfs is used to determine if the node is a leaf or not, recurrence relation applied on stack unwind.

Code:

#include "stdafx.h"

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

#include "UVa10243.h"

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

pair<int, int> UVa10243_dfs(int parent, int current, vector<vector<int> >& adjacency_list)
{
vector<pair<int, int> > results;
{
if (*ai != parent)
{
}
}

if (results.size() == 0)
{
// Leaf case
if (parent != -1)
{
return pair<int, int>(0, 1);
}
else
{
return pair<int, int>(1, 1);
}
}
else
{
int free_sum = 0;
int force_sum = 0;
for (vector<pair<int, int> >::iterator ri = results.begin(); ri != results.end(); ri++)
{
free_sum += ri->first;
force_sum += ri->second;
}

int selected_result = 1 + free_sum;
int not_selected_result = force_sum;

return pair<int, int>(min(selected_result, not_selected_result), selected_result);
}
}

int UVa10243()
{
while (true)
{
int number_of_galleries;
cin >> number_of_galleries;
if (number_of_galleries == 0)
{
break;
}
for (int i = 0; i < number_of_galleries; i++)
{
for (int a = 0; a < number_of_adjacent_galleries; a++)
{
}
}

// Step 2: dfs for the answer
pair<int, int> result = UVa10243_dfs(-1, 0, adjacency_list);
cout << result.first << endl;
}

return 0;
}

### UVa Problem 590 - Always on the run

Problem:

Solution:

This is a variation of the Bellman Ford algorithm for graph shortest path. Just keep track of the minimum cost of reaching a certain city on certain day, that's it.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=531

// #define LOG

#include "UVa590.h"

#include <iostream>
#include <vector>

using namespace std;

int UVa590()
{
int test_case_number = 0;
while (true)
{
test_case_number++;
int number_of_cities, number_of_flights;
cin >> number_of_cities;
cin >> number_of_flights;
if ((number_of_cities == 0) && (number_of_flights == 0))
{
break;
}

// Step 1: Allocation
vector<vector<vector<int> > > flight_schedules;
flight_schedules.resize(number_of_cities);
for (int src = 0; src < number_of_cities; src++)
{
flight_schedules[src].resize(number_of_cities);
}

for (int src = 0; src < number_of_cities; src++)
{
for (int dst = 0; dst < number_of_cities; dst++)
{
if (src != dst)
{
int period;
cin >> period;
flight_schedules[src][dst].resize(period);
for (int p = 0; p < period; p++)
{
cin >> flight_schedules[src][dst][p];
}
}
}
}

// Step 3: Bellman-ford
vector<int> old_cost;
vector<bool> old_reachable;
vector<int> new_cost;
vector<bool> new_reachable;
old_cost.resize(number_of_cities);
new_cost.resize(number_of_cities);
old_reachable.resize(number_of_cities);
new_reachable.resize(number_of_cities);

// Step 3.1: Initialize old_cost to be 0, only cities 0 is reachable
for (int c = 0; c < number_of_cities; c++)
{
old_cost[c] = 0;
old_reachable[c] = (c == 0);
}

// Step 3.2: Relaxation
for (int k = 0; k < number_of_flights; k++)
{
for (int c = 0; c < number_of_cities; c++)
{
new_reachable[c] = false;
}

for (int dst = 0; dst < number_of_cities; dst++)
{
bool first = true;
for (int src = 0; src < number_of_cities; src++)
{
if (old_reachable[src] && src != dst)
{
int period = flight_schedules[src][dst].size();
int day_in_period = k % period;
int cost = flight_schedules[src][dst][day_in_period];
if (cost > 0)
{
new_reachable[dst] = true;
if (first)
{
new_cost[dst] = old_cost[src] + cost;
first = false;
}
else
{
new_cost[dst] = min(new_cost[dst], old_cost[src] + cost);
}
}
}
}
}

// Copy new to old
for (int c = 0; c < number_of_cities; c++)
{
old_cost[c] = new_cost[c];
old_reachable[c] = new_reachable[c];
}
#ifdef LOG
cout << "On day " << k << " we have: ";
for (int c = 0; c < number_of_cities; c++)
{
if (old_reachable[c])
{
cout << old_cost[c] << " ";
}
else
{
cout << "X" << " ";
}
}
cout << endl;
#endif
}

// Step 4: Output
cout << "Scenario #" << test_case_number << endl;
if (old_reachable[number_of_cities - 1])
{
cout << "The best flight costs " << old_cost[number_of_cities - 1] << "." << endl;
}
else
{
cout << "No flight possible." << endl;
}

cout << endl;
}
return 0;
}

### UVa Problem 10651 - Pebble Solitaire

Problem:

Solution:

By modeling the game states as a graph, we can easily BFS the graph to find out all reachable states, and keep track with the state with minimum pebble count.

This one is NOT dynamic programming either. But I did use bitmask to make game state representation easy.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/external/106/10651.html

#include "UVa10651.h"

#include <iostream>
#include <queue>

using namespace std;

{
int game = 0;
int bit = 1 << 11;
for (int p = 0; p < 12; p++)
{
char c = cin.get();
if (c == 'o')
{
game = game | bit;
}
bit = bit >> 1;
}

return game;
}

int UVa10651()
{
int number_of_test_case;
cin >> number_of_test_case;
for (int c = 0; c < number_of_test_case; c++)
{
cin.get(); // eliminate the endline
bool enqueued[4096];
queue<int> bfs_queue;
for (int i = 0; i < 4096; i++)
{
enqueued[i] = false;
}

bfs_queue.push(game);
enqueued[game] = true;

int min_piece = 13; // there are at most 12 pieces, so this is basically infinitely

while (!bfs_queue.empty())
{
int current = bfs_queue.front();
bfs_queue.pop();
int num_piece = 0;
for (int p = 0; p < 12; p++)
{
if ((current & (1 << p)) != 0)
{
num_piece++;
}
}
min_piece = min(min_piece, num_piece);

for (int p = 11; p >= 2; p--)
{
int m1 = 1 << p;
int m2 = 1 << (p - 1);
int m3 = 1 << (p - 2);

// 1 1 0 case
if (((current & m1) != 0) && ((current & m2) != 0) && ((current & m3) == 0))
{
// 0 0 1
int new_game = current - m1 - m2 + m3;
if (!enqueued[new_game])
{
bfs_queue.push(new_game);
enqueued[new_game] = true;
}
}

// 0 1 1 case
if (((current & m1) == 0) && ((current & m2) != 0) && ((current & m3) != 0))
{
// 1 0 0
int new_game = current + m1 - m2 - m3;
if (!enqueued[new_game])
{
bfs_queue.push(new_game);
enqueued[new_game] = true;
}
}
}
}

cout << min_piece << endl;
}

return 0;
}