Addition

It is a quite senior problem. Given several facts of addition formulars such as a+b=10, b+c=4 and c+d=5 and so on, you are asked to write a program that can give answer to any statements that can derive from the conditions given without ambiguity. For example, from the instance above, we can also derive one more statement a+d=11 apart form the three equations given. Given these equations and some querys, we should out all statements we can get without ambiguity.

As for the small data set we can just use DFS as we find that every equation and query only have plus operations and from given equations we build a undirected graph. And we can get the sum of two numbers of there is a path between the two numbers that contains odd number of edges. But this is not fast enough for large set.

To solve the large scale problem, we can use Union-Find. At first we can see if we encode the first variable and the second variable with different encoding even if they are the same, we can use union find to check if the statement a combination of two given names is derivable as the union find graph will be built as a bipartite graph so any path from a node in group one to a node in group two must have odd number of edges. Starts from this we can add extra fields to record the relationship and sum from a node to its parent.

Let's say we have two array types and sums that is corresponding to each node. We define when types[i] is 1 sums[i] keeps the sum of i and its parent ids[i], aka, i+ids[i]=sums[i]. Otherwise we keep i-ids[i] in sums[i]. When perform find operation, we point the node to its root directly and at this time we must recursively update types[i] and sums[i] carefully. Also, when we perform union operation of x and y, we have to calculate their root parents p and q's relationship and sum correctly too. The code here is need deep consideration and is a little hard to implement correctly, but once finished we can check if the statement is valid and give the result easily. For example, if x and y is connected, we know that there is a valid statement describing x+y, also as we are building and querying a bipartite graph so the path from x to y must contains odd number of edges. As the find operation pointed x and y to its parent, we must have either types[x] or types[y] is 1 and the other is 0. So for their common root parent r, we will get either x+r and y-r or x-r and y+r. To get x+y we can just add sum[x] and sum[y].

Also noted that their sometimes given some equations like a+a=10 and b+b=12, by these two fomular we can actually get the value a and b respectively and thus got results for equations like a+b. So don't remember to hander these cases.

import java.io.*;
import java.util.*;

class UnionFind {
    private int[] ids;
    private int[] sizes;
    private int[] sums;
    private int[] types;

    public UnionFind(int N) { 
        ids = new int[N];
        sizes = new int[N];
        sums = new int[N];
        types = new int[N];
        for (int i = 0; i < N; i++) {
            ids[i] = i;
            sizes[i] = 1;
        }
    }

    public int find(int p) {
        if (ids[p] == p) return p;
        int root = find(ids[p]);
        if (types[p] == 0) sums[p] += sums[ids[p]];
        else sums[p] -= sums[ids[p]];
        types[p] ^= types[ids[p]];
        ids[p] = root;
        return root;
    }

    public void union(int x, int y, int sum) {
        int p = find(x);
        int q = find(y);

        if (p == q) return;

        int pqsum = sums[x] + sums[y] - sum;
        int type = types[x] ^ types[y] ^ 1;

        if (sizes[p] < sizes[q]) {
            ids[p] = q;
            sums[p] = (types[x] == 0 ? -pqsum : pqsum);
            types[p] = type;
            sizes[q] += sizes[p];
        } else {
            ids[q] = p;
            sums[q] = (types[y] == 0 ? -pqsum : pqsum);
            types[q] = type;
            sizes[p] += sizes[q];
        }
    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    public int pathsum(int p, int q) {
        return sums[p] + sums[q];
    }
}

public class Addition {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int t = 0; t < T; t++) {
            int N = in.nextInt();
            HashMap<String, Integer> map = new HashMap<String, Integer>();
            String s;
            String[] str;
            UnionFind uf = new UnionFind(N * 4);
            for (int i = 0; i < N; i++) {
                s = in.next();
                str = s.split("\\+|=");
                String a = str[0];
                String b = str[1];
                int sum = Integer.parseInt(str[2]);
                if (!map.containsKey(a)) map.put(a, map.size());
                if (!map.containsKey(b)) map.put(b, map.size());
                int ia = map.get(a), ib = map.get(b);
                uf.union(ia, ib + 2 * N, sum);
                uf.union(ib, ia + 2 * N, sum);
            }
            int Q = in.nextInt();
            System.out.printf("Case #%d:\n", t + 1);
            for (int i = 0; i < Q; i++) {
                s = in.next();
                str = s.split("\\+");
                String a = str[0];
                String b = str[1];
                if (!map.containsKey(a) || !map.containsKey(b)) continue;
                int ia = map.get(a), ib = map.get(b);
                if (uf.connected(ia, ib + 2 * N)) {
                    System.out.printf("%s=%d\n", s, uf.pathsum(ia, ib + 2 * N));
                } else if (uf.connected(ia, ia + 2 * N) && uf.connected(ib, ib + 2 * N)) {
                    System.out.printf("%s=%d\n", s, (uf.pathsum(ia, ia + 2 * N) + uf.pathsum(ib, ib + 2 * N)) / 2);
                }
            }
        }
    }
}