## Wednesday, December 31, 2014

### UVa Problem 821 - Page Hopping

Problem:

Solution:

Obviously, we should run all pairs shortest paths! Can't believe this is a real contest problem!

Code:

#include "stdafx.h"

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

#include "UVa821.h"

#include <iostream>
#include <vector>
#include <map>
#include <iomanip>

using namespace std;

int UVa186_assign_node_number(map<int, int>& node_numbers, map<int, int>& node_namings, int node_name);

int UVa821()
{
int test_case = 0;
while (true)
{
test_case++;
vector<pair<int, int>> edges;
map<int, int> node_namings;
map<int, int> node_numbers;
while (true)
{
int src_name;
int dst_name;
cin >> src_name;
cin >> dst_name;
if (src_name == 0 && dst_name == 0)
{
break;
}

int src_number = UVa186_assign_node_number(node_numbers, node_namings, src_name);
int dst_number = UVa186_assign_node_number(node_numbers, node_namings, dst_name);

edges.push_back(pair<int, int>(src_number, dst_number));
}
if (edges.size() == 0)
{
break;
}

// Step 2: Produce the data structures for Floyd Warshall
int number_of_nodes = node_numbers.size();

vector<vector<int> > distances;
vector<vector<bool> > reachable;
vector<vector<int> > path;
distances.resize(number_of_nodes);
reachable.resize(number_of_nodes);
path.resize(number_of_nodes);
for (int src = 0; src < number_of_nodes; src++)
{
distances[src].resize(number_of_nodes);
reachable[src].resize(number_of_nodes);
path[src].resize(number_of_nodes);

for (int dst = 0; dst < number_of_nodes; dst++)
{
distances[src][dst] = -1;
reachable[src][dst] = false;
path[src][dst] = -1;
}
}

for (unsigned int e = 0; e < edges.size(); e++)
{
pair<int, int> edge = edges[e];
int src = edge.first;
int dst = edge.second;

// Beware of the input could have multiple edges!
distances[src][dst] = 1;
reachable[src][dst] = true;
path[src][dst] = dst;
}

for (int k = 0; k < number_of_nodes; k++)
{
for (int src = 0; src < number_of_nodes; src++)
{
for (int dst = 0; dst < number_of_nodes; dst++)
{
if (reachable[src][k] && reachable[k][dst]) // relaxation is possible if the proposal is valid
{
int current_distance = distances[src][dst];
int propose_distance = distances[src][k] + distances[k][dst];
if (!reachable[src][dst] || propose_distance < current_distance)
{
distances[src][dst] = propose_distance;
reachable[src][dst] = true;
path[src][dst] = path[src][k];
}
}
}
}
}

int sum = 0;
int count = 0;
for (int src = 0; src < number_of_nodes; src++)
{
for (int dst = 0; dst < number_of_nodes; dst++)
{
if (src != dst)
{
sum += distances[src][dst];
count++;
}
}
}
cout << "Case " << test_case << ": average length between pages = " << setprecision(3) << fixed << ((double)sum) / count << " clicks" << endl;
}

return 0;
}

int UVa186_assign_node_number(map<int, int>& node_numbers, map<int, int>& node_namings, int node_name)
{
int node_number;
map<int, int>::iterator probe = node_numbers.find(node_name);
if (probe == node_numbers.end())
{
node_number = node_numbers.size();
node_numbers.insert(pair<int, int>(node_name, node_number));
node_namings.insert(pair<int, int>(node_number, node_name));
}
else
{
node_number = probe->second;
}

return node_number;
}

### UVa Problem 423 - MPI Maelstrom

Problem:

Solution:

Standard single source shortest paths problem. Dijkstra works best for this.

Code:

#include "stdafx.h"

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

#include "UVa423.h"

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

using namespace std;

