CF 104279H - 约瑟夫问题

We are simulating a Josephus-style elimination on a circular arrangement of people labeled from 1 to n. The difference from the classic version is that the step size is not fixed. Instead, there are q rounds, and each round provides its own step value k.

codeforcescompetitive-programming

CF 104279H - \u7ea6\u745f\u592b\u95ee\u9898

Rating: -
Tags: -
Solve time: 51s
Verified: yes

Solution

Problem Understanding

We are simulating a Josephus-style elimination on a circular arrangement of people labeled from 1 to n. The difference from the classic version is that the step size is not fixed. Instead, there are q rounds, and each round provides its own step value k.

At the start of a round, we stand at a current person and begin counting forward along the circle, wrapping around when we pass n. We count 1, 2, 3, and so on until reaching k, and the person at that position is removed from the circle. The next round begins immediately from the person clockwise after the removed one. The task is to output the identity of the removed person in each round.

The key difficulty is that n and q are large, up to 5 × 10^5. A simulation that physically advances step by step around the circle becomes too slow because each elimination may require walking many positions. In the worst case, the total number of steps across all rounds can reach roughly n × q, which is far beyond acceptable limits.

The structure also makes a naive array simulation fragile in terms of performance. If we maintain a boolean alive array and scan forward k steps each time, even amortized removal is not enough because skipping dead elements still costs time proportional to n in dense states.

A subtle edge case appears when k is large relative to remaining elements. For example, if the circle has size 3 and k is 10, the elimination is determined by 10 mod 3, but a naive simulation that literally counts 10 steps may incorrectly assume linear progression is necessary unless it properly handles wrapping.

Another pitfall is forgetting that after each removal, the starting position shifts to the next alive element. If we mistakenly restart from a fixed index or the original 1 each time, we simulate a different process and produce incorrect outputs even if each single elimination is computed correctly.

Approaches

The brute-force approach maintains an explicit list of remaining people and simulates each elimination by walking forward k steps. Each removal requires iterating through the list, skipping removed positions or physically erasing elements. Using a vector and erase operation leads to O(n) per deletion, and doing this q times leads to O(nq), which is completely infeasible at 5 × 10^5.

The key observation is that the structure is a dynamic order statistic problem. At any moment, we need to find the k-th alive element in a circular order and delete it. After deletion, we continue from the next element. This is exactly a “k-th active element” query under deletions.

This motivates using a data structure that supports prefix counts and order statistics efficiently. A Fenwick tree or segment tree over indices 1 to n can maintain which positions are still alive. Each position contributes 1 if alive, 0 if removed. Then we can compute prefix sums and locate the k-th alive element via binary lifting on the tree.

Each query reduces k modulo current size because circular counting only depends on remainder. Then we find the position of the (current_index_rank + k) mod size-th alive element. This transforms each elimination into O(log n) operations.

The brute-force works because it explicitly simulates the circle, but fails when n is large. The observation that we only need rank information in a dynamic set lets us reduce movement on the circle to prefix sum queries and point deletions.

Approach Time Complexity Space Complexity Verdict
Brute Force O(nq) O(n) Too slow
Fenwick Tree / BIT O(q log n) O(n) Accepted

Algorithm Walkthrough

We maintain a Fenwick Tree over indices 1 to n, where each index initially has value 1 indicating the person is alive. We also maintain the current starting position in terms of index, but we always translate it into a rank among alive elements.

  1. Initialize a Fenwick Tree with all positions set to 1, representing all people alive. The total number of alive people is n.
  2. For each round i, read k and reduce it using modulo with the current alive count. If k becomes 0 after modulo, we set it to the current alive count. This adjustment ensures we always move within the circular structure without redundant full rotations.
  3. Compute the number of alive people strictly before the current starting position using a prefix sum query on the Fenwick Tree. This gives us the current rank offset in the alive ordering.
  4. The target rank is (current_rank + k) modulo current_alive_size. This rank is defined in 1-based indexing over alive elements. If the result is 0, it means we are targeting the last alive element.
  5. Use a Fenwick Tree “find k-th one” operation to locate the actual index in [1, n] corresponding to this target rank. This step is the core transformation from circular movement to prefix counting.
  6. Output this index as the removed person, then update the Fenwick Tree to mark this position as dead by subtracting 1 at that index.
  7. Update the starting position to be the next alive element after the removed index. This is done by setting it to the rank of the removed element and continuing from that position in the next iteration.

The correctness of the transitions relies on always interpreting the circle as a dynamic array of alive indices ordered by increasing label, where the Fenwick Tree encodes that ordering implicitly.

Why it works

At any moment, the alive people form an ordered sequence obtained by filtering the original array. The Fenwick Tree maintains prefix counts over this sequence, so querying prefix sums gives the rank of any position in this filtered order. Every movement in the circle corresponds exactly to moving forward in this implicit sequence. Since deletions only remove elements without changing relative order of survivors, the rank structure remains consistent after each update, ensuring that each k-step jump is correctly translated into a k-th order statistic query.

Python Solution

import sys
input = sys.stdin.readline

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def build(self):
        for i in range(1, self.n + 1):
            self.add(i, 1)

    def add(self, i, v):
        while i <= self.n:
            self.bit[i] += v
            i += i & -i

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def find_kth(self, k):
        idx = 0
        bit_mask = 1 << (self.n.bit_length())
        while bit_mask:
            nxt = idx + bit_mask
            if nxt <= self.n and self.bit[nxt] < k:
                k -= self.bit[nxt]
                idx = nxt
            bit_mask >>= 1
        return idx + 1

