UVA - 10763 - Foreign Exchange

This article will explain my thought process to solve a problem called Foreign Exchange (PDF) from UVA Online Judge. Read the original problem statement before reading this article.

Keywords: Graph, Linear Search

Objective

Given:

Number of candidates.
List of student exchanges between 2 locations.

We want to:

Determine whether the student exchange program is possible.

Glossary

Graph — A structure consisting of a set of objects where some pairs of the objects are related.
Linear Search — A searching algorithm that checks each element sequentially until the key is found or the collection is fully traversed.

Observation

We could model the relationship of the student exchanges as a graph, where the locations are the vertices and the candidate exchanges are the edges. The edges have direction, as the student wants to go from one location to another. The edges have weight, which indicates the number of students that go from one location to another.

To determine the validity of the program, we must ensure that the number of the students that goes from location A to B matches the number of the students that goes from the other way around, from location B to A. This can be validated using the weight of the graph.

Algorithm

The graph contains vertices, edges, direction, and weight. Those graph data can be stored in a nested hash map for simplicity and efficiency.

For the graph validation, we could do a linear scan over every possible pair of vertices. In each iteration, check whether the weight of the pair matches the weight of the reversed pair.

The time complexity of this solution is O({total candidates}) or O(10^5).

Implementation

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

/**
 * 10763 - Foreign Exchange
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1704
 */
public class Main {
    public static void main(final String... args) {
        final Scanner in = new Scanner(new BufferedInputStream(System.in));
        final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        final Process process = new Process();

        while (in.hasNextInt()) {
            final Input input = new Input();
            input.totalCandidates = in.nextInt();
            input.exchanges = new int[input.totalCandidates][2];
            for (int i = 0; i < input.totalCandidates; i++) {
                input.exchanges[i][0] = in.nextInt();
                input.exchanges[i][1] = in.nextInt();
            }
            if (input.isEOF()) break;

            final Output output = process.process(input);
            if (output.isValidExchanges) {
                out.println("YES");
            } else {
                out.println("NO");
            }
        }

        in.close();
        out.flush();
        out.close();
    }
}

class Input {
    public int totalCandidates;
    public int[][] exchanges;

    public boolean isEOF() {
        return totalCandidates == 0;
    }
}

class Output {
    public boolean isValidExchanges;
}

class Process {
    private static final Output VALID_OUTPUT = buildOutput(true);
    private static final Output INVALID_OUTPUT = buildOutput(false);

    private static Output buildOutput(final boolean isValidExchanges) {
        final Output output = new Output();
        output.isValidExchanges = isValidExchanges;
        return output;
    }

    public Output process(final Input input) {
        final Counts totalCandidatesPerExchanges = new Counts();
        for (final int[] exchange : input.exchanges) {
            final int original = exchange[0], target = exchange[1];
            totalCandidatesPerExchanges.increment(original, target);
        }

        for (final int original : totalCandidatesPerExchanges.get()) {
            for (final int target : totalCandidatesPerExchanges.get(original)) {
                final int totalCandidates1 = totalCandidatesPerExchanges.get(original, target);
                final int totalCandidates2 = totalCandidatesPerExchanges.get(target, original);

                final boolean isValid = totalCandidates1 == totalCandidates2;
                if (!isValid) return INVALID_OUTPUT;
            }
        }

        return VALID_OUTPUT;
    }
}

class Counts {
    public Map<Integer, Map<Integer, Integer>> counts = new HashMap<>();

    public void increment(final int key1, final int key2) {
        counts
                .computeIfAbsent(key1, k -> new HashMap<>())
                .compute(key2, (k, v) -> 1 + (v == null ? 0 : v));
    }

    public Set<Integer> get() {
        return counts.keySet();
    }

    public Set<Integer> get(final int key1) {
        return counts
                .getOrDefault(key1, Collections.emptyMap())
                .keySet();
    }

    public int get(final int key1, final int key2) {
        return counts
                .getOrDefault(key1, Collections.emptyMap())
                .getOrDefault(key2, 0);
    }
}