UVA - 13054 - Hippo Circus

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

Keywords: Greedy, Sorting

Objective

Given:

Number of hippopotamuses.
Height of the door.
Perform time when walking alone.
Perform time when carrying other hippopotamus.
List of the height of hippopotamuses.
Rules for carry.
1. Can only carry 1 other hippopotamus.
2. The combined total heights must be less than the door height.

We want to:

Find the minimum total times for every hippopotamus to perform.

Glossary

Greedy — A strategy to choose the locally optimal option at each step, in assumption that it will eventually lead to a globally optimal solution.
Sorting — Rearrangement of a given array or list of elements according to a comparison operator on the elements.

Observation

We have 2 options to perform, by going alone or in pair. We could calculate the amount of time that can be saved by calculating the difference between 2 hippos going alone (2 * alone perform time) against 2 hippos going in pair (carry perform time). If we could save time by going in pair, then we should go in pair as much as possible, otherwise just go alone.

Next, we could use greedy strategy for the pair assignment. The total heights of the pair must be less than the door height, and this means that to maximize the number of pair, we want to assign the shortest hippo with the tallest possible hippo.

In order to identify the pairs efficiently, we could start from sorting the hippos by height. This will immediately let us know the shortest and tallest hippos. If both of them couldn’t fit on the door, let the tallest hippos go alone and pair the shortest hippo with the next tallest hippo. If both of them could fit the door, let them go in pair, and keep repeating the process until everyone is gone.

Algorithm

We could use Java built-in sorting function to sort the hippos by the height efficiently. Next, since we want to pair the shortest and tallest hippos, we could use a deque data structure to store the hippos. The first element of the deque represent the shortest hippo, while the last element of the deque represent the tallest hippo.

The time complexity of this solution is O({total hippos} * log2({total hippos}) or O(10^6).

Implementation

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

/**
 * 13054 - Hippo Circus
 * Time limit: 1.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4952
 */
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 totalCases = in.nextInt();
        for (int i = 0; i < totalCases; i++) {
            final Input input = new Input();
            input.caseId = i + 1;
            input.totalHippos = in.nextInt();
            input.doorHeight = in.nextInt();
            input.aloneTime = in.nextInt();
            input.carryTime = in.nextInt();
            input.hippoHeights = new int[input.totalHippos];
            for (int j = 0; j < input.totalHippos; j++) {
                input.hippoHeights[j] = in.nextInt();
            }

            final Output output = process.process(input);
            out.format("Case %d: %d\n", output.caseId, output.minimumTime);
        }

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

class Input {
    public int caseId;
    public int totalHippos;
    public int doorHeight;
    public int aloneTime;
    public int carryTime;
    public int[] hippoHeights;
}

class Output {
    public int caseId;
    public int minimumTime;
}

class Process {
    public Output process(final Input input) {
        final Output output = new Output();
        output.caseId = input.caseId;

        final boolean isFasterAlone = (input.aloneTime * 2) <= input.carryTime;
        if (isFasterAlone) {
            output.minimumTime = input.aloneTime * input.totalHippos;
            return output;
        }

        final int[] hippoHeights = input.hippoHeights;
        Arrays.sort(hippoHeights);
        final Deque<Integer> deque = new LinkedList<>();
        for (final int height : hippoHeights) deque.addLast(height);

        int totalTimes = 0;
        while (!deque.isEmpty()) {
            final int shortest = deque.removeFirst();
            if (deque.isEmpty()) {
                totalTimes += input.aloneTime;
            } else {
                final int tallest = deque.removeLast();
                final boolean canFit = (shortest + tallest) < input.doorHeight;
                if (canFit) {
                    totalTimes += input.carryTime;
                } else {
                    totalTimes += input.aloneTime;
                    deque.addFirst(shortest);
                }
            }
        }

        output.minimumTime = totalTimes;
        return output;
    }
}