bool UVa423_less(vector<int>& distances, vector<bool>& reachable, int one, int two);
void UVa423_bubble_down(vector<int>& dijkstra_queue, vector<int>& distances, vector<bool>& reachable, vector<int>& node_index, int& queue_size, int parent_index);
int UVa423_delete_min(vector<int>& dijkstra_queue, vector<int>& distances, vector<bool>& reachable, vector<int>& node_index, int& queue_size);
void UVa423_change_key(vector<int>& dijkstra_queue, vector<int>& distances, vector<bool>& reachable, vector<int>& node_index, int& queue_size, int changed_node);
void UVa423_dijkstra(int src, vector<vector<pair<int, int> > >& adjacency_list, vector<int>& distances);

int UVa423()
{
int number_of_nodes;
cin >> number_of_nodes;
string entry;
for (int src = 0; src < number_of_nodes; src++)
{
for (int dst = 0; dst < src; dst++)
{
cin >> entry;
if (entry != "x")
{
int cost = stoi(entry);
}
}
}

// Step 2: Dijkstra
vector<int> distances;

cout << *max_element(distances.begin(), distances.end()) << endl;

return 0;
}

bool UVa423_less(vector<int>& distances, vector<bool>& reachable, int one, int two)
{
if (reachable[one])
{
if (reachable[two])
{
return distances[one] < distances[two];
}
else
{
return true;
}
}
else
{
return false;
}
}

void UVa423_bubble_down(vector<int>& dijkstra_queue, vector<int>& distances, vector<bool>& reachable, vector<int>& node_index, int& queue_size, int parent_index)
{
while (true)
{
int child2_index = (parent_index + 1) * 2;
int child1_index = child2_index - 1;

if (child2_index < queue_size)
{
int parent_value = dijkstra_queue[parent_index];
int child1_value = dijkstra_queue[child1_index];
int child2_value = dijkstra_queue[child2_index];

if (UVa423_less(distances, reachable, child1_value, child2_value))
{
if (UVa423_less(distances, reachable, child1_value, parent_value))
{
dijkstra_queue[parent_index] = child1_value;
dijkstra_queue[child1_index] = parent_value;
node_index[parent_value] = child1_index;
node_index[child1_value] = parent_index;
parent_index = child1_index;
}
else
{
break;
}
}
else
{
if (UVa423_less(distances, reachable, child2_value, parent_value))
{
dijkstra_queue[parent_index] = child2_value;
dijkstra_queue[child2_index] = parent_value;
node_index[parent_value] = child2_index;
node_index[child2_value] = parent_index;
parent_index = child2_index;
}
else
{
break;
}
}
}
else if (child1_index < queue_size)
{
int parent_value = dijkstra_queue[parent_index];
int child1_value = dijkstra_queue[child1_index];

if (UVa423_less(distances, reachable, child1_value, parent_value))
{
dijkstra_queue[parent_index] = child1_value;
dijkstra_queue[child1_index] = parent_value;
node_index[parent_value] = child1_index;
node_index[child1_value] = parent_index;
parent_index = child1_index;
}
else
{
break;
}
}
else
{
break;
}
}
}

int UVa423_delete_min(vector<int>& dijkstra_queue, vector<int>& distances, vector<bool>& reachable, vector<int>& node_index, int& queue_size)
{
int u = dijkstra_queue[0];
node_index[u] = -1;
if (queue_size > 1)
{
dijkstra_queue[0] = dijkstra_queue[queue_size - 1];
dijkstra_queue[queue_size - 1] = -1;
node_index[dijkstra_queue[0]] = 0;
queue_size--;
UVa423_bubble_down(dijkstra_queue, distances, reachable, node_index, queue_size, 0);
}
else
{
dijkstra_queue[queue_size - 1] = -1;
queue_size--;
}
return u;
}

