Josephus Permutation problem

 

Link to the article Rank Tree:

http://tclab.kaist.ac.kr/~otfried/cs206/notes16.pdf

 

(Rank tree is a binary search tree that support the operation finding k-th element and others related to it)

 

Problem 1521 Timus War Games II

 

//1521 Timus - War Games II

//Josephus permutation problem

//O(nlogn) algorithm

//Using a binary search tree, initially containing n numbers 1, 2, .., n

//- Find, delete kth number in O(logn)

//The only rather complicated procedure is deleting a node in BST !

 

//You have n+1 numbers, then you delete pth number:

// . . . . x . . . . . . .

// From x, count k numbers more, the new ranks is (x + k - 1) % n !

 

#include <iostream>

using namespace std;

 

struct node

{

int i, s;

node *l, *r;

};

 

class bst

{

private:

node *r;

node * leftmost(node *);

node * deletelm(node *); //delete the left-most element

void recomputesize(node *);

node * buildtree(int, int);

node * findrank(node *, int);

node * removerank(node *, int);

public:

int n;

bst(int);

int rank(int); // find the element with rank k

void remove(int); // remove the element with rank k

};

 

node * bst::leftmost(node *p)

{

while (p->l!=NULL) p=p->l;

return p;

}

 

node * bst::deletelm(node *p) // return the new root of the subtree

{

node *r = p;

node *q = NULL;

while (p->l!=NULL) {q=p; p->s--; p=p->l;}

if (q!=NULL)

{

q->l=p->r;

return r;

}

else

return p->r;

}

 

void bst::recomputesize(node *p)

{

int ls=(p->l!=NULL)? p->l->s : 0;

int rs=(p->r!=NULL)? p->r->s : 0;

p->s=ls+rs+1;

}

 

node * bst::buildtree(int i, int j) // return the root of the subtree

{

if (i > j) return NULL;

node *p=new node;

int m = (i+j)/2;

p->i=m;

p->s=j-i+1;

p->l=buildtree(i, m-1);

p->r=buildtree(m+1, j);

return p;

}

 

node * bst::findrank(node *p, int k) // return the kth-rank element in the subtree

{

int ls = p->l==NULL ? 0 : p->l->s;

if (k<=ls) return findrank(p->l, k);

if (k>ls+1) return findrank(p->r, k-ls-1);

return p;

}

 

node * bst::removerank(node *p, int k) // return the new-root of the sub-tree

{

int ls = p->l==NULL ? 0 : p->l->s;

if (k<=ls) p->l=removerank(p->l, k);

else

if (k>ls+1) p->r=removerank(p->r, k-ls-1);

else

if ((p->l!=NULL) && (p->r!=NULL))

{

p->i=leftmost(p->r)->i;

p->r=deletelm(p->r);

}

else

p = (p->l!=NULL) ? p->l : p->r;

if (p!=NULL) recomputesize(p);

 

return p;

}

 

bst::bst(int n)

{

this->n=n;

r=buildtree(1, n);

}

 

int bst::rank(int k)

{

return findrank(r, k)->i;

}

 

void bst::remove(int k)

{

n--;

r=removerank(r, k);

}

 

// ------------------------------------------------------

 

int main()

{

int n, k;

cin >> n >> k;

bst b(n); // create new binary search tree

int p=1; // rank

for (int i=0; i<n; i++)

{

//new rank

p=(p+k-1)%b.n;

if (p==0) p=b.n;

 

cout << b.rank(p) << " ";

b.remove(p);

}

return 0;

}