L56LABY - EDITORIAL

editorial
, , , , , , ,
4

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

5

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!!

6

@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:CodeChef: Practical coding for everyone

1 Like
7

Can someone point out why I am getting wrong answer pls…
Here’s my solution

9

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…

10

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 .

11

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

12

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

2 Likes
13

Could someone point out the error[link text][1] in my code. It is giving TLE in task2.
Solution Link


[1]


  [1]: https://www.codechef.com/viewsolution/17186562
14

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

Solution Link:


[1]


  [1]: https://www.codechef.com/viewsolution/17193387
15

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

16

I have dropped a message, will be visible soon.

1 Like
17

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.

18

Thanx mate!!!

19

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.

20

Thanx mate!!

21

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

22

Avoid repeated processing of same position.

23

Editorialist’s solution is commented.

24

Check for i>0 before accessing its neighbours.