## Monday, October 6, 2014

### UVa Problem 10158 - War

Problem:

Solution:

The key to solve this problem is the data structure we will use to maintain our current knowledge. We can basically partition the people into sets such that we know for sure they are friends. And then pair up these groups into enemy pairs. So it looks like this

(1, 2) are friends
(3, 4) are friends
(5) are friends
(1, 2) and (3, 4) are enemies.

With the representation, the operation came by easily. For setFriend/setEnemies, we union the friends and union the enemies and form a new pair.  Of course, it might be a contradiction or a no-op.

For example, if we say setFriend(2, 5), the state become
(1, 2, 5) are friends
(3, 4) are friends
(1, 2, 5) and (3, 4) are enemies.

If we say setEnemies(3, 4) then we hit a contradiction because they were friends.

Checking areFriends and areEnemies are even simpler, just check if they are in the same set/different sets within a pair.

Now - it comes to implementation - both groups can simply be simulated by disjoint set union find -so we will use it to achieve near linear performance!

Code:

#include "stdafx.h"

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

#include "UVa10158.h"

#include <iostream>
#include <string>
#include <set>
#include <vector>

using namespace std;

struct partition
{
int left_root;
int right_root;
};

int find_group_representative(vector<pair<int, partition*> >& related_groups, int person)
{
if (related_groups[person].first < 0)
{
return person;
}
else
{
return (related_groups[person].first = find_group_representative(related_groups, related_groups[person].first));
}
}

int find_friend_representative(vector<int>& known_friends, int person)
{
if (known_friends[person] < 0)
{
return person;
}
else
{
return (known_friends[person] = find_friend_representative(known_friends, known_friends[person]));
}
}

partition* merge_same_side(partition* first, partition* second, vector<int>& known_friends)
{
partition* merged = new partition();

if (first->left_root == -1)
{
merged->left_root = second->left_root;
}
else if (second->left_root == -1)
{
merged->left_root = first->left_root;
}
else
{
// Union-by-size for left
if (known_friends[first->left_root] < known_friends[second->left_root])
{
known_friends[first->left_root] = known_friends[first->left_root] + known_friends[second->left_root];
known_friends[second->left_root] = first->left_root;
merged->left_root = first->left_root;
}
else
{
known_friends[second->left_root] = known_friends[first->left_root] + known_friends[second->left_root];
known_friends[first->left_root] = second->left_root;
merged->left_root = second->left_root;
}
}

if (first->right_root == -1)
{
merged->right_root = second->right_root;
}
else if (second->right_root == -1)
{
merged->right_root = first->right_root;
}
else
{
// Union-by-size for right
if (known_friends[first->right_root] < known_friends[second->right_root])
{
known_friends[first->right_root] = known_friends[first->right_root] + known_friends[second->right_root];
known_friends[second->right_root] = first->right_root;
merged->right_root = first->right_root;
}
else
{
known_friends[second->right_root] = known_friends[first->right_root] + known_friends[second->right_root];
known_friends[first->right_root] = second->right_root;
merged->right_root = second->right_root;
}
}

return merged;
}

partition* merge_diff_side(partition* first, partition* second, vector<int>& known_friends)
{
partition* merged = new partition();

if (first->left_root == -1)
{
merged->left_root = second->right_root;
}
else if (second->right_root == -1)
{
merged->left_root = first->left_root;
}
else
{
// Union-by-size for left
if (known_friends[first->left_root] < known_friends[second->right_root])
{
known_friends[first->left_root] = known_friends[first->left_root] + known_friends[second->right_root];
known_friends[second->right_root] = first->left_root;
merged->left_root = first->left_root;
}
else
{
known_friends[second->right_root] = known_friends[first->left_root] + known_friends[second->right_root];
known_friends[first->left_root] = second->right_root;
merged->left_root = second->right_root;
}
}

if (first->right_root == -1)
{
merged->right_root = second->left_root;
}
else if (second->left_root == -1)
{
merged->right_root = first->right_root;
}
else
{
// Union-by-size for right
if (known_friends[first->right_root] < known_friends[second->left_root])
{
known_friends[first->right_root] = known_friends[first->right_root] + known_friends[second->left_root];
known_friends[second->left_root] = first->right_root;
merged->right_root = first->right_root;
}
else
{
known_friends[second->left_root] = known_friends[first->right_root] + known_friends[second->left_root];
known_friends[first->right_root] = second->left_root;
merged->right_root = second->left_root;
}
}

return merged;
}

