You basically are given a grid of N Rose and M columns, 1000 rows and 1000 columns at most.
And you are given some test cases.
And what happens if this grid is that on each new second or each new iteration?
They call them iterations.
We can call them seconds or iterations.
It's really all call on each of these.
Basically, you have two possible scenarios.
You have to look at some cell.
And for each and every cell, if there is at least one neighboring cell which has the same color as
this cell.
Both of them are going to switch colors.
Right.
And yeah, if for that cell, the reason any other cell neighboring which has the same color, it is
going to keep the color.
Right.
So it will keep its color.
So what happens here is that I have free integers and empty.
I have the grid zero and one.
And I have like tell me the value in cell.
I own a row I and column G on moment of time.
And I have to quickly answer these queries.
All right.
So what I thought about a problem and I've read the statement, I was like him.
B, it could be as great as 10 at power 18.
I mean, Tennet Power 18 is a lot.
I'm definitely not going to simulate or do these iterations by hand, like take each and every iteration
and swap the colors, take iterations of the colors and so on and so forth.
So one golden trick that I'm going to share with you right now on this livestream is that when you have
these that are that great.
You basically need to find a cycle to find the pattern, right?
So when I thought about a problem, I was immediately like, all right.
So there's got to be a pattern.
Like, if I take, let's say, 10 at power, 18 iterations, I'm gonna figure out that for this grid
or at least for some cell in this grid.
The the sequences like the colors, the way the way it changes its color are going to be something.
Repeating something that's really beautiful.
Like you're gonna see a pattern.
You're gonna see a formula or something like that, you know.
So, yeah, that's what I thought about.
So what I did, Drew, what I need to do right now is to figure out for each and every cell.
What is the pattern like?
I have to find that number X, which is less or equal than P, such that I know that each X iterations
that cell comes from the beginning state.
All right.
So some cell, right?
That's not a cell.
That's a cell on a row.
Eye and column J.
Right.
Basically goes through some changes right.
On the first iteration, eight.
Maybe it was black.
Now it's white or it's still black.
Who knows?
Then second iteration has a color for the iteration has a color and so on and so forth.
Right.
What I figured out then I was super sure about it is that it's gonna repeat the cycle like first iteration
to second or second one for on and so on and so forth.
And iteration number X, it's here.
And on iteration number X plus one, it gets to a point where it's gonna repeat all over again the Pathum.
Iterations X, plus one, iteration X, iterations X, plus one interation and so on and so forth.
So I really need to think about when does the sale going to do this kind of thing?
So.
Let's make some observations.
The whole problem here is just about making observations.
So on these kind of problems, you really need your pen and paper or Ben and graphic table like I have
here, tablet.
And you should make your observations, man.
So let's see, what observations did I do?
First observation was that if I have a cell.
Let's say this is a black cell.
If it has some neighboring cell, which is also black.
What happens after 183?
Both of them change.
Both of them are white.
What happens after another iteration?
Both of them black again after another iteration.
White again, black again, white again.
Black again.
Right.
So basically what happens here is that the second iteration I have found the site.
Am I right?
As simple as that.
So the problem seems really simple right now.
I was thinking about him.
All right.
So I got to find the cycle.
But on these cells, which have already a neighbor of the same color as that cell, that cycle is always
equal.
It has left to right.
And yeah, that's right.
The only problem is with the cells.
Which let's say are black and all the neighbors are white.
Can that mean right?
Oh, it's the opposite.
Like, you know, that meme, right, of the white girl and only black guys.
Yeah.
So in this cell.
She's black and all neighbors are white.
Now, this is a problem.
On these kinds of cell, which are, let's say, a type number one type number one cells which have
at least one, just one, we need just one, at least one neighbor of the same color as them.
The cycle is two.
On these cells, which have zero neighbors as the same as of the same color of them, the first thing
that I wanted to notice I supposed I was tempted to say is that this is always going to be black, but
that's stupid.
And the counter example is super simple.
If I had here another cell, which is white.
After one iteration, I need only one iteration.
And this one's guess what?
Ah, no black.
Both of them.
And because these cells are now black.
Guess what?
Now these two cells are both black.
So after one iteration, what happens is that these two cells are, again, both white.
Right.
These are both white.
These remain.
These are both white.
This is also white.
So, yeah, yeah, yeah.
So basically, these free are all whites and these remain white.
So all the cells are now whites.
Right.
So now everybody's gonna be black and then white and black and white and so on and so forth.
So the fingers when a cell is of the first type, the cycle is to problem is over.
We just check if T is even or odd and if T is even, you are going to print the color that cell already
has.
As simple as that, if T is owed, you are going to print the other color.
But for these cells, which don't start as type one cells, let's call them type two, a type two cell.
As we said, has only different neighbors.
We have to see if at some moment of time it turns into work.
Type one cell.
And after he does, its cycle is two, because cells are initially type one and they will remain type
one and just cycle cycle cycle.
But some of the type two cells are going to become type one.
And then also remain type one.
So you can convert a type one into a type A, type two into a type one.
But you can't convert a type one into type two.
That's it.
So all I need to do now.
But everything that I need to do is figure out for each cell of type two.
At what moment of time?
If it does, it gets to a type one cell.
That was it.
And I needed one more example to figure out this, too.
And the problem is this is the power of drawing guys.
This is the power of drawing examples.
Let's take a look again at this example right back up on here.
I had this cell.
I don't even know who it was anyways.
So basically what they had here is a black cell.
If only white neighbors.
Right.
So it was a type to sell.
It was a type two cell, type two cell, right?
Bam, bam, bam, bam end.
And very important.
And.
Because I had here another Whitesell.
This took only one iteration.
Be converted into a type one set.
But if I didn't have it, if I didn't have it.
So, yeah, let's say the greed was indeed full of whites.
Pool of whites, pool of whites.
If it was full of white.
How many iterations do I need in order to turn this into
Whitesell?
Into a type one cell.
Sorry.
Well, I won't be able ever to do that because this is going to be a type on some sort of weather when
it has at least one neighbor.
Which is different.
Not which is the same.
Just the same area, which is the same, but these neighbors.
Wait, wait a minute.
Oh, no, I'm sorry or sorry about or sorry about that.
Yeah.
This takes also one iteration.
No, no, no, sorry about that.
This also takes one iteration because they have this white.
White, right.
So one iteration, no mistake.
Two iterations, one plus one.
All right.
So.
So after one iterations, these cells become Blagg and after another.
Okay, so it takes one iteration for the cell to get off type two.
All right, sorry.
Yeah, yeah.
OK, so I've expressed myself correctly in the first place.
So it takes one iteration for the cell not to change the color, but to be but to change typewrite like
to become type one.
But if this didn't happen and let's say I didn't have this whites, let's say this was blacks, these
were blacks so black that.
Black, black now is the real problem, because on this type of grid, every cell but each and every
cell is of type two because for each and every cell, I don't have any neighbor of the same color.
So each cell in this grid is of type two.
Well, in this kind of scenario.
Guess what?
Nothing happens.
Nothing really happens.
You can do an infinite number of iterations.
The grid remains the same.
So the thing was that if maybe I had here, who knows, some black if these two were black.
At least these two cells were of type one.
So after one iteration, what happens is that they become white.
So after one more iteration, I have this white, white, white, white.
This become like.
So after two iterations.
In this example, because I had peer.
One cell of type one and hear one cell of type one, because these two cells were of type one.
I managed in two iterations to extend myself until I got to the cell.
So basically what I'm trying to say, and it's not that complicated, is that if you have somewhere
but somewhere two cells of type one.
After one iteration, they are going to expand and they are going to make those neighbors.
Which were all the neighbors, actually?
Yeah.
All right.
So if you have two sets of type, one after one iteration, each and every of their neighbors are going
to be of type one after one more iteration.
Each and every of their neighbors are going to be of type one.
And two have seen exactly why.
Because when they change color immediately, they are equal with those neighbors.
They weren't equal with.
And then those neighbors becomes of type one because now they have at least one neighbor equal to them.
Do one more reiterations.
All of this type once, bam, all the neighbors are of type one.
So if we pick a cell I n g.
We need to know.
The minimum distance.
Between the sale, I g-.
And type one said.
If we know this minimum distance, which we can get, we have a lead algorithm or a beer fest or however
we want to call it, if we know this minimum distance.
We know after how many iterations that cell becomes of type one.
And then the cycle is, too.
So let's do a small recap here and end the problem.
A query cell is already of type one.
What happens?
We just have to check.
Is the if he is owed.
Or is even because the cycle has left, too.
And if it is even.
The answer is going to be the current caller.
So the initial color this cell has, if it's odd, the opposite color.
Case number two, if I j.
The selling of Prarie is of type two, I need to know when does it convert to a type one?
Because when it is of type two, nothing happens.
It's gonna it's going to keep its collar.
Right.
So I have to let's say I have these.
The minimum distance.
We are going to compute these distances, DFS.
We can start a beer fest with multiple sources from all that's type one sales and let's say we store
indeed the minimum distance to a good cell.
Right, to to a cell.
There's going to change.
Right.
Which is a type one.
And if we know D.
D, what happens is that either T is less or equal, then D.
Which means current color, because it didn't even start to be a type to type one cell.
So it's change its state, so it keeps the current color or if T is greater than the.
This means it has changed.
Each is type.
Right.
So I have to take a look at T minus the because it took D iterations to change its type.
And then for the next T minus the iterations, it just changes its color.
So I now have to look at T minus the.
And see whether this is odd or even.
And if T minus the is odd.
I have the opposite color.
And if T minus the is even.
I have the same color.
And that's it guys.
Type one type to be affairs.
No.
The distance.
And then you basically have six cases or something.