I am not sure which part you wish me to elaborate:
- Why Josh must stand to the left of a soldier with A[P] <= F.
I think I have explained this sufficiently above.
- How to decide when Josh is attacked.
The alternate killing starts initially at the beginning, subsequently from the soldier to the right of Josh. If there is an even number of soldiers (excluding Josh) then the soldier to the left of Josh will be killed. If an odd number, Josh will need to defend himself, using up some of his defence.
- The way to maintain the number of soldiers left in each round.
As alternate soldiers are killed, the number after a round starting with Y other soldiers will be Y / 2 by integer division, alternatively = Y >> 1 (right-shift)
- Keeping track of the index of the soldier to the left.
This one is the most tricky. I use 0-based indexing in the description below and in the implementation:
Maintain several integers:
n1 = number of soldiers left, initially = N - 1
i_left = index of soldier to the left of Josh
r_left = number of passes from start to left of Josh
r_right = number of passes from after Josh to end N - 2
Note that r_right = r_left - 1, except when Josh is to the left of soldier 0.
When Josh is attacked, the soldier to his left remains unchanged.
When he is attacked, we need to change i_left to the soldier to the left of i_left, which needs to be calculated according to where we are and how many rounds we have had.
If i_left < P, we first reduce i_left by (1 << r_left) = 2 ^r_left. If the result is negative, we have gone beyond the start, and need to reset it to near the end, to a soldier whose index is the largest value of p + a multiple of 2^r_right which does not exceed n2. The use of a bit-mask is simply more efficient than using a mod % function.
If i_left >= P, then we reduce it similarly by (1 << r_right) = 2 ^r_right
Please look at the code for details. If you want me to go into more details about the bit-mask or any other parts of the algorithm, please ask!