Basically, we are given and lamps.
Yeah, that's cool.
We are given an lamps, right?
Each lamp is either turned on or turned off.
Yeah.
Like everybody in quarantine.
You're either turned on or turned off.
And basically, when you are turned off, you are a zero.
So we are basically given a binary string in which the zeros means that the lamp is turned off.
And one means that the lamp is turned on.
Now, what we have to do here is that we are also given a positive integer key, which denotes some
period.
And what does this period actually tells us?
It tells us that we have moves.
And in one move, I get to choose one lamp and switch it if it is zero or turned off.
I get to turn it on.
It's super amazing to turn on lamps, right?
If it's turned on, you gotta turn it off.
It's not that amazing to turn off something.
But yeah, eventually we'll have to do that too.
So we are basically given this string of lamps and of zeros and ones.
And we have to make sure that after we perform other little moves as possible or as few moves as possible.
I think that's more correct.
We have to make sure that each two adjacent ones.
Right.
So each and every pair of two adjacent ones.
Right.
Consecutive ones are that distance.
Exactly.
K.
And that's it.
You have to do that with us.
Few we have as few operations as possible.
And of course we don't have any constraints saying guys that print minus one, if this is not possible
because it's quite always possible.
Right.
Like yeah, you can do whatever moves you like.
And even in the worst case scenario, you can make all the lamps turned off.
Everybody zero.
So you don't have someone.
Right.
I have read the statement.
Right.
What's in my mind?
Get ready because you will come and you will basically be in my mind right now.
You will getting my right.
So I see the string.
Right.
And I'm like, hmm.
Okay, let's take some example.
Let's say I took example the first one.
Right, which is zero one free zeros.
So I say zero one three zeros.
Then what I have left.
Let's see.
Zero one three zero one zero one zero.
Okay, one zero one zero.
Let's switch on full screen.
So I have this string, right?
And I'm thinking about this each and every.
Two consecutive once.
Have to be on distance.
Exactly.
Kate.
This means that one information that I'm going to need for sure is where is the first one placed?
Right.
That's an important thing, because if the length of the string is at.
I am basically going to fix.
The position of the first Lemn, let's say, on position.
I, I have the first ever turned on Lemp.
This is a one.
All of these are zeroes.
Everything's quite clear now, right?
What I am interested in right now is, is there going to be any other lamp?
Because if it is, the distance between I and the next lamp is exactly key.
So the next lamp is exactly in position.
I.
That makes sense.
Right.
That's basic maths.
So if let's say I want to have another lamp.
It's one position.
I plaskett.
All of this are zeros.
Next, do I want another lamp?
Let's say I do.
All right, cool.
Everybody says zero.
And then the Ford lamp is on position.
I plus two crossed key because I have to keep this distance.
Exactly.
Kay.
Everybody zero.
This is a one.
And so on and so forth.
When do I stop?
Well, it depends on how many lamps I need, right?
Let's say in this example, I choose let's not have any other turned on lamps.
All right, cool.
Everybody says you're.
So I have only free value equal to one.
And they are in positions.
I Plastiki I plus two crossed key.
So I was thinking about.
All right.
First thing I need to know is I.
Right, which is the position of the first.
Right.
The first turned or lamb or the first one.
Then if I knew how many lamps I'm going to have.
Let's give it a name.
Let's say.
I don't know.
Gee.
All right.
Let it be G if I know G.
Which is how.
How many turn Don lamps?
I basically know the string.
So does the first thing that comes to my mind.
All right.
I don't have a string of one million things, which is a lot.
Everybody's a zero or a one.
All I'm interested in is where is the forest land?
How many lamps are there?
That's it.
If I know this, I know the string.
Right?
If I know the string, I compare the string with the old string and I see how many positions are different.
So the problem now is equivalent to the following one.
They have to choose the optimal pair.
I.
The difference between let's call this as prime as prime is the string that is obtained is generated
by this I n g.
The difference between subprime and S is is is minimal.
Exactly.
I have to pick these two things.
I n g such that this difference is minimal.
Cool.
I have the first brute force approach.
I have my first brute force approach.
Yeah, it's like super brute force approach because how many possibilities how many ways are there to
fix I.
Yeah.
Kind of end.
Right.
How many ways are there to fix G.
End of end.
Right.
So, yeah.
Basically, I have my first brute force approach in Begal of an squared, just fixing these two.
Then if let's say I go all lean on brute force approach and I even generated linearly the S prime and
then I linearly still compare s and as prime, I'm gonna have myself a very rounded, nice and cube.
And that's how I started.
I have no shame in thinking about brute forces.
I love brute force approach as men.
What you should love more in computer science are the brute force approaches because they are basically
your solution.
Like right now I know I'm gonna solve the problem because I've got the first brute force approach and
I'm already thinking more.
OK.
There are a lot of ways in which I can optimize this.
I can do a lot of tricks here to get from and cube to a beagle of N.
And let's see how well.
So I have I, I have G and then I have the string.
Let's go.
Let's try to have.
Biegel of M squared.
So I'm gonna clear the blackboard.
And next, I'm thinking.
All right.
Right, and you've got this.
You have some end cube.
Can you go?
Well, beagle event squared.
Morandi, you got this.
You can do this.
And I'm thinking like this.
All right.
Why do I have a bigger event Cube?
I'm fixing the pair, iji.
And it takes me bigger ones end to generate the string and competitive s.
What should I do, Foster?
It's either not fixing each and every i n g because they are and squared or comparing s and as Prime
Foster and I chose the second one, the second one sounded really appealing.
Yep.
I can do some tricks in order to compare them Foster.
And let's see what I did.
What I did was this for each and every pair I and J.
I basically do.
If I have the initial string s.
Right.
I have my ass.
Position zero.
All the way to position and minus one.
Well, it's clear that I'm going to start from position I so all of these.
From position zero to position, I'm minus one.
Are going to be.
Zeros in Asprey.
Let's have here Asprey.
So all of these are going to be zero.
So what is the difference between S and s prime?
Between position zero and minus one and minus one, sorry, the difference between them is how many
ones are in this?
S because s prime has got only zeros.
So I'm interesting in how many ones are in S between positions zero and minus one.
So it's basically in a binary string.
How many once you have in Southbury or in a prefix, it's equivalent to a partial sum.
Right.
So the difference here on this prefix is actually the partial sum.
Let's call it B.
S of A minus one.
All right, cool.
So I know this difference.
Then I have to.
Find out what is the difference in the rest of the array's.
Perfect.
I start from Position I, which is going to be one.
So let's make this a little bit O.
K..
This is a one.
So first of all, I'm interesting in.
Sorry, sorry.
In Asprey.
All right.
So in s prime, this is a one, right?
I'm interesting in what is value is.
Then a plus gate is a one, so I I'm interested in what that value is.
So I plan to cross K is the one what that value is and so on and so forth, what that value is, what
that value is, what that value is.
So basically I care about.
This positions.
Positions.
I.
I plus two crossed the key and so on and so forth until the last one, which is live less or equal than
an.
I have to compare all of these characters' on this positions with what?
We've once.
So the answer is for these positions.
How many are zero?
How?
As simple as that, I am interested in how many zeros are on these positions.
Then.
The other positions from the suffix.
They are going to be zero in as prime.
That's what we know for sure.
So we are interested in the other positions.
How many ones are there?
Yeah, that's kind of it.
So.
The thing is very simple.
For each eye that I fix, let me clean a little bit here.
Again.
So for each eye they fix.
For each eye that I fix.
Let's say this is S.
Eyebrows to cross.
K.
Dot, dot, dot.
And they have the other ones, right.
Each and every position which is greater or equal than I.
Is in one of these two categories is either in s prime.
A one or a zero?
The positions that are in s prime once are, as I said, I.
I that dot that until the greatest one less or equal than.
And the other ones are zero.
But all I'm interested in is.
How many of these characters' on this positions are zero?
Because zero is different than what is this prime?
Which is one and how many from here are once.
So how can I know?
Very quick.
In some southbury, how many zeros and how many ones I have there.
Of course, again, partial sums I have.
I can have something like partial sums to tell me how many ones I have in some Saberi.
And then of course the rest of the positions, if they are not one, they are zeros.
So I figured out immediately that it's super simple.
It's super, super simple to have myself a bigo of N squared.
If I fix I n g, I can compute in constant time using these partial sums.
How many of these positions that I don't want to be zeroes are in fact zeros and how many of the others
are ones.
But then another thing struck to me.
And this is even more interesting.
I figured out.
All right, if I know where I start from, cool, then I have to fix how many of these ones I have.
So I was like.
Where I start Ommaney one.
Now that I have a beagle event squared, I need to go for the linear approach.
So I'm thinking like this.
I have a linear approach for a linear approach.
I can't fix both of these, too.
I and Jay.
I have to fix only one of them.
Do I fix I or do I fix gee, what should I do?
Well, I is the first position.
G is the number of ones who is more important.
Well, I really don't know.
But I have a feeling.
That if I fixed G.
I can somehow deal with this.
I.
And that's because let's take a look again at the positions in the set when we start from.
I.
These are the ones I.
Eight plus two crossed.
Kate.
So obviously, if I know how many of those are, I'm going to have my cell phone I plus G crossed K.
Right.
Forgot to say about the G.
Yeah, sorry about that.
All right, cool.
It's no difference anyways.
And the problem is that I'm not able to fix both of them.
But what have these values?
Income.
I and I plus K and I plus two crossed K and so on and so forth.
They shared the same reminder, Modred, okay.
And that was a big thing to me.
I immediately noticed one thing these values share indeed the same reminder module by module Ocky.
Is, of course, the same as I.
Plus K, Mordialloc, K.
Bonus or fourth?
So why not be smarter about this?
And instead of fixing I n g well, I'm still going to need G.
Of course.
Yeah, that's right.
But instead of fixing I, I can fix I Mordialloc.
And although it seems like the same thing.
All right.
Your fixing eye, which can take and possible values or your fixing.
I modulo K, which can take K less or equal than and possible values.
It's still a brute force approach.
It is.
But fixing the reminders will give us a better time complexity when we are more amortize it.
Or was the term anyway anyways a better amortized I think time complete overall time complexity and
you will see what I mean by that.
I don't know the word.
So one thing that I've noticed here, again, let's continue, was that they shared the same reminder.
So instead of fixing, I am going to fix the reminder, which is I.
Mordialloc.
And why do I do that?
Because if we take a look at the string, which are positions zero, what?
B, dot, dot, dot.
Until and minus one.
For each and every different reminder are we have a different set of values.
If we take, for example, are equals zero.
Have zero.
A two crossed kay.
That.
If we take our equals one, we have one.
One plus key.
One plus two crossed K.
Dot, dot, dot.
And so on and so forth.
Right.
So when I'm fixing each and every reminder are.
Guess what?
I can also fix now, Jay.
And it's not Bigo of and squared.
Yeah, you heard me.
It's not Bigo event squared.
If instead of fixing.
Each and every pair, A.J., I fix the reminder, so I Mordialloc Key and then the number of turned
on LEMS.
What was here.
Biegel of and squared.
I can do now and I will show you why this is linnear L'Étoile.
Let's take some example again.
What was that example?
And I think was.
All right, let's see here.
And was nine K was, too.
All right.
Let's have this example.
We have free.
Yeah, that's a better one.
So an end is nine.
K is free.
Just take a look at this one.
This is epic and is like.
My string is one one one one zero zero zero zero zero.
I am fixing each and every reminder.
Mordialloc.
So first of all, I fix R equals zero.
This means that I will choose to turn on some lamps, which are a subset of all the lamps, which which
are basically on positions multiple of Kate.
So I take a look at this positions, zero, four, five, six, seven, eight.
And because Kate is equal to free.
And the reminder is zero.
I can choose to have turned on in as prime.
Of these two lamps.
Free.
And six.
Right.
If I try out, R equals one.
What are the indices, which Mordialloc gives us the reminder one?
Well, they are one.
They are for.
They are seven, so I can pick a subset of these lamps and have them turned on, which is great.
The fingers, if for each and every reminder I choose the G, which is the number of lamps that I will
have turned on to be less or equal than the actual number of lamps, which are we have that reminder
which correspond to that reminder.
The sum of all these iterations is.
And because each lamp.
Has a unique reminder.
So each lamp belongs to only one reminder group.
So fixing each and every reminder and iterating only through those lamps will definitely give me Bago
of N..
And that was a big thing, guys, because now basically the problem is solved.
If I fixed a reminder and I know I can iterate through all the lamps that correspond to that reminder,
it's not that hard.
Right?
It's kind of a no brainer.
Let's say we fix a reminder.
So for.
Remind between.
And K minus one.
Right.
These are the possible reminders for each reminder.
Are.
I have the lamps.
What are the lamps?
First one is are.
So for.
It starts from R, right?
The lamp is initial R.
Is less or equal than an.
Gets increased by.
For each lamp, I get to do something.
But my point is that these two four loops are big over, right?
That's what I talking about overall time complexity, because if we we add together all these iterations,
it is linear.
So now I iterate through each and every lamp and I have to think about, OK.
Or you have to choose a Saberi of lamps and have them all turned out.
Right.
So from all these lamps.
I have to choose a Saberi of them, a continuous segment of them, and have them turned on and the other
ones are going to be turned off.
So, yeah, that's not a big thing.
I mean, you can think of all the lamps.
Right.
Let's take these lamps and imagine these lamps form another array.
These lamps are basically another array of zeros and one zero one zero one zero zero one one zero or
something like that.
Right.
This is lamp.
This is going to be lamp.
This is going to be lamp plus key.
This is a lamp plus two cross K and so on and so forth.
Right.
If these are these lamps, what I need to do here is.
I have to choose a contiguous segment of lamp's.
I have to choose some lamps starting from one lamp and ending in another lamp.
I have to choose a contiguous segment of these lamps and make all of them one and the other lamps in
the whole sub, in the whole string are going to be zeroes.
That's basically my job, right?
Well, how I can do that.
There are a couple of of ways to do that.
Let's see.
I thought about him.
I have to choose.
Exactly one Saberi from this one's right.
Such that.
All of them are turn are turned on.
So all of them are one.
So if I choose a Saberi of those lambs, I need to know how many lambs in that Saberi are zero.
And that number is going to be basically what I pay to make all my lambs equal to one.
And afterwards, each and every lamp in S is going to be zero.
So this is very simple.
Basically, what I need to do is.
I need to know.
How many zeros I have?
And then I need to know from all the other lamp's in s how many ones I have because those ones are zero
and those zero hour ones.
And guess what?
Yeah, it is as simple as it sounds to be.
It's, again, some partial sums as simple as that.
So you basically get to choose one thing.
You are able from this array of lamps, right?
You are basically able.
To choose its starting or end point, it's really your choice.
I chose the end point.
So let's erase these two nested for loops and see what I mean by that.
If this was, let's say, the chosen lamb.
So all the lambs which have the reminder are I have to choose some sabari.
And what I did was that I chose.
The right pointer of this Saberi, and then you have to find the optimal left pointer, right?
Such that.
The number of zeros that are here.
So the number of zeros from.
This sub, Eric.
As the number of ones.
The rest of us.
Right.
So the whole substring, the whole string s minus all these lamps, which we have chosen in this Saberi
of reminder, are you'd have to take the number of ones from there because you are making them zeros
and the numbers of zeros here and you are making them one.
You have to find this optimal el in Kohnstamm time.
And how do you do that?
Well, now, did you know about the partial sums?
It's not that hard, right?
Because the number of zeros from L two are you can write a special sums.
Right.
You can have, let's say, partial sums of zero.
How many of them are zeros.
Let's say right.
Of our.
Minus partial sums is zero of L minus one, plus the number of ones from the rest is basically the total
number of ones from the street.
But let's have total let's say total is the number of ones from the whole S string, minus how many
ones they have here.
And this is the number of ones in the rest of the string.
Right.
So minus partial sums, one of our.
Because this was a minus.
Now it's a plus because this sign partial sums, one of L minus one.
So basically, you have fixed the reminder you have ether rated through the lamps, which have that
reminder and stored them in a separate array.
Let's see.
Let's just imagine that.
Then we use the partial sums, the partial sums.
In order to get how many zeros we have in this Starbury, plus the total number of ones in the holler,
the string minus partial sums, one of our plus partial sums, one of L minus one note is that this
R is the right point or not the same as the reminder.
Right.
So, yeah, I really should specially specify that.
And now, because I chose that, I will fix the right pointer.
I know partial sum zero of right?
I know partial sums, one of right.
These are no constants.
The total is constant because is the total number of ones in S..
It doesn't depend on left, right or the remainder.
And I have to maximize pass with some one of left minus one minus partial sum zero of left minus one,
because all of them are constants besides these two.
I have to maximize this difference.
And how do I do that?
I'm going to store another variable.
And as long as I iterate for that string, I'm gonna keep a variable, which is gonna tell me.
Let's say mean div.
Is very what is gonna tell me.
All right.
This is the minimum difference between all of these partial sums for the left.
Yeah, I know it can get quite a little bit messy and confusing now, but let's do one more recap here
just to make sure that you all understood it.
The first step, really simple.
Fix the reminder.
But this is going to be between zero and K minus.
That step number to iterate through each and every lamp with this reminder.
We said we have proved this.
This is going to be linearly.
So you can have these two nested for loops.
And it's still linearly.
So for each lamp that starts from a reminder all the way to N..
And let's say plus equals or something.
Okay.
Right.
For all the lamps, you've this reminder, you can store them into a separate array.
Let's say let's say an array V.
Right.
So we can do something like V that push back.
S of the lab.
So in this V vector or array, whatever you are in a store, it you are going to have the lamp's with
this reminder, you have to choose that Sabari right and left.
So what can I do?
Here is again, make another for loop where I choose the right pointer.
Which is going to be, again, between now between Zero and VEDAT sites.
Which was the right point there of the Saberi of the Lambs, which have reminder.
Ah.
And in order to get the optimal left pointer, I'm gonna have that mean difference variable.
Which basically is going to tell me that, I mean, difference or makes a difference.
I think it Max.
Yeah.
Because this should be as big as possible, the max difference, which will always be part of the answer.
So for each and every right, I get all of L because I know that makes a difference.
And then I get to update the max difference because these are rights that I have just fixed.
He's going to be now a feasible left pointer for the next right once.
So first of all, use Max DPH to get the answer for this.
Right.
And then update Max diff in order to use it in the future.
So that's it.
Reminder LEMSIP, that reminder stored them in an array.
You need a Sabari from this array.
You have that array.
You have that partial sums on that array.
And use that partial sums.
And this Max Deve in order to always know the left for each.
Right.