Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Haieri81's blog

By Haieri81, 6 weeks ago, In English,

Tutorial 319B - Psychos in a Line

Hi everyone!


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[].


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 :

Step[A] = Kill[B];

The answer of the question would be the maximum of array Step[].

Here , You can find my implementation 82179372.

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

  • Vote: I like it
  • +2
  • Vote: I do not like it

6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Haieri81 (previous revision, new revision, compare).