Tutorial 319B - Psychos in a Line
Let's start with a hint : Assume
Step[i] as the step that i-th person was killed. And
Kill[i] as the number of people that i-th person has killed. Now try to find :
Who Will Kill i-th Person?
And then, update to
Now we will use a stack to update
Kill, based on the person who killed i-th person. So, we will start from the 1-st person and updating. The first person will survive for sure (sth clear). We add first person to stack. (When i-th person survive,
Step[i] = -1.)
Now we want to add i-th person to the stack Assume B as the top of the stack and A as the unique ID of the i-th person that we want to add him. While B < A It is not possible that B kills A. So we continue removing persons from the top of the stack. There is two situations :
1 : We don't find sb that Can kill A. In this case, we just add A to the stack.
2 : We found sb like B such that
B > A In this case, we have to check, is it possible that B, survive in order to kill A? For checking that
Step[B] must be strictly bigger than
Step[B] = -1.
And when we found a person like B that can kill A, the updates would be like this :
Kill[B]++; Step[A] = Kill[B];
The answer of the question would be the maximum of array
Here , You can find my implementation 82179372.
At The End, I Would Really Like To Thank reza_kd for help in solving the question.