tc - 516 div2 - 1000 (java)

NetworkXMessageRecovery.java

/*(c) gorlum0 [at] gmail.com*/
import java.io.*;
import java.util.*;
import java.math.*;

public class NetworkXMessageRecovery
{
    public String recover(String[] messages) {
        StringBuilder res = new StringBuilder();

        HashMap<Character, HashSet<Character>> req = new HashMap();
        for (String msg : messages)
            for (char c : msg.toCharArray())
                if (req.get(c) == null) req.put(c, new HashSet());
        for (String msg : messages)
            for (int i = 0; i < msg.length(); i++) {
                char a = msg.charAt(i);
                for (int j = i-1; j >= 0; j--) {
                    char b = msg.charAt(j);
                    req.get(a).add(b);
                }
            }

        while (!req.isEmpty()) {
            Vector<Character> cands = new Vector();
            for (char k : req.keySet())
                if (req.get(k).isEmpty())
                    cands.add(k);
            char best = Collections.min(cands);
            res.append(best);
            for (char k : req.keySet())
                req.get(k).remove(best);
            req.remove(best);
        }

        return res.toString();
    }

    void main() throws IOException {
        int n;
        while ((n = nextInt()) != EOF) {
            Vector<String> messages = new Vector();
            for (int i = 0; i < n; i++)
                messages.add(nextToken());
            out.println(recover(messages.toArray(new String[0])));
        }
    }

    public static void main(String[] args) {
        new NetworkXMessageRecovery().run();
    }

    // ======================================================================

    int inf = Integer.MAX_VALUE;
    final int EOF = -1;

    boolean not(boolean p) { return !p; }

    int sqr(int x) { return x*x; }
    long sqr(long x) { return x*x; }
    double sqr(double x) { return x*x; }

    BufferedReader fin;
    StringTokenizer st;
    PrintWriter out;

    public void run() {
        try {
            fin = new BufferedReader(new InputStreamReader(System.in));
            st = null;
            out = new PrintWriter(System.out);
            main();
            fin.close();
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    String nextToken() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            String line = fin.readLine();
            if (line == null) return "-1";
            else st = new StringTokenizer(line);
        }
        return st.nextToken();
    }
}