Josephus Problem 2

Explanation

This problem is similar to the previous one, except we cannot simply loop and alternate the numbers. Here, we'll have to use a complex data structure to keep track of the children and their positions. We'll use an indexed_set from the pb_ds library. This data structure is similar to a set, but it also allows us to access the ith element in the set in O(log n) time. This is exactly what we need to solve this problem.

Behind the scenes, this data structure is implemented as a Red Black Tree. This is a self-balancing binary search tree. This means that the tree will always be balanced, and the height of the tree will always be O(log n). This is important because it means that all operations on the tree will be O(log n).

Unfortunately, I wasn't able to implement it in Python and Rust. I am still learning these data structures and once I learn more, I will update this post with the Python and Rust implementations.

Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

// SOURCES: https://codeforces.com/blog/entry/5631
//          https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/
template <typename T> using indexed_set =  tree<T,\
            null_type, less<T>, rb_tree_tag,\
            tree_order_statistics_node_update>;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    indexed_set<int> children;
    for (int i = 1; i <= n; i++) children.insert(i);

    int index = k + 1;
    while (children.size() > 1) {
        index %= children.size();
        if (index == 0) index = children.size();

        auto it = children.find_by_order(index - 1);
        cout << *it << " ";
        children.erase(it);

        index += k;
    }

    cout << *children.begin() << endl;
}