BOJ. Josephus problem(2) (1168)

Problem: BOJ 1168 — Josephus Problem 2

There are N people in a circle, numbered from 1 to N. Repeatedly remove every K-th person, starting the count at the next person after the previous removal, and print the removal order in the form <a, b, ...>.

Fenwick tree of live people

Keep a Fenwick tree whose value at each position is 1 while that numbered person is still in the circle, and 0 after removal. A prefix sum therefore tells how many live people occur up to a position. The tree supports both removing a person and selecting the person with a given live-person rank in O(log N).

Let rank be the zero-based rank of the next person to count among the remaining live people. The person removed in this round has rank (rank + K - 1) % remaining. Find the original number at one-based order rank + 1 using Fenwick binary lifting, then decrement its count. The next count starts at the slot immediately after that removal, which now has zero-based rank rank % (remaining - 1); this is exactly the selected rank modulo the new circle size. Updating that rank only when people remain also handles the final removal without a modulo by zero. For N = 1, the only rank is 0, so the sole output is <1>.

Each of the N removals performs one order-statistic search and one update, giving O(N log N) time and O(N) space.

Java

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int n = input.nextInt();
        int k = input.nextInt();

        FenwickTree live = new FenwickTree(n);
        StringBuilder output = new StringBuilder("<");
        int rank = 0;

        for (int remaining = n; remaining > 0; remaining--) {
            rank = (int) ((rank + (long) k - 1) % remaining);
            int person = live.findByOrder(rank + 1);
            live.add(person, -1);
            if (remaining > 1) {
                rank %= remaining - 1;
            }

            if (output.length() > 1) {
                output.append(", ");
            }
            output.append(person);
        }
        output.append('>');
        System.out.print(output);
    }

    private static class FenwickTree {
        private final int size;
        private final int[] tree;
        private final int highestPowerOfTwo;

        FenwickTree(int size) {
            this.size = size;
            this.tree = new int[size + 1];
            for (int i = 1; i <= size; i++) {
                tree[i] = i & -i;
            }

            int power = 1;
            while (power <= size / 2) {
                power <<= 1;
            }
            highestPowerOfTwo = power;
        }

        void add(int index, int delta) {
            for (int i = index; i <= size; i += i & -i) {
                tree[i] += delta;
            }
        }

        int findByOrder(int order) {
            int index = 0;
            for (int step = highestPowerOfTwo; step > 0; step >>= 1) {
                int next = index + step;
                if (next <= size && tree[next] < order) {
                    index = next;
                    order -= tree[next];
                }
            }
            return index + 1;
        }
    }

    private static class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);

        int nextInt() throws IOException {
            int c;
            do {
                c = input.read();
            } while (c <= ' ' && c != -1);

            int value = 0;
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = input.read();
            }
            return value;
        }
    }
}