UVA - 11351 - Last Man Standing 

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

Keywords: Josephus Problem, Recurrence Relation

Problem Summary 

Given:

  1. List of peoples

  2. Kill interval

We want to:

  1. Find the last survivor

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 primitive data structure as much as possible.

This problem is identical to the Josephus Problem. One of the known solution to this problem is to extract the pattern from every possible combination of total peoples and killing interval, which lead to the discovery of these recurrence relation:

Keep in mind that the equation above is for 0-index josephus problem.

Algorithm 

We could implement the equation is by using a recursive function. We also need to convert between 1-index and 0-index when using the recursive function.

The time complexity of this solution is O({total peoples}) 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;

/**
 * 11351 - Last Man Standing
 * Time limit: 1.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2326
 */
public class Main {
    public static void main(String... args) throws IOException {
        final BufferedIO io = new BufferedIO(System.in, System.out);
        final Process process = new Process();

        final int totalTestCases = Integer.parseInt(io.readLine());
        for (int i = 0; i < totalTestCases; i++) {
            final Input input = new Input();
            input.caseId = i + 1;
            final String[] lines = io.readLines(" ");
            input.totalPeoples = Integer.parseInt(lines[0]);
            input.interval = Integer.parseInt(lines[1]);

            final Output output = process.process(input);
            io.write("Case %d: %d\n", output.caseId, output.survivor);
        }

        io.close();
    }
}

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

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

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

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

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

    public BufferedIO write(final String string) throws IOException {
        out.write(string);
        return this;
    }

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

class Input {
    public int caseId;
    public int totalPeoples;
    public int interval;
}

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

class Process {
    public Output process(final Input input) {
        final Output output = new Output();
        output.caseId = input.caseId;
        output.survivor = josephus(input.totalPeoples, input.interval) + 1;
        return output;
    }

    private int josephus(final int totalPeoples, final int interval) {
        if (totalPeoples == 1) return 0;
        return (josephus(totalPeoples - 1, interval) + interval) % totalPeoples;
    }
}


Powered by Docmost