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

×

L56LABY - EDITORIAL

4
1

PROBLEM LINK:

Practice
Contest

Setter: Kirill Gulin
Tester: Misha Chorniy
Editorialist: Taranpreet Singh

DIFFICULTY:

Simple

PREREQUISITES:

BFS, Max-heap/Priority Queue, Greedy

PROBLEM:

Given a $N*M$ grid with certain forbidden cells (represented by -1) where Chef cannot enter, Empty cells (represented by 0) where chef can enter and exit, and Escape Cells (represented by x>0) using which Chef can escape from grid if he can reach escape cell from any cell within x seconds, i.e. the distance from escape cell must be at most x.
Chef can only move from one cell to another if they share an edge.

Find out from which Non-Forbidden cells from where the chef escape and print it in specified format.

STRATEGY TO SOLVE

A Tempting greedy but Wrong solution

The intuitive idea to solve this problem is For every node with value Greater than 0, run a BFS, mark the node as visited and terminating BFS when distance become greater than x. This strategy fail for following test case:

1
5 5
0 0 0 0 0
0 0 0 0 0
0 0 0 2 4
0 0 0 0 0
0 0 0 0 0

In this case, if we visit the position with value 2 first, we will either have to reprocess the same position with value 3 (while processing 4), thus getting either TLE or WA, depending upon implementation.

Why above solution doesn't work

Suppose we process a position with lower grid value first. Then later, it might happen, that we visit the same node with higher value of x. Here, if we choose to process it again, we will get TLE in 2nd subtask, because our solution become $O((N*M)^2)$ in worst case. If we choose not to process this vertex again, there is a the possibility that a node earlier not reachable with initial grid value, now become reachable with higher value of x, thus giving us WA.

This gives shape to the ideal strategy to get the correct solution.

Correct Solution:

The element with maximum value should be processed first of all.

