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

×

SNAKY - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

For each cell (r, c) of the grid we can compute the time T[r][c] when the snake makes this cell free. It means that for the next T[r][c]-1 moves this cell will be occupied by the snake and at the move T[r][c] tail will leave it (this cell can be immediately occupied by the head but we don't worry about that). For this just simply model the snake movements that given in the input and mark k-th cell in this sequence by the number k. (First cell is occupied by the tail and we marked it by 1 and really snake will leave it just in one move. Second cell will be free after two moves and so on). Since N, M <= 1000 we can do this using usual two-dimensional array. After that, model the movement of the snake head. If at k-th step the head visits the cell (r, c) then it collides with its body if and only if k < T[r][c]. Indeed, if k < T[r][c] then by definition of T[r][c] it means that the snake body still occupies this cell and collision happens otherwise all is fine. So if at some moment we obtain this inequality then we should output "BODY" and k-1, otherwise snake will collide with the wall. So the overall complexity is O(M N + L + max{M, N}) per test case (we need to clean corresponding two-dimensional array before treatment of the snake movement hence we have M N term, L corresponds to the analyzing of the snake movement and max{M, N} corresponds to the movement of the head.)

SETTER'S SOLUTION

Can be found here.

TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 26 Nov '12, 18:43

admin's gravatar image

0★admin ♦♦
19.8k350498541
accept rate: 35%

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,684
×3,767
×5
×3

question asked: 26 Nov '12, 18:43

question was seen: 1,650 times

last updated: 26 Nov '12, 18:43