UVA - 11490 - Just Another Problem

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

Keywords: Algebra, Searching

Objective

Given:

Number of soldiers.
Rules for the arrangement of the soldiers.
1. The shape of the formation is a rectangle.
2. The formation has 2 layers: inner and outer.
3. The missing soldiers must be placed on the inner layer.
4. The existing soldiers must be placed on the outer layer.
5. The shape of the inner layer is a two equal sized square.

We want to:

Find list of every possible total missing soldiers.

Glossary

Algebra — A branch of mathematics in which arithmetical operations and formal manipulations are applied to abstract symbols rather than specific numbers.
Searching — A process of locating a specific element or item within a collection of data.
Linear Search — A searching algorithm that checks each element sequentially until the key is found or the collection is fully traversed.

Observation

First, we need to find the algebraic equation to calculate the number of soldiers based on the dimension of the inner and outer layer. Let A be the dimension of the inner layer, and B be the thickness of the outer layer. We can say that the area of the formation is (3B + 2A) * (2B + A) or 6B^2 + 2A^2 + 7AB.

Next, we can deduct the formation area with the inner layer area to find the number of the soldiers. Since the area of the inner layer is 2A^2, we can say that the number of soldiers is 6B^2 + 2A^2 + 7AB - 2A^2 or 6B^2 + 7AB. Let C be the number of soldiers, and this give us the final equation of C = 6B² + 7AB.

After we have discovered the equation, we need to find the values of A and B that are able to produce C. We can reduce the search space by taking advantage of the total soldiers equation. First, we know that both A and B must be strictly positive number, so this give us A ≥ 1 and B ≥ 1. Second, from C = 6B^2 + 7AB, if we ignore the least influential variable, we know that B ≤ √C. Third, if B is known, then A = (C - 6B^2) / 7B.

Based on the above deduction, we just need to try every possible B values within 1 ≤ B ≤ √C range, which will let us know the estimated A value as well. Since the value of B and the estimated value of A is known, we can calculate the C as well and validate it against the actual C value.

Algorithm

For the searching, we can use linear search algorithm to go over 1 ≤ B ≤ √C search space. This will give us the value of B, the estimated value of A, and the value of C for the current configuration. Be careful when calculating the number of the missing soldiers, as A could potentially have a maximum value of 10^12 and it means that the number of missing soldiers could potentially reach 10^24 and causes overflow error. Use modulo 100000007 as much as possible to avoid those error.

The time complexity of this solution is O(sqrt({total soldiers})) or O(10^6).

Implementation

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

/**
 * 11490 - Just Another Problem
 * Time limit: 4.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2485
 */
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();

        for (int caseId = 1; ; caseId++) {
            final Input input = new Input();
            input.caseId = caseId;
            input.totalSoldiers = in.nextLong();
            if (input.isEOF()) break;

            final Output output = process.process(input);
            if (output.isPossible) {
                for (final long totalMissingSoldiers : output.listTotalMissingSoldiers) {
                    out.format("Possible Missing Soldiers = %d\n", totalMissingSoldiers);
                }
            } else {
                out.println("No Solution Possible");
            }
            out.println();
        }

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

class Input {
    public int caseId;
    public long totalSoldiers;

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

class Output {
    public int caseId;
    public boolean isPossible;
    public long[] listTotalMissingSoldiers;
}

class Process {
    private static final long MODULO = 100000007;

    public Output process(final Input input) {
        final LinkedList<Long> innerLengths = new LinkedList<>();
        final long minOuterLength = 1;
        final long maxOuterLength = Math.round(Math.ceil(Math.sqrt(input.totalSoldiers)));

        for (long outerLength = minOuterLength; outerLength <= maxOuterLength; outerLength++) {
            final long innerLength = getInnerLength(input.totalSoldiers, outerLength);
            final long totalSoldiers = getTotalSoldiers(innerLength, outerLength);

            final boolean valid = innerLength > 0 && totalSoldiers == input.totalSoldiers;
            if (valid) innerLengths.addLast(innerLength);
        }

        final long[] listTotalMissingSoldiers = innerLengths.stream()
            .mapToLong(Long::longValue)
            .map(innerLength -> getTotalMissingSoldiers(innerLength, MODULO))
            .toArray();

        final Output output = new Output();
        output.caseId = input.caseId;
        output.isPossible = !innerLengths.isEmpty();
        output.listTotalMissingSoldiers = listTotalMissingSoldiers;
        return output;
    }

    private long getTotalSoldiers(final long innerLength, final long outerLength) {
        return (7 * innerLength * outerLength) + (6 * outerLength * outerLength);
    }

    private long getInnerLength(final long totalSoldiers, final long outerLength) {
        return (totalSoldiers - (6 * outerLength * outerLength)) / (7 * outerLength);
    }

    private long getTotalMissingSoldiers(final long innerLength, final long mod) {
        final long length = innerLength % mod;
        final long length2 = (length * length) % mod;
        return (2 * length2) % mod;
    }
}