Now, this way, whenever we reach a position already visited, we can simply ignore it because we have already processed this position with a higher value of x, Thus, keeping Time Complexity to $O(N*M*log(N*M))$ (Log factor added for insert and delete operations of Max-heap.

Our final solution become to maintain a max-heap, running a BFS. Due care must be taken to ensure that a position does not get inserted into heap twice, to keep our solution within time limit.

Tester's implementation: An $O(N*M + maxA)$ spproach.

With the same idea, Tester made a vector V array of size $max(A)$ , storing all the position $(i,j)$ in $V[grid[i][j]]$ for $grid[i][j]>0$. This way, we run a loop from maxA to 0, and for each position in $V[x]$, we add all its neighbours which are not already processed into $V[x-1]$ and also mark them as visited.

This way, we save the Log factor associated with insertion in max-heap, thus, getting $O(N*M+maxA)$ runtime.

Complexity:
Time Complexity is $O(N*M+maxA)$ or $O(M*N*log(M*N))$, depending upon implementation.

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter's solution
Tester's solution
Editorialist's solution

This question is marked "community wiki".

asked 22 Jan '18, 23:33

taran_1407's gravatar image

6★taran_1407
3.9k2791
accept rate: 22%

edited 27 Jan '18, 23:51

admin's gravatar image

0★admin ♦♦
19.7k350498541


@vivek 3 node (0,1) is processed that gives value 2 to (1,1) then it is processed which gives value 1 to (2,1). now node (3,2) is processed which gives value 1 to (3,1) which when processed marks (4,1) as Y. there might be insertions needed while processing any node that's why we use a priority queue instead of a static array to get nmlog(nm) complexity. My sol:https://www.codechef.com/viewsolution/17173110

link

answered 27 Jan '18, 23:52

praveenkumar12's gravatar image

5★praveenkumar12
29819
accept rate: 8%

Thanx mate!!!

(27 Jan '18, 23:53) vivek_19982996★

after reading the editorial and seeing tester's solution i finally got ac , so thought this might help i've heavily commented the code inorder to understand better. Anyone not getting anystep of tester's solution can see my code here

link
This answer is marked "community wiki".

answered 28 Jan '18, 17:56

shahianshu's gravatar image

5★shahianshu
12
accept rate: 0%

Editorialist's solution is commented.

(28 Jan '18, 19:50) taran_14076★

solution are not visible @admin

link

answered 27 Jan '18, 23:18

dushyant7917's gravatar image

5★dushyant7917
716
accept rate: 0%

1

I have dropped a message, will be visible soon.

(27 Jan '18, 23:21) taran_14076★

I used the same approach as the one described in the editorial but getting wrong answer. Can someone help in finding the error. Thanks in advance.

Link to solution

link

answered 27 Jan '18, 23:39

sai_rathan's gravatar image

4★sai_rathan
1043
accept rate: 0%

Refer the TC mentioned above, run it with your solution, and pay special attention to position (3,1).

Don't mark nodes visited as you input them.

(27 Jan '18, 23:57) taran_14076★

Thanks mate. Understood my mistake. Initially I tried marking visited after processing but it gave TLE because of multiple entries in max heap. Thanks

(28 Jan '18, 00:50) sai_rathan4★

I couldn't understand this part "Now, this way, whenever we reach a position already visited, we can simply ignore it because we have already processed this position with a higher value of x",

Lets say for this grid:

-1 3 -1 -1

-1 0 -1 -1

-1 0 -1 -1

-1 0 2 -1

-1 0 -1 -1

How does it works in this test case.3 would reach till 2nd last row,then when bfs strts from 2 it'll see that (3,1) is visited and stops ,so (4,1) never got included.

I know i am missing something.

Thank you!!

link

answered 27 Jan '18, 23:42

vivek_1998299's gravatar image

6★vivek_1998299
1.6k29
accept rate: 23%

The use of max-heap process the positions in following order (i,j,x).

(2,1,3)

(4,3,2)

(2,2,2)

(2,4,1)

(2,3,1).

Note that actual order among tuples with same values of x may vary from above mentioned, but doesn't affect our solution.

(27 Jan '18, 23:52) taran_14076★

Thanx mate!!

(28 Jan '18, 00:23) vivek_19982996★

Can someone point out why I am getting wrong answer pls...
Here's my solution

link

answered 28 Jan '18, 01:49

dishant_18's gravatar image

5★dishant_18
61419
accept rate: 12%

I tried to solve this question by recursion but i am getting TLE. Can anybody help me to optimise this solution.. thanks in advance. solution link link text

link

answered 28 Jan '18, 01:50

deepak_097's gravatar image

4★deepak_097
933
accept rate: 0%

I constructed a binary maze matrix and applied bfs on it..then I saved all those i,j which were >0 and than ran a source to destination bfs for every i,j and the saved i,j(obviously on those i,j which equal 0). I should have sorted the saved i,j according to max value..would have got a right answer..

link

answered 28 Jan '18, 03:51

tanmaym96's gravatar image

2★tanmaym96
1
accept rate: 0%

My solution gives WA even for the 1st subtask . Can anyone provide me a test case ?

Link .

I store the position of each element with value > 0 and then do a dfs .

link

answered 28 Jan '18, 12:42

hackslash_123's gravatar image

4★hackslash_123
111
accept rate: 0%

can someone give some tricky test cases so that it can help everyone who got wrong. thanks in advance

link
This answer is marked "community wiki".

answered 28 Jan '18, 12:55

kasa's gravatar image

4★kasa
1
accept rate: 0%

Could someone point out the errorlink text in my code. It is giving TLE in task2. Solution Link Code

link

answered 28 Jan '18, 19:35

barindervir's gravatar image

1★barindervir
1
accept rate: 0%

Avoid repeated processing of same position.

(28 Jan '18, 19:49) taran_14076★

Used the same approach as of tester but the code is throwing Segmentation fault. Unable to debug the cause. Can anyone help?

Solution Link: Code

link

answered 29 Jan '18, 20:46

fukra's gravatar image

3★fukra
261
accept rate: 33%

Check for i>0 before accessing its neighbours.

(30 Jan '18, 10:34) taran_14076★

Figured it out last night. Still thank you. Silly mistake!

(31 Jan '18, 13:28) fukra3★

https://ideone.com/OLCxhx

please someone find error in my code i ran few test cases but that are fine :-(

link

answered 31 Jan '18, 02:42

jayantjain001's gravatar image

3★jayantjain001
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:

×15,630
×3,741
×997
×649
×505
×53
×42
×24

question asked: 22 Jan '18, 23:33

question was seen: 4,160 times

last updated: 31 Jan '18, 13:28