UVA - 1176 - A Benevolent Josephus 

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

Keywords: Josephus Problem, Recurrence Relation

Problem Summary 

Given:

  1. Total players

We want to:

  1. Find total payments

Glossary 

  1. Josephus Problem — A theoretical problem related to a certain counting-out game.

  2. Recurrence Relation — A mathematical expression that defines a sequence in terms of its previous terms.

Observation 

For each round of the game, we want to alternately remove players until there is only 1 player left. Every players with ID greater than the survivor are eliminated, while the remaining players will goes to the next round. We’ll repeat the process until there is no player that can be eliminated, or in other words, the survivor has the greatest ID compared to the remaining players.

This is similar to Josephus Problem. Since we want to alternately remove players, this is a Josephus Problem with interval equals to 2. There is a known recurrence relation equation to find a survivor of a Josephus Problem, which is based on the brute force modeling of the Josephus Problem:

Keep in mind that the equation above is for 0-index Josephus Problem.

The total players of the round will be equals to the survivor of the previous round of the Josephus Problem. We will pay an amount equals to the number of eliminated players on each round, and twice the amount of the total players for the last round.

Algorithm 

Based on the constraints, there might be 32,767 players at maximum. To avoid stack overflow error, we should avoid implementing the recurrence relation as a recursive function. The equation can be converted into an iterative computation by calculating the survivor from the base case (total players = 1) until the maximum case (total players = 32767).

After we have discovered the survivor of each possible total players, we just need to run the game until there are no players that can be eliminated while keeping track of the total payments on each round.

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

Implementation 

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

/**
 * 1176 - A Benevolent Josephus
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3617
 */
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();

        while (in.hasNextInt()) {
            final Input input = new Input();
            input.totalPlayers = in.nextInt();

            final Output output = process.process(input);
            out.println(output.totalPayments);
        }

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

class Input {
    public int totalPlayers;
}

class Output {
    public int totalPayments;
}

class Process {
    private static final int INTERVAL = 2;
    private static final int MAX_TOTAL_PEOPLES = 32767;
    private static final int[] SURVIVORS = findSurvivors(MAX_TOTAL_PEOPLES, INTERVAL);

    private static int[] findSurvivors(final int maxTotalPeoples, final int interval) {
        final int[] survivors = new int[maxTotalPeoples + 1];

        survivors[0] = -1;
        survivors[1] = 0;

        for (int totalPeoples = 2; totalPeoples <= maxTotalPeoples; totalPeoples++) {
            survivors[totalPeoples] = (survivors[totalPeoples - 1] + interval) % totalPeoples;
        }

        return survivors;
    }

    public Output process(final Input input) {
        final Output output = new Output();

        int totalPayments = 0;
        int totalPlayers = input.totalPlayers;

        while (true) {
            final int survivor = SURVIVORS[totalPlayers] + 1;
            final boolean canRemove = survivor < totalPlayers;

            if (canRemove) {
                final int payment = (totalPlayers - survivor);
                totalPayments += payment;
                totalPlayers = survivor;
            } else {
                final int payment = totalPlayers * 2;
                totalPayments += payment;
                totalPlayers = survivor;

                output.totalPayments = totalPayments;
                return output;
            }
        }
    }
}


Powered by Docmost