Saturday, November 1, 2014

UVa Problem 10763 - Foreign Exchange

Problem:

Please find the problem here.

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

No comments :

Post a Comment