UVA - 12840 - The Archery Puzzle 

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

Keywords: Dynamic Programming, Coin Change, Pointer

Problem Summary 

Given:

  1. Total targets

  2. List of score for each target

  3. Expected total scores

We want to:

  1. Determine whether it is possible or not to obtain the expected total scores

  2. Find the minimum number of arrows

  3. List target scores in descending order

Observation 

First, we need to be extra careful with the time limit of this problem. It has 1 second time limit, so for Java user, this means we must use fast IO and primitive data structure as much as possible.

Next, we want to pick a list of target that satisfy the total scores required and has minimum amount of total arrows. We can hit the same target multiple times if needed. This is similar to the concept of Coin Change in Dynamic Programming. Coin Change is a classic Dynamic Programming problem where we want to find the number of ways to produce a sum from a different coin denominations. Notice that our targets is equivalent to the “coin denominations”, and the total scores is equivalent to the “sum”. Coin Change made it possible for us to iterate over the permutation of targets for every possible total scores.

Once we’re able to identify the permutations, we need to find a way to optimally retrieve the list of targets. This can be done by taking advantage of the sequence of the Coin Change algorithm. Coin Change works by creating a new permutation every time we iterate over the target and total point. This means that to preserve the sequence, we just need to chain the old permutation and the new permutation together using a pointer. This will enable us to retrieve the sequence by traversing the last pointer.

And last, just keep permutation with minimum number of total arrow and sort the end result targets in descending order.

Algorithm 

We could use an array to store the coin change result. The index of the array will be used to store the total coins, and the value of the array will be used to store the permutation data. For the loop, we want to create a permutation of targets and total scores, and we can do this by creating a nested loop. Don’t forget to initiate the permutation data for 0 total coins with empty permutation data.

Next, we need to define the permutation data. At least, to fulfill the problem output, we want to know the total arrows, last target, and link to the previous permutation.

Last, it is impossible if there is no permutation data for the desired total coins. The number of arrows should be available on the permutation data, and the list of target can be retrieved by traversing the previous permutation data.

The time complexity for this solution is O({total targets} * {total scores}) or O(10^4).

Implementation 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;

/**
 * 12840 - The Archery Puzzle
 * Time limit: 1.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4705
 */
public class Main {
    public static void main(final String... args) throws IOException {
        final BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        final BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        final Process process = new Process();

        final int totalTestCases = Integer.parseInt(readLine(in));
        for (int i = 0; i < totalTestCases; i++) {
            final Input input = new Input();
            input.caseId = i + 1;

            final String[] l1 = readSplitLine(in);
            input.totalTargets = Integer.parseInt(l1[0]);
            input.expectedTotalPoints = Integer.parseInt(l1[1]);
            input.targets = new int[input.totalTargets];

            final String[] l2 = readSplitLine(in);
            for (int j = 0; j < input.totalTargets; j++) {
                input.targets[j] = Integer.parseInt(l2[j]);
            }

            final Output output = process.process(input);
            out.write(String.format("Case %d: ", output.caseId));
            if (output.isPossible) {
                out.write(String.format("[%d]", output.totalArrows));
                for (final int point : output.points) {
                    out.write(String.format(" %d", point));
                }
                out.write('\n');
            } else {
                out.write("impossible\n");
            }
        }

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

    private static String[] readSplitLine(final BufferedReader in) throws IOException {
        final String line = readLine(in);
        return line == null ? null : line.split(" ");
    }

    private static String readLine(final BufferedReader in) throws IOException {
        String line = in.readLine();
        while (line != null && line.isEmpty()) line = in.readLine();
        return line;
    }
}

class Input {
    public int caseId;
    public int totalTargets;
    public int[] targets;
    public int expectedTotalPoints;
}

class Output {
    public int caseId;
    public boolean isPossible;
    public int totalArrows;
    public int[] points;
}

class Process {
    public Output process(final Input input) {
        final Progress result = doCoinChangeDynamicProgramming(input);

        final Output output = new Output();
        output.caseId = input.caseId;
        output.isPossible = result != null;
        output.totalArrows = output.isPossible? result.totalArrows : 0;
        output.points = output.isPossible? result.points() : null;

        return output;
    }

    private Progress doCoinChangeDynamicProgramming(final Input input) {
        final Progress[] progressPerTotalPoints = new Progress[input.expectedTotalPoints + 1];
        progressPerTotalPoints[0] = new Progress();

        for (int targetId = 0; targetId < input.totalTargets; targetId++) {
            final int target = input.targets[targetId];

            for (int totalPoints = 0; totalPoints <= input.expectedTotalPoints; totalPoints++) {
                final Progress progress = progressPerTotalPoints[totalPoints];
                if (progress == null) continue;

                final Progress newProgress = progress.next(target);
                if (newProgress.totalPoints > input.expectedTotalPoints) continue;

                final Progress oldProgress = progressPerTotalPoints[newProgress.totalPoints];
                if (oldProgress == null || newProgress.totalArrows <= oldProgress.totalArrows) {
                    progressPerTotalPoints[newProgress.totalPoints] = newProgress;
                }
            }
        }

        return progressPerTotalPoints[input.expectedTotalPoints];
    }
}

class Progress {
    public final Progress previous;
    public final int totalPoints;
    public final int totalArrows;
    public final int target;

    public Progress() {
        this.previous = null;
        this.totalPoints = 0;
        this.totalArrows = 0;
        this.target = 0;
    }

    private Progress(
        final Progress previous,
        final int totalPoints,
        final int totalArrows,
        final int target
    ) {
        this.previous = previous;
        this.totalPoints = totalPoints;
        this.totalArrows = totalArrows;
        this.target = target;
    }

    public Progress next(final int target) {
        return new Progress(
            this,
            totalPoints + target,
            totalArrows + 1,
            target
        );
    }

    public int[] points() {
        final LinkedList<Integer> targets = new LinkedList<>();
        for (Progress progress = this; progress != null; progress = progress.previous) {
            if (progress.target != 0) {
                targets.add(progress.target);
            }
        }
        final int[] points = targets.stream().mapToInt(Integer::intValue).sorted().toArray();
        for (int i = 0, j = points.length - 1; i < j; i++, j--) {
            final int point1 = points[i];
            final int point2 = points[j];
            points[i] = point2;
            points[j] = point1;
        }
        return points;
    }
}


Powered by Docmost