12

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)

Zero Piraeus
  • 56,143
  • 27
  • 150
  • 160
Edward Tonai
  • 121
  • 1
  • 5
  • Which `if` does the last `else` belong to? – biziclop Jan 30 '11 at 21:06
  • 2
    @biziclop - isn't it rather obvious it belongs to the last one...? – IVlad Jan 30 '11 at 21:14
  • @IVlad: Isn't it obvious to you that if the question has to be asked the code suffers from lack of clarity? – JimR Jan 30 '11 at 21:36
  • 1
    @JimR - The logic behind the code is indeed not clear, but that's what the question is about, so it can't be helped. The syntax however is very clear. – IVlad Jan 30 '11 at 21:40
  • @IVlad: I think you'll catch on once you gain some experience fixing bugs in this type of code. – JimR Jan 30 '11 at 21:41
  • 1
    @JimR - actually, I have about 5 years experience working with this type of algorithm-competition code. It might be a bit cryptic and not follow the best industry standards, but I can assure you it's correct and written as it is intended to work, because it is the official (or at least a correct) solution to the given problem. I apologize to @biziclop if my question sounded rude or anything, that was not my intention. I just meant to emphasize that the code **works**, and the question is about **why it works**. – IVlad Jan 30 '11 at 21:46
  • @Mad No worries, I'm on the brink of understanding it but not quite there yet. :) – biziclop Jan 30 '11 at 21:58
  • @Oscar Lopez You're editing all these problems to have tag `josephus`, which you have created (I reckon). But there is not description for that tag. – Walter Sep 21 '13 at 13:40
  • @Walter wait for it... be patient – Óscar López Sep 21 '13 at 13:42

1 Answers1

5

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.

biziclop
  • 48,926
  • 12
  • 77
  • 104
  • May I ask what's the complexity of this algorithm? Even faster than O(n)? so O(logn) I suppose? – noooooooob Feb 27 '14 at 11:15
  • 2
    I didn't invent the algorithm so I'm not entirely certain but Wikipedia claims it's O(k*logn), which looks about right. – biziclop Mar 04 '14 at 11:46