UVA - 12834 - Extreme Terror

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

Keywords: Greedy, Sorting

Objective

Given:

Number of businesses.
Number of deniable businesses.
Amount of money for Vuri Kamal for each businesses.
Amount of money for Kana Shamsu for each businesses.

We want to:

Determine whether Kana Shamsu is able to reach a profit.
Find the maximum amount of profit for Kana Shamsu.

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

The profit for Kana Shamsu for each businesses is the difference between the amount of money that Kana Shamsu received and Vuri Kamal received. We can use greedy strategy to maximize the amount of profit for Kana Shamsu by minimizing collection from loss-making businesses.

To minimize the loss, we want to deny money collection from the loss-making business starting from business that produces the greatest amount of loss until the maximum amount of denied business is reached. The remaining businesses

To maximize the profit, we want to collect money from every business that is profitable for Kana Shamsu. Since there is a limit to the number of business that can be denied (for money collection), we may need to collect money from loss-making business as well. . Keep track of the total profits on each iteration of the money collection. Kana Shamsu is profitable when the total profits is greater than 0.

Algorithm

To implement the greedy strategy, we first need to calculate the profit for Kana Shamsu on each businesses by subtracting the money he received with what Vuri Kamal received. After the profits is calculated, sort the profits from the least amount to the greatest amount. Then, we can do a linear scan to calculate the cumulative profits and ignore the loss until the maximum amount of deniable business is reached.

The time complexity of this solution is O({total businesses} * log({total businesses})) or O(10^7).

Implementation

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

/**
 * 12834 - Extreme Terror
 * Time limit: 1.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4699
 */
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 caseId = 1; caseId <= totalTestCases; caseId++) {
            final Input input = new Input();
            input.caseId = caseId;
            input.totalBusinesses = in.nextInt();
            input.totalDeniableBusinesses = in.nextInt();
            input.kamalMoneys = new long[input.totalBusinesses];
            input.shamsuMoneys = new long[input.totalBusinesses];
            for (int i = 0; i < input.totalBusinesses; i++) {
                input.kamalMoneys[i] = in.nextLong();
            }
            for (int i = 0; i < input.totalBusinesses; i++) {
                input.shamsuMoneys[i] = in.nextLong();
            }

            final Output output = process.process(input);
            if (output.isProfitable) {
                out.format("Case %d: %d\n", output.caseId, output.totalProfits);
            } else {
                out.format("Case %d: No Profit\n", output.caseId);
            }
        }

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

class Input {
    public int caseId;
    public int totalBusinesses;
    public int totalDeniableBusinesses;
    public long[] kamalMoneys;
    public long[] shamsuMoneys;
}

class Output {
    public int caseId;
    public boolean isProfitable;
    public long totalProfits;
}

class Process {
    public Output process(final Input input) {
        final long[] profits = new long[input.totalBusinesses];
        for (int i = 0; i < input.totalBusinesses; i++) {
            final long profit = input.shamsuMoneys[i] - input.kamalMoneys[i];
            profits[i] = profit;
        }
        Arrays.sort(profits);

        long totalProfits = 0;
        int totalDeniedBusinesses = 0;
        for (final long profit : profits) {
            final boolean loss = profit <= 0;
            if (loss && totalDeniedBusinesses < input.totalDeniableBusinesses) {
                totalDeniedBusinesses++;
                continue;
            }
            totalProfits += profit;
        }

        final Output output = new Output();
        output.caseId = input.caseId;
        output.totalProfits = totalProfits;
        output.isProfitable = totalProfits > 0;
        return output;
    }
}