void UVa423_change_key(vector<int>& dijkstra_queue, vector<int>& distances, vector<bool>& reachable, vector<int>& node_index, int& queue_size, int changed_node)
{
int child_index = node_index[changed_node];
while (child_index != 0)
{
int parent_index = (child_index + 1) / 2 - 1;

int child_value = dijkstra_queue[child_index];
int parent_value = dijkstra_queue[parent_index];

if (UVa423_less(distances, reachable, child_value, parent_value))
{
dijkstra_queue[child_index] = parent_value;
dijkstra_queue[parent_index] = child_value;
node_index[parent_value] = child_index;
node_index[child_value] = parent_index;
child_index = parent_index;
}
else
{
break;
}
}
}

void UVa423_dijkstra(int src, vector<vector<pair<int, int> > >& adjacency_list, vector<int>& distances)
{
vector<int> dijkstra_queue; // containing the node numbers
vector<bool> reachable;     // false if the node is unreachable
vector<int> node_index;     // the priority queue position of the node in the queue
int queue_size;
dijkstra_queue.resize(num_nodes);
distances.resize(num_nodes);
reachable.resize(num_nodes);
node_index.resize(num_nodes);
queue_size = num_nodes;

// Step 1: Initialize the nodes and get them into the queue
int j = 1;
for (int i = 0; i < num_nodes; i++)
{
if (i == src)
{
distances[i] = 0;
reachable[i] = true;
dijkstra_queue[0] = i;
node_index[i] = 0;
}
else
{
distances[i] = -1;
reachable[i] = false;
dijkstra_queue[j] = i;
node_index[i] = j;
j++;
}
}

// Step 2: Main Loop
while (queue_size > 0)
{
int explored = UVa423_delete_min(dijkstra_queue, distances, reachable, node_index, queue_size);

if (reachable[explored])
{
for (unsigned int ni = 0; ni < adjacency_list[explored].size(); ni++)
{
int neighbor = neighbor_edge.first;
int new_neighbor_distance = distances[explored] + neighbor_edge.second;
if (!reachable[neighbor] || new_neighbor_distance < distances[neighbor])
{
distances[neighbor] = new_neighbor_distance;
reachable[neighbor] = true;
UVa423_change_key(dijkstra_queue, distances, reachable, node_index, queue_size, neighbor);
}
}
}
else
{
break;
}
}
}

### UVa Problem 186 - Trip Routing

Problem:

Solution:

We could have solve the problem by running the single source shortest path algorithm on all queries, but it could be much faster if we just run all pair shortest path once and answer the queries right away.

For all pair shortest paths, we used Floyd Warshall's algorithm for its simplicity.

The problem is quite complicated and tricky, be careful with a few things:

1. All highways are assumed to be bidirectional.
2. The input contain multiple edges.

Lots of coding work is devoted to the parsing of the inputs, mapping of names to numbers and so on. I had a bug with edge lookup because these complicated work are not done properly.

Code:

#include "stdafx.h"

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

#include "UVa186.h"

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

using namespace std;

void UVa186_split(string line, string* parts);
int UVa186_assign_city_number(map<string, int>& city_numbers, map<int, string>& city_namings, string city_name);