int UVa10158()
{
int number_of_people;
cin >> number_of_people;
vector<pair<int, partition*> > related_groups;
vector<int> known_friends;
related_groups.resize(number_of_people);
known_friends.resize(number_of_people);
for (int i = 0; i < number_of_people; i++)
{
related_groups[i].first = -1;
related_groups[i].second = new partition();
related_groups[i].second->left_root = i;
related_groups[i].second->right_root = -1;
known_friends[i] = -1;
}
while (true)
{
int operation_code;
int person1;
int person2;
cin >> operation_code;
cin >> person1;
cin >> person2;
if (operation_code == 0)
{
break;
}
int root1 = find_group_representative(related_groups, person1);
int root2 = find_group_representative(related_groups, person2);
bool oneIsLeft = find_friend_representative(known_friends, person1) == related_groups[root1].second->left_root;
bool twoIsLeft = find_friend_representative(known_friends, person2) == related_groups[root2].second->left_root;

switch(operation_code)
{
case 1:
// setFriends
if (root1 == root2)
{
if (oneIsLeft == twoIsLeft)
{
// They are already on the same side - setFriend is a no-op here
}
else
{
// They are already on different sides - report an error
cout << -1 << endl;
}
}
else
{
partition* merged = NULL;
if (oneIsLeft == twoIsLeft)
{
// Now we know they are on the same side
merged = merge_same_side(related_groups[root1].second, related_groups[root2].second, known_friends);
}
else
{
// Now we know they are on the different sides
merged = merge_diff_side(related_groups[root1].second, related_groups[root2].second, known_friends);
}

// Union by size
if (related_groups[root1].first < related_groups[root2].first)
{
related_groups[root1].first = related_groups[root1].first + related_groups[root2].first;
related_groups[root2].first = root1;
delete related_groups[root1].second;
delete related_groups[root2].second;
related_groups[root1].second = merged;
related_groups[root2].second = NULL;
}
else
{
related_groups[root2].first = related_groups[root1].first + related_groups[root2].first;
related_groups[root1].first = root2;
delete related_groups[root1].second;
delete related_groups[root2].second;
related_groups[root1].second = NULL;
related_groups[root2].second = merged;
}
}
break;
case 2:
// setEnemies
if (root1 == root2)
{
if (oneIsLeft == twoIsLeft)
{
// They are already on the same side - report an error
cout << -1 << endl;
}
else
{
// They are already on different sides - setEnemies is a no-op here
}
}
else
{
partition* merged = NULL;
if (oneIsLeft == twoIsLeft)
{
// Now we know they are on different sides
merged = merge_diff_side(related_groups[root1].second, related_groups[root2].second, known_friends);
}
else
{
// Now we know they are on the same side
merged = merge_same_side(related_groups[root1].second, related_groups[root2].second, known_friends);
}

// Union by size
if (related_groups[root1].first < related_groups[root2].first)
{
related_groups[root1].first = related_groups[root1].first + related_groups[root2].first;
related_groups[root2].first = root1;
delete related_groups[root1].second;
delete related_groups[root2].second;
related_groups[root1].second = merged;
related_groups[root2].second = NULL;
}
else
{
related_groups[root2].first = related_groups[root1].first + related_groups[root2].first;
related_groups[root1].first = root2;
delete related_groups[root1].second;
delete related_groups[root2].second;
related_groups[root1].second = NULL;
related_groups[root2].second = merged;
}
}
break;
case 3:
// areFriends
if (root1 == root2)
{
if (oneIsLeft == twoIsLeft)
{
// They are surely friends
cout << 1 << endl;
}
else
{
// They are surely enemies
cout << 0 << endl;
}
}
else
{
// Not sure case
cout << 0 << endl;
}
break;
case 4:
// areEnemies
if (root1 == root2)
{
if (oneIsLeft == twoIsLeft)
{
// They are surely friends
cout << 0 << endl;
}
else
{
// They are surely enemies
cout << 1 << endl;
}
}
else
{
// Not sure case
cout << 0 << endl;
}
break;
default:
break;
}
}
return 0;
}