Overview

A simulation problem where \(N\) children arranged in a circle pass a ball in order, with each child who passes the ball leaving the circle. Using a BIT (Binary Indexed Tree), we efficiently find the \(k\)-th child among those remaining.

Analysis

Problems with the Naive Approach

If we simply manage the circle with a list or array and count one by one, since \(D_i\) can be as large as \(10^9\), counting one at a time will result in TLE.

Key Insights

1. Speedup using modulo: When there are \(R\) children remaining (excluding the ball holder), counting to the \(D_i\)-th person may involve going around the circle multiple times, but it is effectively the same as finding the \(((D_i - 1) \mod R + 1)\)-th person. This limits the count to at most \(R\).

2. The “find the \(k\)-th remaining child” problem: The operation of counting while skipping children who have left the circle can be reduced to the problem: “Among the currently remaining children, who is the \(k\)-th child clockwise from a given position?”

3. Finding the \(k\)-th element with BIT: By storing the presence (1 or 0) of each child in the BIT, the prefix sum tells us “how many children remain at or before position \(i\)”. Furthermore, using binary search on the BIT (find_kth), we can find “the index of the \(k\)-th remaining child overall” in \(O(\log N)\).

Algorithm

1. Initialize the BIT and set all positions to 1 (all children are in the circle).
2. For each pass, do the following:
   • Compute the effective distance effective_d by taking the modulo of \(D_i\) with the remaining count \(R = N - i - 1\) (excluding the current ball holder).
   • Find the number of remaining children after that are after the current position current (on the side with larger indices).
   • If effective_d <= after, search for the effective_d-th child after current. Specifically, find the child at overall cumulative rank bit.query(current) + effective_d using find_kth.
   • Otherwise, wrap around to the beginning and search for the (effective_d - after)-th child.
3. Remove current from the BIT (update its value to -1) and update the ball holder.
4. After \(M\) passes, output current.

Concrete Example

For \(N=5, S=3, D_1=7\): - Remaining count \(R=4\), effective_d \(= (7-1) \mod 4 + 1 = 3\) - Starting from position 3, count 3 people clockwise → counting 4, 5, 1, the ball is passed to 1 - Remove position 3

Complexity

• Time complexity: \(O((N + M) \log N)\) (initialization takes \(O(N \log N)\), each pass takes \(O(\log N)\))
• Space complexity: \(O(N)\)

Implementation Notes

• Implementation of find_kth: Performs binary search on the BIT to find the minimum position where the prefix sum is at least \(k\) in \(O(\log N)\). Using a standard binary search + query would result in \(O(\log^2 N)\), but by exploiting the internal structure of the BIT, this is reduced to \(O(\log N)\).

• Handling the circular structure: By splitting into two cases — “after current” and “from the beginning” — the circular traversal is converted into operations on a linear array.

• Overflow of \(D_i\): Since \(D_i\) can be up to \(10^9\), it should be read as long long and the modulo computation must be done correctly.

  Source Code

#include <bits/stdc++.h>
using namespace std;

struct BIT {
    int n, log_n;
    vector<int> tree;
    BIT(int n) : n(n), tree(n + 1, 0) {
        log_n = 0;
        while ((1 << (log_n + 1)) <= n) log_n++;
    }
    void update(int i, int val) {
        for (; i <= n; i += i & (-i))
            tree[i] += val;
    }
    int query(int i) {
        int s = 0;
        for (; i > 0; i -= i & (-i))
            s += tree[i];
        return s;
    }
    int find_kth(int k) {
        int pos = 0;
        for (int pw = (1 << log_n); pw > 0; pw >>= 1) {
            if (pos + pw <= n && tree[pos + pw] < k) {
                pos += pw;
                k -= tree[pos];
            }
        }
        return pos + 1;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M, S;
    cin >> N >> M >> S;
    
    BIT bit(N);
    for (int i = 1; i <= N; i++)
        bit.update(i, 1);
    
    int current = S;
    for (int i = 0; i < M; i++) {
        long long D;
        cin >> D;
        
        long long remaining = N - i - 1; // countable children (excluding current holder)
        int effective_d = (int)(((D - 1) % remaining) + 1);
        
        // Count active children with index > current
        int after = bit.query(N) - bit.query(current);
        
        int target;
        if (effective_d <= after) {
            int rank = bit.query(current) + effective_d;
            target = bit.find_kth(rank);
        } else {
            int k = effective_d - after;
            target = bit.find_kth(k);
        }
        
        // Remove current from circle
        bit.update(current, -1);
        current = target;
    }
    
    cout << current << endl;
    return 0;
}

This editorial was generated by claude4.6opus-thinking.