int UVa186()
{
map<string, int> city_numbers;
map<int, string> city_namings;
map<pair<int, int>, string> edge_namings;
vector<pair<pair<int, int>, int> > edges;
vector<pair<int, int> > queries;

string line;
getline(cin, line);
do
{
string parts[4];
UVa186_split(line, parts);

string src = parts[0];
string dst = parts[1];
string route = parts[2];
int cost = stoi(parts[3]);

int src_id = UVa186_assign_city_number(city_numbers, city_namings, src);
int dst_id = UVa186_assign_city_number(city_numbers, city_namings, dst);

if (dst_id < src_id)
{
int temp = src_id;
src_id = dst_id;
dst_id = temp;
}

pair<int, int> edge(src_id, dst_id);
edge_namings.insert(pair<pair<int, int>, string>(edge, route));
edges.push_back(pair<pair<int, int>, int>(edge, cost));

getline(cin, line);
}
while (line != "");

getline(cin, line);
while (true)
{
string parts[2];
UVa186_split(line, parts);
queries.push_back(pair<int, int>(city_numbers[parts[0]], city_numbers[parts[1]]));

if (cin.eof())
{
break;
}

getline(cin, line);

if (line == "")
{
break;
}
}

// Step 2: Produce the data structures for Floyd Warshall
int number_of_nodes = city_numbers.size();

vector<vector<int> > distances;
vector<vector<bool> > reachable;
vector<vector<int> > path;
distances.resize(number_of_nodes);
reachable.resize(number_of_nodes);
path.resize(number_of_nodes);
for (int src = 0; src < number_of_nodes; src++)
{
distances[src].resize(number_of_nodes);
reachable[src].resize(number_of_nodes);
path[src].resize(number_of_nodes);

for (int dst = 0; dst < number_of_nodes; dst++)
{
distances[src][dst] = -1;
reachable[src][dst] = false;
path[src][dst] = -1;
}
}

for (unsigned int e = 0; e < edges.size(); e++)
{
pair<pair<int, int>, int> edge = edges[e];
int src = edge.first.first;
int dst = edge.first.second;
int cost = edge.second;

// The input has multiple edges!
{
distances[src][dst] = cost;
reachable[src][dst] = true;
path[src][dst] = dst;

distances[dst][src] = cost;
reachable[dst][src] = true;
path[dst][src] = src;
}
}

for (int k = 0; k < number_of_nodes; k++)
{
for (int src = 0; src < number_of_nodes; src++)
{
for (int dst = 0; dst < number_of_nodes; dst++)
{
if (reachable[src][k] && reachable[k][dst]) // relaxation is possible if the proposal is valid
{
int current_distance = distances[src][dst];
int propose_distance = distances[src][k] + distances[k][dst];
if (!reachable[src][dst] || propose_distance < current_distance)
{
distances[src][dst] = propose_distance;
reachable[src][dst] = true;
path[src][dst] = path[src][k];
}
}
}
}
}

for (unsigned int q = 0; q < queries.size(); q++)
{
pair<int, int> query = queries[q];
int src = query.first;
int dst = query.second;

cout << endl;
cout << endl;

cout << "From                 To                   Route      Miles" << endl;
cout << "-------------------- -------------------- ---------- -----" << endl;

int cur = src;
while (true)
{
int path_src_id = cur;
int path_dst_id = path[cur][dst];
string path_src_name = city_namings[path_src_id];
string path_dst_name = city_namings[path_dst_id];

int edge_src_id = min(path_src_id, path_dst_id);
int edge_dst_id = max(path_src_id, path_dst_id);

string route = edge_namings[pair<int, int>(edge_src_id, edge_dst_id)];
while (path_src_name.length() < 20)
{
path_src_name += ' ';
}
while (path_dst_name.length() < 20)
{
path_dst_name += ' ';
}
while (route.length() < 10)
{
route += ' ';
}

cout << path_src_name << " " << path_dst_name << " " << route << " ";
cout << right << setw(5) << adjacency_matrix[path_src_id][path_dst_id] << endl;

cur = path_dst_id;
if (cur == dst)
{
break;
}
}
cout << "                                                     -----" << endl;
cout << "                                          Total      ";
cout << right << setw(5) << distances[src][dst] << endl;
}

return 0;
}

void UVa186_split(string line, string* parts)
{
string* current_part = parts;
for (unsigned int i = 0; i < line.length(); i++)
{
if (line[i] != ',')
{
(*current_part) += line[i];
}
else
{
current_part++;
}
}
}

int UVa186_assign_city_number(map<string, int>& city_numbers, map<int, string>& city_namings, string city_name)
{
int city_number;
map<string, int>::iterator probe = city_numbers.find(city_name);
if (probe == city_numbers.end())
{
city_number = city_numbers.size();
city_numbers.insert(pair<string, int>(city_name, city_number));
city_namings.insert(pair<int, string>(city_number, city_name));
}
else
{
city_number = probe->second;
}

return city_number;
}