What's up there?
And here you're on a little PDA in this video, we are continuing serving with forces around 614.
We have problem E but before getting on to that, I have a really important call to action to you because
my time and energy are now kind of limited because I'm working on a big project.
I really need to know what kind of videos do you enjoy the most?
Is it called forces roles?
Is it coding interview questions?
Make sure you farms up this video.
You subscribe to the channel.
But most importantly, make sure your comment and tell me your favorite types of videos, because I
really need to know where to put my most effort.
Should I do more coding interview questions?
All right, I'll do it.
Today, the mod squad forces problems.
Outsourcing rounds.
Be live rounds.
All your ideas are super important.
All your feedback is necessary.
So make sure to comment again.
Make sure you like these videos if you really enjoy them and you want me to continue to do them and
make sure you subscribe Talgo P.D.A.
Because more awesome content is always is always flowing on this channel.
So that was my last one.
Again, if you want to stop this kind of problems daily, make sure you go and join the Facebook mastermind
group right now.
You'll make a lot of friends and we post almost daily coding interview questions and competitive programming
problems.
And we basically share some experience together.
And you will be able to ask me questions directly or any other awesome guys on that change in this game.
So I say, OK, guys, we're back again.
So let's see what it's about.
Basically, you are given four integers and am l and are and they are quite large.
And the problem asks you this.
You have to count how many grids we have and rows and columns are there such that if you start off with
that grid.
You can make all cells equal in value, and the first requirement is that each.
Value of some sell is between L and ah.
So initially, these values are all in the range.
L.
R.
And the second one is that you can make all sales equal.
Right.
So let's say something like equal says.
And for this you have two types of operations.
The first one is that you choose two adjacent cells like these two.
Or maybe these two.
And you increase their values by one.
And the second one is that you choose only one sale.
And you increase that sales value by two types.
How many different setups are there such that if you start from that setup, you can make all the values
equal?
These kind of statements, we have games and values and all that stuff.
Let's simplify it.
Let's let's think about some property, some mathematical property that this grid really has to satisfy.
Basically, when I take a cell and I increase its value by two, it's FERRETI is going to be the same.
So it's quite clear to me that a valid grid is agreed in which all the cells have the same parity,
because if they do, I can apply.
The second type of operation.
Any number of times, and I'm going to make all the services.
So if I if I only can perform the second type of operation.
The problem is quite simple because I have the range elde.
And ah.
Right.
And it's super trivial to count how many even and how many all the numbers are in this range.
So let's do something like this.
Let's say X, right.
Is the number of odd numbers in this range.
And let's say why is the number of even numbers in this range?
Of course, the the formula is going to be X at power and crust and plus Y at power and crust.
The real question here is, how does the first type of operation really make this problem harder?
My intuition says that it's all of game.
It's all a game of parities here.
So I kind of have to make sure that I have the right parities in the right number of times, and that's
actually it.
So I want to restate a little bit the problem, and I want to think about it like this.
Let's take the first of the first type of operation.
Right.
So first operation.
What are the possible scenarios?
Well, some scenario is that when I choose to adjacent cells, both of them are evil.
So to take two even.
Well, I increased both of them, we've won.
I'm going to have to oord instead of two even right now.
Second scenario is if both of them are odd.
Of course, same spiel.
They become both even.
But if see.
One is Ford.
And one is even right.
So one old and one even when I increase both of them by one, they are basically swapping their Paradies.
So it's still the same.
It's still one old and one even, isn't it?
So the real thing here is.
When I'm gonna apply the first operation, I'm just going to change the counter of all the numbers and
even numbers in this grid and nothing else.
And when I reach to the point that all the cells are even or all the Serbs are odd, I can apply the
second operation.
How many times I need to.
And I'm gonna make all the cells in integrate equal in value.
So it's all a matter of in this grid, let's say a cells initially are owed in value and B of them are
even.
Right.
What do I do by applying the first operation.
Well in scenario A.
I increase a.
And decrease B.
In Scenario B.
It's the reverse.
Decrease a Viju and increase.
B.
In the scenario, they are exactly the same.
Right, because they swab their parities.
So basically.
All of those greed's those and crossed em cells they all reduce to how many odd and how many even values
are in the grid.
So I have to count how many configurations, how many pairs of this.
A and B, are there such that by applying these two operations, I can either make a equal to zero and
be equal to N crust M.
So basically, all the cells have became Evelyn.
And then I can apply the second operation.
How many times I need to.
And all the cells are going to be equal in value.
Or, of course, they could be and crossed M aude values and zero even value.
How many types of pairs like this are there and for each pair.
Of course.
How many greed's are there that are equivalent to that pair?
So if both of them are.
Audie, initially, there is no way you can make one of them zero.
Right.
So basically, this problem reduces to how many pairs in the form a M.B.
Are there such that.
A or B is even.
So at least one of them is even.
Maybe both.
But at least one of them is evil.
And the second one is that A plus B.
So the total number of cells has to be equal to N.
Crust.
And that's it.
And for each bird like this, we are going to count how many greed's are there which are equivalent
to despair.
All right.
So basically because we are dependent of FERRETI and some, we are going to a field there.
The answer by the parity of and crust.
So let's make, first of all, two scenarios.
The first one is when an crust M is odd.
If this is odd.
Remember that A Class B is M crust M.
So it is going to be odd.
Right.
So this is odd.
This means that we are going to have Aude and one evil.
Just cool, because remember, we need to have at least one even, right?
So it's not that important.
Let's say A is Khaled.
So, uh, Bay is even right.
So if A is owed, basically the number of owed sales is owed and the number of evil itself is evil.
What does this mean?
Well, if the number of even sales is even, you basically have to go through all of this, even calendars
and see how many possibilities can we have.
So let's see if we have zero sales that are even that's an crossed M or the sales.
So remember, the number of odd sales was X or Y?
I don't even know.
Let's say it was Y.
So if it was Y, we will have Y at power and crossed M.
Right.
That if we have two sales that are even.
What does it mean.
It means that we have to choose what are those sales.
Right.
So from all the M crossed M sales big two of them which are going to be even.
Multiply this by the number of possibilities to give them value such that they are even.
So which is basically X OPOWER two, right?
Not such a big deal that if you have four.
It's exactly the same thing.
We have an arrest.
Sallas, from which we have to choose four of them, which are going to be even, of course, in how
many ways can do that?
Exit bar four, right?
But let's not forget about the odd sense, because here, if you have zero, even we have an crust m
odd.
So this is going to be multiplied.
Yeah, I know.
That's cool.
This is the problem here, because if you have to even cells.
That means we have N crust M minus two or the cells.
Right.
So if we have that many odd cells that means we will multiply this by Y power n crust M minus two.
That same principle.
And crust M minus four.
And so on and so forth, until eventually we have some let's say if and Crust M is owed.
We will have an.
Crust.
M minus one.
Even cells.
Which means its combinations of and crust.
M.
Taken of an crust.
M minus swan.
And here I have X.
At what power?
Of course.
At power and crust.
M minus one.
And the Y.
Of course.
At power.
What.
So.
For this case, when an crossed M is owed, so A plus B is owed, so A is owed and B is even, for example,
we got to this.
And does this sum look any familiar to you?
Because it might if it didn't miss your math classes, you would recognize that this is Newton's formula
or bilum.
I don't even know why it's called, but we got a formula for this and it's still based on combinations,
so.
And yeah, if you choose a, let's say, to be even and B, to be Aude, it's exactly the same formula.
It's exactly Newton's formula.
But it's going to be like instead of Y, you're gonna have X and instead of X are going to have Y.
Right.
And if you know Newton's formula, that is based on combinations and you can compute that in Bigo of
Log, which is super cool because basically we have solved the case in which N crust M is odd.
Now let's take the second scenario in which and crust Emmies even.
This means that A Class B.
Is even right.
So A plus B is even waterways.
There it is here.
Both of them are old or both of them are either.
Right.
So let's say.
A is even right.
And B is evil.
Let's say we choose A and we go for all the possible even values.
So if I choose to have zero evil values, that means I ain't going to have any crust M or the cells.
So this is again for the old one.
I don't know what was, let's say y whatever and crust am right then let's say we choose to even sense.
That means.
Combinations of and crust am taken of two multiplied by X at power, two multiplied by Y power and crust
M minus two.
Right.
Or for exactly the same and so on and so forth.
And because and crossed Ms.
Even the last step is going to be.
Also interesting.
Right.
This is, of course, you have to add them together.
And this is, of course, Newton's formula.
Which is based on combinations and can be computed in Bigo Block.
Same spiel.
Of course, you're going to take the second scenario in which you have A, ORed and B even.
And again, let's say we raise this really quick.
All right.
So A is old and B is.
All right.
A and B, both of them are on.
Well, both of them are old, again, big.
All the scenarios one.
And A is one combinations of and crossed em.
They can have one.
Brust X crossed Y at Bauer and crossed M minus one, and that's it.
Let's take free.
Combinations of and crossed em, they can go free, then X at power free, then Y power and crust M
minus three.
And we go so on and so forth.
And the last step is of course and or crossed M minus one in which the formula.
So my point is you basically have the two main scenarios in which and cross them is odd or and cross
them is even.
And for each of these scenarios you have two sub scenarios when you choose if A is order B's evil or
whatever.
But for each of these total sub scenarios, you have the Newton's formula when I have some Newton form
in.
All right.
Which is going to involve some combination, let's say a combination of.
And you can have K.
Right.
This is basically.
Turrill crossed, divided by Kaif, factorial crossed and minus K factorial.
Right.
So one possible solution to this is that you pre compute this Victorias.
All right.
Let's say you compute some vector.
Let's say you have a vector of INTs factorial of Idaho and Max.
Right.
Where?
Is equal to.
I factorial, of course, modulo mode, right, because factories can get really big.
So where do computers kind of vector linearly?
You break computed modular mode when you have this kind of formula.
Basically, it reduces to combinations of N taken of K, it reduces to.
All of it divided by F of K crossed F of and minus K.
And of course, you pre computer this, but you precocity did more jula or something.
So.
As you might know when you have this therms.
Modulo something, and you need to make the division of them and you still want the division to not
be a float or a double.
You wanted module or something, you will apply the Fermat's theorem.
And that involves, of course, the logarithmic power algorithm and you will have in Bego.
Of log of n all the formulas that you.
Right.
I don't wanna get into super detail of these mathematical formulas, because that's not the point of
these tutorials.
But we are going to write the code for this problem in the next tutorial so I can take you there.