h2. Additional problems

# *(Josephus Problem)* $n$ people numbered from 1 to $n$ sit in a circle and play a game. Starting from the first person and every $k$th person is eliminated. Write an algorithm that prints out the order in which people are eliminated.

# *(Josephus Problem)* $n$ people numbered from 1 to $n$ sit in a circle and play a game. Starting from the first person and every $kth$ person is eliminated. Write an algorithm that prints out the order in which people are eliminated.

# *(Level Ancestor)* You are given an tree of size $n$. $ancestor(node, levelsUp)$ finds the node’s ancestor that is $levelsUp$ steps up. For example, $ancestor(node, 1)$ returns the father and ancestor(node, 2) returns the grandfather. Implement $ancestor(node, levelsUp)$ efficiently. ($O(sqrt(n))$ per query)
# *(Range Median)* You are given an array of size $n$. Implement a data structure to perform update operations $a[i] = k$ and range median operations efficiently. The range median query, $median(l, r)$  returns the median element of the sorted subsequence $a[l..r]$. $O(log{n})$ per update and $O(sqrt(n)log(n))$ per query