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

×

VISITALL - Editorial

PROBLEM LINK:

Practice
Contest

Author: Vitaliy Herasymiv
Tester: Istvan Nagy
Editorialist: Amit Pandey

DIFFICULTY:

Easy.

PREREQUISITES:

Simulation.

PROBLEM:

Given a robot and $N\times N$ grid, find any valid sequence of moves starting from $(1,1)$ such that there are no more than three consecutive turns that moved the robot in the same direction and robot covers each cell at-least once.

QUICK EXPLANATION:

Start at $(1,1)$ and at each step, consider two consecutive rows and visit in pattern $DRURDRU$(D=Down, R=Right, U=Up). Once both rows are done, jump to another pair of rows. Take care of hurdles using some specific technique. See explanation for details.

EXPLANATION:

There might be many possible solutions to the problem, lets discuss one of them. We need to derive an strategy which will be covering all of the cells using minimum number of steps and later we have to increase the steps to stop ourselves to go to forbidden cells.

Start at co-ordinate $(1,1)$, Consider two rows at a time. visit in the pattern $DRURDRU$. img

If in any row, we found a forbidden cell then it will fall in one of these two cases.

  1. We are visiting in pattern $DRURDRU$. Suppose while we are going up after going right and get to a cell which is forbidden, then we may continue in right direction and then go up(the pattern $DRUR$ becomes $DRRU..$). See the first one in the image.
  2. We get a forbidden cell while we are going into right and previous one was the up. In this case, we may go down again, go right twice and then go up($DRURDR$ becomes $DRUDRUR..$). Drawing

In second case, we are visiting a cell more than once but we are skipping a cell as well. So, number of steps will not exceed number of cells. So, if $N$ is even then in worst case we are using $O(N^2)$ number of steps. If $N$ is odd, we are using $(N-1)^{th}$ row twice so, we using $N(N+1)$ number of step in worst case.

While connecting the row pair ending we will be using at most $5$ steps while there is some forbidden cell, which can be shown using the following image. If there is no forbidden cell, we can do it in lesser number of steps.

Drawing

Maximum number of step would be $\le N(N+1) + 5(\frac{N}{2}) = N(N+\frac{7}{2})$

It is easy to see we are never taking three steps in same direction in any of the case. In first two cases, we are taking at most two steps in the same direction. While we are switching the pair of rows, we are taking three steps in one direction in the same direction and later changing the direction just after third step.

Solution:

Setter's solution can be found here
Tester's solution can be found here

This question is marked "community wiki".

asked 21 Mar '15, 19:11

amitpandeykgp's gravatar image

4★amitpandeykgp
25911522
accept rate: 0%

edited 11 Feb '16, 18:42

admin's gravatar image

0★admin ♦♦
19.8k350498541


Nice problem and nice solution:)

However, that "DIFFICULTY: Easy." sounds strange after looking at scoreboard. At the same time STRAB is marked as Easy-Medium. You think this one is easier than STRAB?

link

answered 23 Mar '15, 03:23

lebron's gravatar image

7★lebron
3.3k317
accept rate: 24%

Thanks :) Changed the difficulty to medium. The problem is definitely more difficult than the STRAB.

(23 Mar '15, 03:48) amitpandeykgp4★

I don't first case when N is 2 it will be like

1)
N N
N F
or
2)
N F
N N

N-non-forbidden cell F-forbidden cell

link

answered 24 Mar '15, 05:22

rogersands123's gravatar image

1★rogersands123
-1
accept rate: 0%

How is the solution handling the cases where it might not be possible to traverse the entire row. Something like

.#...
.#...
..#..
..#..
.....

One valid solution to this would be DDRDLDRRRURDUULURULLD. Setter's solution never returns the correct answer here. Shouldn't there be some basic graph based solution.

link

answered 28 May '15, 21:14

perseus's gravatar image

2★perseus
1
accept rate: 0%

@perseus I think you didn't read the problem statement carefully. No two forbidden cells can share a corner or side. Your test case is wrong.

link

answered 18 Jul '15, 11:14

manav2018's gravatar image

3★manav2018
1
accept rate: 0%

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:

×3,770
×171
×124
×1

question asked: 21 Mar '15, 19:11

question was seen: 1,935 times

last updated: 11 Feb '16, 18:42