Josephus for large n (Facebook Hacker Cup)

Question

Last week I participated in round 1b of the Facebook Hacker cup.

One of the problems was basically the Josephus problem

I've studied the Josephus problem before as a discrete math problem, so I basically understand how to get the recurrence:

f(n,k) = (f(n-1,k) + k) mod n, with f(1,k) = 0

But that didn't work in the Facebook Hacker Cup, because the max value of n was 10^12. The mak value of k was 10^4.

Wikipedia mentions an approach when k is small and n is large. Basically remove people from a single round, and then renumber. But it's not described much and I don't understand why the renumbering works.

I looked at sample working source code for the solution, but I still don't understand that final portion.

long long joseph (long long n,long long k) {
    if (n==1LL) return 0LL;
    if (k==1LL) return n-1LL;
    if (k>n) return (joseph(n-1LL,k)+k)%n;
    long long cnt=n/k;
    long long res=joseph(n-cnt,k);
    res-=n%k;
    if (res<0LL) res+=n;
    else res+=res/(k-1LL);
    return res;
}

The part I really don't understand is starting from res-=n%k (and the lines thereafter). How do you derive that that is the way to adjust the result?

Could someone show the reasoning behind how this is derived? Or a link that derives it? (I didn't find any info on UVA or topcoder forums)

Answer 1

Right, I think I cracked it.

Let's look at how the iterations go with n=10, k=3:

0 1 2 3 4 5 6 7 8 9    n=10,k=3
1 2   3 4   5 6   0    n=7,k=3

Observe how the elements of the second iteration map to the first one: they are transposed by n%k, because the circle wraps around. That's why we correct the result by subtracting 10%3. The numbers in the second row appear in groups of k-1, hence the correction by res/(k-1).

The other case is hit further along the iterations

0 1 2 3 4     n=5,k=3
2 3   0 1     n=4,k=3

Now j(4,3) returns 0, which corrected by 5%3 turns out to be -2. This only happens if the result of the second row is in the last group, in which case adding n to the result will give us our original index.