Tutorial 319B - Psychos in a Line

Hi everyone!

Hint

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 Step[] and Kill[].

Solution

Now we will use a stack to update Step[] and 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 Kill[B] OR 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 Step[].

Overall complexity: O(n)

Here , You can find my implementation 82179372.

At The End, I Would Really Like To Thank Reza_kd for help in solving the question.