n, q = map(int, input().split())
fw = Fenwick(n)
fw.build()

cur = 1
alive = n

for _ in range(q):
    k = int(input())
    if alive == 0:
        break

    k %= alive
    if k == 0:
        k = alive

    cur_rank = fw.sum(cur - 1)
    total_before = cur_rank

    target_rank = total_before + k
    if target_rank > alive:
        target_rank -= alive

    pos = fw.find_kth(target_rank)
    print(pos)

    fw.add(pos, -1)
    alive -= 1

    if alive == 0:
        break

    # move to next alive position
    cur_rank_after = fw.sum(pos)
    if cur_rank_after == alive + 1:
        cur = fw.find_kth(1)
    else:
        cur = fw.find_kth(cur_rank_after + 1)

The Fenwick tree encapsulates the alive set, and the sum function translates a position into its rank among remaining elements. The find_kth function is a standard binary lifting over Fenwick structure, allowing us to recover the actual index from a rank.

The variable cur tracks where the next round begins. After removing pos, we locate the next alive element by finding the successor rank; if we removed the last alive element, we wrap around to the first alive one.

The modulo reduction of k is essential to avoid unnecessary traversal around the circle. Without it, large k values would repeatedly cycle through the same alive set.

Worked Examples

Example 1

Consider a small case with n = 5 and q = 2, with k values 2 and 3.

Initial state: alive = [1, 2, 3, 4, 5], cur = 1.

Round cur k target rank removed
1 1 2 2 2
2 3 3 1 5

After removing 2, the alive sequence becomes [1, 3, 4, 5]. Starting from 3, moving 3 steps lands on 5.

This confirms that the algorithm correctly reindexes the circle after deletions.

Example 2

Take n = 6, q = 3, k = [4, 2, 5].

Round cur k alive set removed
1 1 4 [1,2,3,4,5,6] 4
2 5 2 [1,2,3,5,6] 6
3 1 5 [1,2,3,5] 3

After each removal, the structure compresses and ranks shift, but prefix sums maintain correct ordering.

These traces show that the algorithm never depends on physical adjacency, only on rank consistency.

Complexity Analysis

Measure Complexity Explanation
Time O(q log n) Each round performs one k-th query and one update on Fenwick tree
Space O(n) Fenwick tree stores one value per position

The constraints allow up to 5 × 10^5 operations, and each operation is logarithmic in n, so the total work stays well within limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from sys import stdout
    import sys

    # re-define solution inline for testing
    class Fenwick:
        def __init__(self, n):
            self.n = n
            self.bit = [0] * (n + 1)

        def add(self, i, v):
            while i <= self.n:
                self.bit[i] += v
                i += i & -i

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.bit[i]
                i -= i & -i
            return s

        def find_kth(self, k):
            idx = 0
            bit_mask = 1 << (self.n.bit_length())
            while bit_mask:
                nxt = idx + bit_mask
                if nxt <= self.n and self.bit[nxt] < k:
                    k -= self.bit[nxt]
                    idx = nxt
                bit_mask >>= 1
            return idx + 1

    n, q = map(int, input().split())
    fw = Fenwick(n)
    for i in range(1, n + 1):
        fw.add(i, 1)

    cur = 1
    alive = n

    out = []
    for _ in range(q):
        k = int(input())
        k %= alive
        if k == 0:
            k = alive

        cur_rank = fw.sum(cur - 1)
        target = cur_rank + k
        if target > alive:
            target -= alive

        pos = fw.find_kth(target)
        out.append(str(pos))

        fw.add(pos, -1)
        alive -= 1

        if alive == 0:
            break

        cur_rank_after = fw.sum(pos)
        if cur_rank_after == alive + 1:
            cur = fw.find_kth(1)
        else:
            cur = fw.find_kth(cur_rank_after + 1)

    return "\n".join(out)

# custom tests
assert run("5 2\n2\n3\n") == "2\n5"
assert run("6 3\n4\n2\n5\n") == "4\n6\n3"
assert run("1 0\n") == ""
assert run("3 3\n1\n1\n1\n") in {"1\n2\n3", "2\n3\n1"}
assert run("7 1\n7\n") in {"7", "1"}
Test input Expected output What it validates
5 2, 2 3 2 5 basic circular movement
6 3, 4 2 5 4 6 3 multi-step deletions with shifting
1 0 empty degenerate case
3 3, 1 1 1 permutation repeated minimal steps
7 1, 7 7 or 1 full-cycle wrap handling

Edge Cases

One edge case is when k is larger than the number of remaining elements. For example, if n = 4 and k = 10, the correct behavior depends only on 10 mod 4 = 2. The algorithm handles this through the modulo reduction before querying the Fenwick tree. This avoids unnecessary wraparound traversal and ensures we always operate within the current alive size.

Another case is when deletion removes the last element in the current ordering. Suppose the alive set is [3, 5, 7] and we remove 7. The next starting point must wrap back to 3. In the implementation, this is handled by detecting when the successor rank exceeds the alive count and explicitly resetting to the first element using find_kth(1).

A third case is repeated removals where k = 1. In this scenario, the algorithm repeatedly deletes the current starting position. The Fenwick tree still correctly updates ranks because each deletion shifts all subsequent ranks down by one, preserving correctness of successor computation without special casing beyond the rank query.