UVA - 13177 - Orchestral scores

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

Keywords: Greedy, Sorting

Objective

Given:

Number of scores.
Number of instruments.
List of the number of musicians for each instrument.

We want to:

Find the minimum number of musicians in the most crowded stand.

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

First, we need to be careful with the time limit of this problem. It has a strict time limit of 1 second, so we must use a custom fast I/O method to process the I/O.

To minimize the crowds, we want to distribute the scores equally across the instruments. We can use the ratio to get a roughly equal distribution. Let A be the total scores for the instrument, B be the total musicians for the instrument, C be the total scores, D be the total musicians, and the ratio should be A = C * B / D.

After we have distributed the scores equally based on the ratio, this will give us some remaining scores that couldn’t be assigned due to rounding. For the remaining scores, we want to use greedy approach to prioritize assigning the scores to the most crowded instrument. This can be achieved by creating a queue which elements is sorted by the total crowds. Let E be the total crowds, and the total crowds should be E = round_up(B / A). We keep repeating the process until there are no remaining scores.

After we have finished with the assignment of the remaining scores, the first element of the queue should be the instrument with the maximum total crowds.

Algorithm

The ratio-based distribution can be implemented iteratively. For each instrument, we can calculate the number of scores that is given to the instrument based on the ratio formula. In each iteration, we also keep track of the remaining number of instruments.

Next, the priority-based distribution can be implemented using priority queue. This data structure will let us dynamically add and remove an element while still maintaining the order of the queue, with the order based on the total crowds. We keep removing an instrument from the queue, assigning scores to the instrument, and adding the instrument back to the queue, until we have no remaining scores.

There is a quick trick to calculate a rounded up division of an integer, which is by using the (a + b - 1) / b formula.

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

Implementation

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 13177 - Orchestral scores
 * Time limit: 1.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=5088
 */
public class Main {
    public static void main(final String... args) throws IOException {
        final BufferedIO io = new BufferedIO(System.in, System.out, 1 << 16);
        final Process process = new Process();

        while (true) {
            final String[] line1 = io.readLine(" ");
            final String[] line2 = io.readLine(" ");
            final boolean isEOF = line1 == null;
            if (isEOF) break;

            final Input input = new Input();
            input.totalScores = Integer.parseInt(line1[0]);
            input.totalInstruments = Integer.parseInt(line1[1]);
            input.totalMusiciansPerInstrument = new int[input.totalInstruments];
            for (int i = 0; i < input.totalInstruments; i++) {
                input.totalMusiciansPerInstrument[i] = Integer.parseInt(line2[i]);
            }

            final Output output = process.process(input);
            io.write("%d\n", output.totalCrowds);
        }

        io.close();
    }
}

class Input {
    public int totalScores;
    public int totalInstruments;
    public int[] totalMusiciansPerInstrument;
}

class Output {
    public int totalCrowds;
}

class Process {
    public Output process(final Input input) {
        final int totalMusicians = sum(input.totalMusiciansPerInstrument);
        final int[] totalScoresPerInstrument = new int[input.totalInstruments];
        int remainingScores = input.totalScores;

        // assign scores based on ratio
        for (int instrument = 0; instrument < input.totalInstruments; instrument++) {
            final int thisTotalMusicians = totalScoresPerInstrument[instrument];
            final int thisTotalScores = Math.max(1, input.totalScores * thisTotalMusicians / totalMusicians);

            totalScoresPerInstrument[instrument] = thisTotalScores;
            remainingScores -= thisTotalScores;
        }

        // assign remaining scores based on crowd
        final Comparator<Integer> orderByCrowdDesc = Comparator
            .comparingInt(instrument -> -getTotalCrowds(
                input.totalMusiciansPerInstrument[instrument],
                totalScoresPerInstrument[instrument]
            ));
        final PriorityQueue<Integer> instrumentq = new PriorityQueue<>(orderByCrowdDesc);
        for (int instrument = 0; instrument < input.totalInstruments; instrument++) {
            instrumentq.add(instrument);
        }

        while (remainingScores > 0){
            final int instrument = instrumentq.remove();
            totalScoresPerInstrument[instrument]++;
            remainingScores--;
            instrumentq.add(instrument);
        }

        final int maxInstrument = instrumentq.peek();
        final int maxTotalCrowds = getTotalCrowds(
            input.totalMusiciansPerInstrument[maxInstrument],
            totalScoresPerInstrument[maxInstrument]
        );

        final Output output = new Output();
        output.totalCrowds = maxTotalCrowds;
        return output;
    }

    private int getTotalCrowds(final int totalMusicians, final int totalScores) {
        if (totalScores == 0) return Integer.MAX_VALUE;
        return ceilDiv(totalMusicians, totalScores);
    }

    private int ceilDiv(final int a, final int b) {
        return (a + b - 1) / b;
    }

    private int sum(final int[] array) {
        int sum = 0;
        for (final int value : array) sum += value;
        return sum;
    }
}

final class BufferedIO {
    private final BufferedReader in;
    private final BufferedWriter out;

    public BufferedIO(final InputStream in, final OutputStream out, final int bufferSize) {
        this.in = new BufferedReader(new InputStreamReader(in), bufferSize);
        this.out = new BufferedWriter(new OutputStreamWriter(out), bufferSize);
    }

    public String[] readLine(final String separator) throws IOException {
        final String line = readLine();
        return line == null ? null : line.split(separator);
    }

    public String readLine() throws IOException {
        String line = in.readLine();
        while (line != null && line.isEmpty()) line = in.readLine();
        return line;
    }

    public void write(final String format, Object... args) throws IOException {
        final String string = String.format(format, args);
        write(string);
    }

    public void write(final String string) throws IOException {
        out.write(string);
    }

    public void close() throws IOException {
        in.close();
        out.flush();
        out.close();
    }
}