Menu
Description: There are people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.
I Googled this 'Josephus problem' and the Wikipedia hit gives me a dynamic-programming solution: f(n,k)=((f(n-1,k)+k-1) mod n)+1, with f(1,k)=1, but this only yields the last survivor. How can I get the sequence of the people executed? Say, p(5, 3) = {3,1,5,2,4}.
Also, is there a O(nlogn) solution instead of a O(nk) one?
615
There are N people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed.
The problem is named after Flavius Josephus, a Jewish historian living in the 1st century. According to Josephus' account of the siege of Yodfat, he and his 40 soldiers were trapped in a cave by Roman soldiers.
The time complexity is O(N).
To get sequence of executed persons and last survivor you just need to simulate whole process from the beginning. Given description of procedure this would be quite easy task. Formula that you present is only shortcut to check who will survive and to obtain answer quickly.
Description on how to do this in O(n log n) using Range Trees is here: http://pl.scribd.com/doc/3567390/Rank-Trees
More detailed analysis can be found here: http://www.imt.ro/romjist/Volum12/Number12_1/pdf/02-MCosulschi.pdf
121
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
