UVA - 11804 - Argentina 

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

Keywords: Greedy, Sorting

Objective 

Given:

  1. List of player names.

  2. List of player attacking abilities.

  3. List of player defending abilities.

  4. Rules for assignment:

    1. Maximize total attacking abilities.

    2. If more than one result, maximize total defending abilities.

    3. If more than one result, use the first lexicographically increasing attackers name.

We want to:

  1. Find the optimal attackers and defenders assignment.

  2. Give the names in lexicographically increasing order.

Glossary 

  1. Greedy — A strategy to choose the locally optimal option at each step, in assumption that it will eventually lead to a globally optimal solution.

  2. Sorting — Rearrangement of a given array or list of elements according to a comparison operator on the elements.

Observation 

Based on the rules, the priority for the assignment are from the attack, defend, and name. For attack, it is obvious that the greater the attacking abilities is, the greater the sum will be. In this case, we could apply greedy strategy to assign players with the greatest attacking abilities as the attackers, and the remaining players should automatically become the defenders.

Next, we want to maximize the defend without compromising the attack. In this case, we want to extend the greedy strategy to assign players with the greatest attacking abilities and the least defending abilities as the attackers.

After that, we want to find the first lexicographically increasing assigment. In this case, we want to extend the greedy strategy to assign players with the greatest attacking abilities, the least defending abilities, and the lexicographically increasing names as the attackers.

After we have identified the optimal attackers and defenders configuration, the list of attackers and defenders should be ordered by its name.

Algorithm 

The greedy strategy can be implemented using sorting algorithm. The sort should be based on increasing attacking abilities, decreasing defending abilities, and lexicographically increasing names. After the players are sorted, the first 5 players will become the attackers, while the remaining automatically become the defenders. After this is done, we should use the sorting algorithm again to sort the attackers and defenders based on lexicographically increasing names.

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

Implementation 

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

/**
 * 11804 - Argentina
 * Time limit: 1.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2904
 */
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.players = new Player[10];
            for (int j = 0; j < 10; j++) {
                final Player player = new Player(in.next(), in.nextInt(), in.nextInt());
                input.players[j] = player;
            }

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

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

class Input {
    public int caseId;
    public Player[] players;
}

class Output {
    public int caseId;
    public Player[] attackers;
    public Player[] defenders;
}

class Process {
    private static final Comparator<Player> ORDER_BY_ABILITIES_AND_NAME = Comparator
        .comparingInt((Player p) -> -p.attack)
        .thenComparingInt((Player p) -> p.defense)
        .thenComparing((Player p) -> p.name);
    private static final Comparator<Player> ORDER_BY_NAME = Comparator
        .comparing((Player p) -> p.name);

    public final Output process(final Input input) {
        final Player[] players = input.players;
        Arrays.sort(players, ORDER_BY_ABILITIES_AND_NAME);

        final Player[] attackers = Arrays.copyOfRange(input.players, 0, 5);
        Arrays.sort(attackers, ORDER_BY_NAME);

        final Player[] defenders = Arrays.copyOfRange(input.players, 5, 10);
        Arrays.sort(defenders, ORDER_BY_NAME);

        final Output output = new Output();
        output.caseId = input.caseId;
        output.attackers = attackers;
        output.defenders = defenders;
        return output;
    }
}

class Player {
    public final String name;
    public final int attack;
    public final int defense;

    public Player(final String name, final int attack, final int defense) {
        this.name = name;
        this.attack = attack;
        this.defense = defense;
    }
}


Powered by Docmost