# CT2 - Editorial

Practice

Contest

Author: D. Vishnu Vardhan reddy

Tester: D. Vishnu Vardhan reddy

Editorialist: D. Vishnu Vardhan reddy

CAKEWALK

### PROBLEM:

Given zombies walking in left or right direction indicated by -1 and +1, find the last zombie to die if they walk towards the left and right edges respectively. When a left zombie meets with a right zombie, they change their directions only.

### EXPLANATION:

Count the number of zombies walking towards the left and let it be count_left. N- count_left gives the number of zombies walking towards right, that is count_right.
Whenever the zombies reach the ends, theyâ€™ll die. Counting the number of left and right zombies helps to eliminate the one on the left and one on the right simultaneously. Subtracting the total number of zombies by the larger count value gives the index of the required zombie.

If count_left < count_right , N+1 -count_right gives the index of the last zombie to die.

Else , N+1 -count_left gives the index of last zombie to die.

### AUTHORâ€™S AND TESTERâ€™S SOLUTIONS:

Authorâ€™s solution can be found here.

1 Like

I thought briefly about modelling this, but coded it just using the count of â€ś-1â€ť zombies, which agreed with the test cases.

However I was curious about the state of the tunnel is when there are multiple consecutive zombies heading one way after the lead zombie collides. Using the given test case of

`````` 1  1 -1  1  1  1 -1  1
``````

at time t=0, I made a little illustration using > for 1 and < for -1 with `X` indicating a collision in progress:

``````> > < > > > < >
. X > . > X > .
< . > > < > > >
. . . X > . > >
. . < . > > . >
. < . . . > > .
< . . . . . > >
. . . . . . . >

``````

(of course some collisions happen on the half-second, not shown). Whatâ€™s striking here is that the last zombie to die is at the low end or high end depending on the original walking directions at the other end of the tunnel.

This should mean that the answer for

`````` -1  1  1  1  1  1  1 -1
``````

should be 2, since the last zombie to die comes out of the low end:

``````< > > > > > > <
. . > > > > X >
. . . > > X > >
. . . . X > > >
. . . < . > > >
. . < . . . > >
. < . . . . . >
< . . . . . . .

``````

I recoded my answer to take this into account properly and got a â€śWrong Answerâ€ť response. This suggests there may be an error in the marking.

Actually at first I had written code with the same exact algorithm as you did. This was a question given to me to solve in one of my interviews. The interviewer told me that he didnâ€™t mention time so he told me to move the zombies after there are no collisions at all. Actually saying the question needs a clarity about the time.If possible just help me to add a sentence or two, to make the question more reasonable. As people wonâ€™t understand it untill they see the sample input-output. Thank you in advance.

You can perhaps rescue the original solution by claiming that zombies will run immediately to the end of the tunnel once they can see it.

Didnâ€™t get you. You mean - I should include a line like -â€śZombies will run immediately to the end of the tunnelâ€ť in the question

I havenâ€™t yet satisfied myself that it is always correct, but yes, â€śZombies will run immediately to the end of the tunnel once they can see itâ€ť seems to fix things up in a lot of cases. It makes the question a little bit harder to read perhaps. Maybe thereâ€™s another way.

modified the question

feel free to accept my answer as useful if you find it so \checkmark