You are not logged in. Please login at www.codechef.com to post your questions!

×

CT2 - Editorial

PROBLEM LINK:

Practice

Contest

Author: D. Vishnu Vardhan reddy

Tester: D. Vishnu Vardhan reddy

Editorialist: D. Vishnu Vardhan reddy

DIFFICULTY:

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.

asked 13 Sep, 17:48

dvvr's gravatar image

2★dvvr
112
accept rate: 0%

edited 13 Sep, 17:49


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.

link

answered 13 Sep, 20:11

joffan's gravatar image

5★joffan
4186
accept rate: 9%

edited 13 Sep, 21:36

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.

(13 Sep, 21:33) dvvr2★

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.

(13 Sep, 21:48) joffan5★

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

(13 Sep, 22:12) dvvr2★

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.

(13 Sep, 22:17) joffan5★

modified the question

(14 Sep, 00:10) dvvr2★

feel free to accept my answer as useful if you find it so $\checkmark$ :-)

(14 Sep, 00:16) joffan5★
showing 5 of 6 show all
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,010
×1,514
×6

question asked: 13 Sep, 17:48

question was seen: 108 times

last updated: 13 Sep, 21:41