## Saturday, November 1, 2014

### UVa Problem 10763 - Foreign Exchange

Problem:

Solution:

Despite the data size, the problem seems trivial. If someone want to go to 1 from 2 and you have already seen someone want to go from 2 to 1, match them, that's it.

The key to this problem is the fast look-up to match expectation. Fortunately C++ STL map do just that. Beyond fast lookup, it allows removing element at iterator to avoid lookup again, and updating value of the item pointed by the look-up, which is exactly what I needed.

Code:

#include "stdafx.h"

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

#include "UVa10763.h"

#include <iostream>
#include <map>

using namespace std;

int UVa10763()
{
while (true)
{
int num_candidates;
cin >> num_candidates;
if (num_candidates == 0)
{
break;
}
map<pair<int, int>, int> expectations;
for (int c = 0; c < num_candidates; c++)
{
int src, dst;
cin >> src;
cin >> dst;
map<pair<int, int>, int>::iterator probe1 = expectations.find(pair<int, int>(src, dst));
if (probe1 == expectations.end())
{
map<pair<int, int>, int>::iterator probe2 = expectations.find(pair<int, int>(dst, src));
if (probe2 == expectations.end())
{
expectations.insert(pair<pair<int, int>, int>(pair<int, int>(dst, src), 1));
}
else
{
probe2->second++;
}
}
else
{
if (--probe1->second == 0)
{
expectations.erase(probe1);
}
}
}

cout << (expectations.size() == 0 ? "YES" : "NO") << endl;
}
return 0;
}