ad_red's blog

Multiple people Josephus problem
By ad_red, history, 10 months ago, In English

I have a modification of the Josephus problem (e.g., we have $$$n$$$ people in a circle, and we kick each $$$k$$$-th out till we have only one, tell which number he has), but I have to output the order in which the last $$$4$$$ people (I guess it generalises to $$$p$$$ people in the end) are kicked out.

The constraints are $$$10^7$$$ for both $$$n$$$ and $$$k$$$, which makes it almost impossible to pass a naive solution ($$$O(n \log{k})$$$) without optimisation magic. All Josephus problem approaches which are known to me seem to be ungeneralisable to get the order of elements which are removed from the circle.

Feel free to comment if you have any ideas! The unfolding from the last state (1 element left) doesn't seem to be a very promising strategy, but I might have missed some important observations.

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
10 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Hope I'm not misinterpreting the problem (I'm assuming "last" means "the final remaining people"), but if I'm not, you can solve it in $$$O(np)$$$ time by using the usual $$$O(n)$$$ solution. Another way you can think about that solution:

Say I have some pointer which starts at zero, and during some round with $$$i$$$ elements, I'm looking at the $$$s$$$th element. I want to know where the $$$s$$$ th element was in the round with $$$(i + 1)$$$ elements in relation to the pointer. Since I've advanced the pointer by $$$k$$$ to move from $$$(i + 1)$$$ to $$$i$$$, I'm subtracting $$$k$$$ from the distance from $$$s$$$ to the pointer. That means to go back a round we just need to add $$$k$$$.

There's probably a more clever way to implement this but here's a solution using a boolean array to keep track of which element actually gets removed during the round.

Spoiler

(If "last" meant the order of "persons $$$(n - p + 1), ... (n - 1), n$$$, then I have no ideas :p)

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks! Such a nice idea! I guess it would be nice to have this way of solving somewhere on CF, so here we are lol

    → Reply