In Codeforces problem, Neko’s maze game, there is a grid with height 2 and width N We start in cell (1,1) and want to reach the last, the opposite corner (2, N) and we want to say if it’s possible to get there without visiting forbidden cells. Every time, from a cell, we can move to adjacent cell, one of four neighboring ones and here, there is a path, So we say yes. It doesn’t matter if there are multiple possibilities. Then there are Q queries, each query it changes the state of one cell It makes it forbidden or it allows it again, it changes its state, After each query we should say yes or no, and the constraints are here both, N width of the grid and Q the number of queries are up to 100,000. let’s analyze some example with Q queries given on the right The first cell is (1,4), we forbid it and we say yes It is possible to get from first cell to the last one, from one corner to the opposite one. Then there is cell (2,8), still the answer is yes, (2,2) still yes, (2,4) now the answer is no. Then there is (1,6) and (1,4) here, It changes the state of this single cell, It is allowed again and now there is a path from (1,1) to (2,9). So we say again, Yes. So the answers were Yes, Yes, Yes and then no, no, yes, and we continue, so it isn’t true that it just yes for some time then there is some first moment where we cannot reach the opposite corner and then for the whole time it will be no, if that was the case by the way, we could use binary search and we could then Maybe binary search over the time when there will be the first answer no On that exact time we can run DFS from first cell and we check if the last cell is reached and then if it was possible to reach it this way we can binary search in the further half Because the first no happened later, otherwise earlier but binary search here doesn’t make sense because we can get yes now yes, no again and again, so it isn’t that just prefix is yes, and then suffix is no. Okay. What can we do though? It might make sense for every column to keep track of the number of forbidden cells in that column, So when we make some cell forbidden we say counter[column]++ And if we make this allowed or empty again we say cnt[col]– and whenever some column reaches count 2 we say this column is completely blocked so we could we cannot go from one corner to the opposite one, from (1,1) to (2,n). But how to check quickly if any column is completely blocked? We shouldn’t iterate over all the counts every single time because I don’t want to get Complexity O(N*Q), this would be too slow and I would get time limit exceeded, how to handle that? Some columns will become completely blocked, then maybe one of them becomes available again, than the other, than the other and now I should say yes How to fix that ? Well I can store one extra counter for bad columns and I can increase it by one whenever some column becomes completely blocked, I could also decrease it by one and then I check if there is at least one bad column, just by comparing this variable with 0. Let’s see pseudo code or actually C++ code for that – whenever I need to change the state of some cell or col, then if it’s not forbidden, then I mark it as forbidden and increase the count of Forbidden cells in this column and if this count becomes 2, then I increase bad columns count by one. But columns is a single counter and the other two things are arrays else here in this case I should say if this was forbidden, then I mark it as forbidden equal to false and I decrease count by one- so here it would be instead – – in the opposite case and I say if count of col from two, it became one I Unlocked this column, so I decrease bad columns by by one. This is an incorrect solution though, and you can take a moment to think about it. This is incorrect because the answer is no also, if there is this situation Here, starting from the first corner no matter what we do here, We cannot reach the opposite corner We can only go from a cell to one of four adjacent cells, at most four and we cannot jump like this So this is also some other bad situation when there are two X’s that touch each other by a corner There are two questions now, Is this enough to check, so is it enough to say if there is some column that is completely blocked So 1 X above the other, 2 forbidden cells or two X’s that touch each other by a corner are some other situations when the answer will be no, And also how will we implement this? First let’s answer the first question. Let’s prove that it is in fact enough to check So consider an empty grid where there is some X and maybe some other X’s Now if There is nothing in adjacent cells, also by a corner, because we know if there is another X there we cannot reach the final destination. And this is an interesting moment where I make a mistake in my proof because two forbidden cells can be next to each other Like in the same row and this will be all OK, you will just move over them or below them So this is not what a proof should be But because of my thinking here right now It cost me wrong answer in a few minutes when I implement the solution So it’s interesting to see what a very simple mistake in your logic and thinking can cost later when implementing a problem But if there is nothing here and the next X can only be two cells to the right, So one of those cells or more to the right, then for sure we can move however we want through those cells. So no matter what X is here or below or maybe more to the right, we can still move freely here. Atleast every second column it has both empty cells and we can switch our level there and we know that when moving more to the right, there will be at least one of those next two cells It will be empty, and that’s the full proof that we can still move to the right. So it was enough to track this for the situation with 2 X that are one above the other and they touch by a corner. Then how to implement this and here let’s just jump to the code editor Let’s read the input first and then think about the details, read n and q. This is width of the grid and number of queries Maybe I will not actually use n but we’ll see, now repeat something Q times I get row and col. And now this is useful sometimes, if you operate with arrays Then by doing this you change numbering from 1 to n into 0 through n-1 indices of an array, but I think I will not actually use an array, For the convenience, I’m going to use set Set has a complexity of logarithm per operation But this is fine for small constraints in this problem, 100,000. If constraints were more like 1,000,000, 1,000,000, then I would be worried about this, here it isn’t a big deal and cells will contain currently forbidden cells, So maybe I will want to say if(cells.count(row,col}). Then this was forbidden, so make unforbidden Otherwise the opposite, maybe this will be useful My first idea for solution was about columns, for every column to check if there are two forbidden cells there, Now I realize that I also need that for kind of diagonals but I don’t need a separate counter for every diagonal, I just want to detect if there are two forbidden cells next to each other and that’s it Similarly to columns, I’m going to create a counter bad neighbors initially equal to 0 and when I detect two forbidden cells next to each other, I will increase it by one and At the end of a query I will say if(bad neighbor>=1) then print No, you cannot go get from one corner to the other, else print Yes. But what does happen here, I’m going to iterate over Neighbors of a new cell and I will do it here, I will explain why in a moment this far loop will iterate from row-1 to row+1 and the same for columns For a cell, I iterate over all the 9 cells that are neighboring with me and myself and now if If R is row and C is col, then continue, I don’t want to count myself But otherwise, I have a neighbor, maybe it is outside of the grid but then just cells will not contain it as a forbidden cell and now If(cells.count({row,col}) so if I am forbidden and I want to make it unforbidden Then what Actually, I don’t want to nine times do the same operation so I will save it So was_forbidden, whether I was forbidden is cells.count({row,col}) This would be 1 if I was forbidden, so I’m not, I’m going to say not this and now If cells.count, this new cell, a neighbor Then something happens, I am {row,col} My neighbor is (r,c) and it is forbidden, if I I was also forbidden Then this was a forbidden pair, but now I’m unmarking myself so I will say bad_neighbors–. else bad_neighbor++, I am becoming forbidden and I have a forbidden neighbor And that I hope should be it The complexity will be Q*9, at most 9 neighbors and Here just logarithmic operation to access a set I will maybe make it slightly faster and I will say if not in the grid, So 1


26 Comments

so what · January 22, 2020 at 5:15 pm

First!

M I · January 22, 2020 at 5:16 pm

Second!

Abhishek · January 22, 2020 at 5:16 pm

third

deepak singh · January 22, 2020 at 5:18 pm

Fifth😂😂

Really Man Really · January 22, 2020 at 5:29 pm

thank for sharing the videoo bruh!!!

Dastan Alybaev · January 22, 2020 at 5:32 pm

I hope there will be more tutorials from divs in future

Alberto Rosado · January 22, 2020 at 5:44 pm

(n+1)th

Quá NO · January 22, 2020 at 5:44 pm

It's a 2*n grid, so you can just iterate from column i-1 to i+1 of row (1-currentRow), (or 3-currentRow without the renumbering). Otherwise this tutorial should be easy to understand.
When I solved, I stored all the pairs of cells and then insert/delete as needed; yours only need a count/badNeighbor variable so that's much better I guess 😀

Roushan Singh · January 22, 2020 at 6:30 pm

can u please so hashcode 2020 pizza
problem

mightygamer11679 · January 22, 2020 at 6:55 pm

Hey

Harsh Patel · January 22, 2020 at 7:10 pm

Good video!

ABHIS · January 22, 2020 at 7:11 pm

Thank you for this 🙂

bahaa eldeen · January 22, 2020 at 8:13 pm

thanks please keep up those great videos

aspry · January 22, 2020 at 8:25 pm

PRGORAMMING GOD

Aadharsh Rathod · January 22, 2020 at 9:42 pm

what does this mean ? " she can only move between cells with a common side "

blah blahblah · January 22, 2020 at 9:44 pm

Nice, this one to me seemed to be more of a challenge of finding a simple way to do what you knew you had to do. I wish they had said explicitly how to evaluate a grid that is clear except for the top-left cell being lava.

Philips Koroy · January 23, 2020 at 4:45 am

Hi, I'm Akikaze. :">
Great tutorial video, I'll also include it into the editorial for references. 😉

office official · January 23, 2020 at 5:15 am

best way to show the struggle of programmer
great video brother
love from India

office official · January 23, 2020 at 5:16 am

One Question:-
Why you do not come live for a long time on errichto2

sachin pawar · January 23, 2020 at 12:51 pm

Very helpful! Thanks 😊

Bilal Tariq · January 23, 2020 at 3:10 pm

Is this optimal? The space complexity seems a bit much no?

vulence · January 23, 2020 at 3:35 pm

This is extremely helpful, especially for beginners. Keep it up!

mahin hossen · January 23, 2020 at 3:44 pm

This is really helpful, especially for beginners like me. I hope to see lot more this kind of video in near future.

Bhavansh Sthapak · January 23, 2020 at 5:49 pm

thanks for the good work as always errichto !!

aditya singh · January 23, 2020 at 7:36 pm

Hi Kamil,
Could you make videos on codechef weekly challenge

s B · January 24, 2020 at 7:17 am

Can you make a video on bitsets?

Leave a Reply

Your email address will not be published. Required fields are marked *