UVA - 12844 - Outwitting the Weighing Machine

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

Keywords: Combination, Algebra

Problem Summary

Given:

List of weights from every possible couples.

We want to:

Find the weight of each person.

Glossary

Combination — A selection of items from a set that has distinct members, such that the order of selection does not matter.
Algebra — A branch of mathematics in which arithmetical operations and formal manipulations are applied to abstract symbols rather than specific numbers.

Observation

There is exactly 5 persons on this problem, lets say A, B, C, D and E. The weights given by the input comes from combination of 2 persons weights (A+B, A+C, A+D, A+E, B+C, B+D, B+E, C+D, C+E, D+E) ordered randomly.

We could extract more information from the input using Algebra Approach. If we sum the weights, the result is equals to 4 * (A + B + C + D + E). We can retrieve the total weights of every person using that equation. Furthermore, if the weights of every person and weights of 2 person is known, it is also possible to retrieve the weight of every person using these equations:

A’s weight = (A + B + C + D + E) - (B + C) - (D + E).
B’s weight = (A + B) - (A)
C’s weight = (A + C) - (A)
D’s weight = (A + D) - (A)
E’s weight = (A + E) - (A)

Since the order of the 2 person weights is random, we could explore every possible combination of the weights by taking 4 weights from the 10 available weights as the (A + B), (A + C), (A + D) and (A + E). During each iteration, we will be able to determine the personal weight of A, B, C, D, and E. To validate the combination, we can compare the 2 person weights given by the input against the current combination 2 person weights. Keep in mind that the weights must be sorted.

Algorithm

To implement the combination, since we take exactly 4 weights out of exactly 10 weights, this can be implemented using a 4 levels nested loops. Each level will represent (A+B), (A+C), (A+D), and (A+E). At each iteration, we will compute the personal weights and validate it against the input weights.

For the validation, we take exactly 2 weights out of exactly 5 personal weights. Then, the totals are collected on a list, sorted, and compared against the sorted version of the input weights. If the contents are equals, then the combination is valid.

The time complexity of this solution is O({total weights}^4 * {total peoples}^2) or O(10^5).

Implementation

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

/**
 * 12844 - Outwitting the Weighing Machine
 * Time limit: 1.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4709
 */
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();

        final int totalTestCases = in.nextInt();
        for (int i = 0; i < totalTestCases; i++) {
            final Input input = new Input();
            input.caseId = i + 1;
            input.coupleWeights = new int[10];
            for (int j = 0; j < 10; j++) {
                input.coupleWeights[j] = in.nextInt();
            }

            final Output output = process.process(input);
            out.format(
                "Case %d: %d %d %d %d %d\n",
                output.caseId, output.weights[0], output.weights[1], output.weights[2], output.weights[3], output.weights[4]
            );
        }

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

class Input {
    public int caseId;
    public int[] coupleWeights;
}

class Output {
    public int caseId;
    public int[] weights;
}

class Process {
    public Output process(final Input input) {
        final int[] couples = input.coupleWeights;
        Arrays.sort(couples);

        final int abcde = Arrays.stream(couples).sum() / 4;

        for (int i = 0; i < couples.length; i++) {
            final int ab = couples[i];

            for (int j = i + 1; j < couples.length; j++) {
                final int bc = couples[j];

                for (int k = j + 1; k < couples.length; k++) {
                    final int cd = couples[k];

                    for (int l = k + 1; l < couples.length; l++) {
                        final int de = couples[l];

                        final int a = abcde - bc - de;
                        final int b = ab - a;
                        final int c = bc - b;
                        final int d = cd - c;
                        final int e = de - d;

                        final int[] personals = new int[]{a, b, c, d, e};
                        Arrays.sort(personals);

                        final boolean isValid = isValid(couples, personals);
                        if (isValid) {
                            final Output output = new Output();
                            output.caseId = input.caseId;
                            output.weights = personals;
                            return output;
                        }
                    }
                }
            }
        }

        throw new NullPointerException();
    }

    private boolean isValid(final int[] couples, final int[] personals) {
        final int[] couples2 = new int[10];
        for (int i = 0, k = 0; i < 5; i++) {
            for (int j = i + 1; j < 5; j++, k++) {
                couples2[k] = personals[i] + personals[j];
            }
        }
        Arrays.sort(couples2);

        return Arrays.equals(couples, couples2);
    }
}