Nice approach 
Also the part where you defined fast i/o lines as nfs_mw…I love that game.
1 Like
Couldn’t agree more. I personally was too lazy to implement this one and also nothing new to learn. On contrary, people got to learn DP and at least about quadratic residue/congruences from CIRMERGE and GUESSPRIME.
1 Like
can you please debug my code where i am missing…in subtask 1 i got 2 ac and and for some testcases i got wrong answer.i tried too much to find some cases which i am missing.
i have done this problem with recursion.
https://www.codechef.com/viewsolution/25282485
@anand20, If you think is not nice to solve is probably beause you solved it the wrong way.
- is not necessary to find any pattern in the problem, just working the indices in binary and simulation is enough. And even if a pattern is required to be found, I think is ok, math is the science of patterns.
- You can learn something new, it is actually a nice tweak of Josephus problem
- Is not hard to implement, tester solution is very small.
9 Likes
Totally agree with you. Thanks for mentioning 2nd point, got new thing to learn😃
For me this was the easiest problem in the Div 1 Challenge. (I failed to find the solution to several others.)
First note that the soldier to the right of Josh will survive all the rounds of killing, until there are only 2 left. As Josh wants this other soldier to be killed rather than himself in the final attack, this other soldier should have a power <= F. Therefore we need only consider Josh in positions where A[P] <= F.
Now consider the solution for Josh starting between P-1 and P with 1-based indexing, as described in the problem. On the first part-round from the start until Josh, he will be attacked only if (P-1) is odd. X = Floor((P-1)/2) soldiers will be killed, leaving Y = N-1-X where Josh is not included in this total. On subsequent rounds, starting from the soldier to the right of Josh, Josh will be attacked only if Y is odd. A simple loop with bit-shifting is all that is needed to solve for each potential starting position, but some care is needed to maintain the index of the soldier to the left of Josh in each round.
You can find my solution at CodeChef: Practical coding for everyone which passed in 0.1 seconds.
Wow your solution looks clean, Can you please elaborate your solution/algo.
You can notice that it is easy to solve this problem for only P = 1. So I somehow maintained a data structure that treats any position as P = 1, by doing some maintenance through a deque. It can be achieved simply using a vector as well but meh I wrote down what came to my mind first. The deque contains the order of warriors alive when the sword crosses josh the first time, from the point of view of Josh. I increment i, meaning position of Josh and make the simple changes to the deque.
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!
i wrote the code for this problem in O(Nlog(N)) and still got TLE in 2 of the results but according to me O(Nlog(N)) is appropriate if we see the constraints
here is my code. Please help!!
i wrote the code for this problem in O(Nlog(N)) and still got TLE in 2 of the results but according to me O(Nlog(N)) is appropriate if we see the constraints
here is my code. Please help!!
Actually I was referring to megatron10 's solution.
But anyways thanks for your detailed explanation.
A little doubt.
The first attacking soldier is the one on the first position or Soldier 1?
In case P=1; is the first atticking soldier josh?
josh will never attack and soldier 1 will always start the attack.
The first attacking soldier is the one on the first position or Soldier 1?
Soldier on first position is Soldier 1 only.
Soldier 1 is attacking soldier always. but if P=1, Soldier 1 is Josh therefore his attack chance passes to 2nd soldier.
why my programe give TLE,
even my complexity is O(NlogN)
https://www.codechef.com/viewsolution/25344615
Wow.
I am amazed by line 46,47. I wonder how you found out that this would always give the index of next person that attacks. Was it due to some past experience on working something similar ? or was it due to some clever thaught process ?
The positions of people in the deque that are alive forms an arithmetic progression. Initially, the common difference is 1. Alternate people are killed, and the difference doubles. j is the size of the arithmetic progression. I just referred the last person in the series by using the formula for the term in arithmetic progression, a + (n-1)*d. a being 0, n being j and d being k.
I think this is not observation-based or experience-based, its just simple logic.
3 Likes
ye easy question hai bhai…khud try kar pata chal jaayega 