Basically, you are given the length of some strings, which is M.
Right.
So you basically start off with each and every binary string of length.
M.
Right.
There are two at power m such strings in total and.
OK.
Then you are told how they are lexicographical graphically smaller than others.
You know what lexicographical smaller means.
So I think that's cool.
And from this set which contains initially to add power m strings you will remove and these things binary
strings and you are given those strings.
Right.
So you start off with each and every binary string of land m you remove any of them.
And then you are asked to print the string, which is the median from the remaining set.
Right.
So take all the strings, remove those and strings that are given in the input.
And then sort lexical graphicly the strings.
And give me the media basically.
That's what the problem asks, right?
So, yeah.
All right.
It wasn't that hard, I'd say.
And it was pretty interesting.
So how do they think about it?
First of all, I thought about a way simpler problem.
I think, like, all right, so what's going to be a simple problem?
Let's suppose I don't remove any string, basically.
Right.
So I have all those to add power M strings of LAMS M and I keep all of them.
If I do that.
And I need.
The median.
So the string.
Which is basically to add power, minus one lexical graphicly, the smallest.
Right.
So basically, I need that.
All right, cool.
So let's think out.
If I don't remove any string.
It's pretty simple, right, because.
When you deal with binary numbers, binary strings, basically the Kafe Lexical GraphicLy smallest string
is number K written in by the reform.
And that's it.
Right.
So yeah, the smallest is zero.
Then the second smallest is one.
Right.
Then you have one zero one one and so on and so forth.
It's really simple.
The whole difficulty of the problem is given is given by the fact that we remove some strings.
So I'm thinking about this.
Let's say this medium, this position, which is true at power M minus N plus one divided by two or
something, I think that's the formula of that index.
Let's noted with some K.
Right.
So I have to find the cave.
Smallest lix geographically.
String called.
Kay is going to be pretty big.
Right.
Because M is 60, so I can have something like what power 60.
Right.
KS less or equal into a power 60.
So if that happens.
Why do I have to do?
Is find a way of finding this cave, smallest number involved performing cave operations or something
like that.
So.
It's kind of a classic problem.
I mean, it's that type of problem in which you have to build from scratch the Kafe small lists.
The other day.
No, it's a constructive algorithm.
Right.
On all of the problems which ask for the Kafe smallest, especially lexicographical string, it is a
constructive algorithm because you are going to think, first of all, the first character and you are
going to say something like, hmm.
If the first ever character is zero, then the number is good.
Could be the smallest one.
If it's one, then I know the three.
There are two at power and minus one a smaller number than that or something like that.
Right.
So I knew this is going to be a constructive algorithm.
And at this point I am just thinking a more constructive algorithm.
And let me show you how simple it was.
So what I have to do here is that I'm going to construct a number which has lamp.
Exactly.
Let's take an example.
Yeah.
Let's take an example.
I think that's cool.
All right.
Right.
All right.
Right.
Mm hmm.
What should we do here?
Let's take the second one for free.
All right.
So I have to build a number which has length.
Exactly.
Free.
So M equals free.
So here I have free.
One, two.
Free.
And the numbers that they have erased are zero zero zero one one one.
Let's write them down here.
Zero zero zero one one one one zero zero zero one one one zero zero zero one one call.
So I have removed these numbers.
Right, called.
M is for M is free.
So from all that to add power free numbers, I subtract four of them and buy the formula, I have to
increase one and divided by two.
And I get an eight minus four for plus one five divided by two, which is going to be two.
Right.
So I need the second smallest.
Binary number of lenth m.
Right.
Of course, which is not in this set, right.
So what is good?
What's it gonna be?
I think it's gonna be zero one zero.
Right.
Am I right or not?
Yeah, it's zero one zero.
Right.
Because what can we do is we can have zero zero one.
And that's valid.
We can have zero one zero.
Oh, we can have one.
You have zero one one, we can't.
We can have one.
Zero one.
And so on and so forth.
Right.
And they are like two roughly increasing.
Right.
In disorder.
So.
Basically, what they think about at this point is super simple is I just asked myself.
I just ask myself, what's going to be the first child actor like in any other constructive algorithm?
Right.
So I take a look at the first character.
And I'm like, it could be zero or one.
Right.
All right.
What if this character is going to be a zero?
So basically, I'm gonna have a number of land free starts with you.
How many numbers of land free which started with zero, are there exactly?
Four.
Then what are going to be these numbers?
Let's say zero zero zero zero zero one zero one zero and zero one one run out from all of these numbers,
which are four of them.
I have to see how many of them are not in this set because these are the numbers that we have removed
initially, right?
So zero zero zero is not anymore.
011 basically.
So what I have to do at each point is for the first position initially, if I had the zero.
From this to what power M minus one?
Numbers like in this example to add power two, which are for.
I have to subtract.
How many numbers are in this set which start with zero, and I find two of them right.
So at each point I have to do that right.
For example, here I have four numbers, minus two of them started with zero.
So I'm going to have.
Exactly, two numbers.
Which are going to be subtracted.
Right.
So I have a total of two possible numbers.
Jordis, too, right?
So what I found out here is that if I start my number Riva's zero, this number is going to take only
two possible values.
And I have to see what is my K?
O k equals two.
So I have to find the second smallest number.
And if I started with zero, I have the second smallest number here.
Cool.
So this is a zero move.
Then position number one.
What if I have a zero?
How many numbers are there?
Which start of land free, which started?
Zero zero.
There are two of them, right?
Zero zero zero zero zero one.
How many of this?
Zero zero zero zero zero one are in my set.
Well, zero zero zero.
This is the only one which starts with two zeros.
Only one of them.
So from to add power now and minus two.
But from to add power and minus two, I'll have to remove one because it was removed initially.
I get a total of one number.
All right.
So if I had a zero here, I have only one number, so only the smallest possible number, but I need
the second smallest.
So it's quite clear that I won't have a zero.
I'm going to have a one here.
And because I'm going to have a one from this key, I'm going to subtract this value.
Just one.
So K minus equals one.
And it stays one.
And then because case one, I try again, hero zero and I have to find out.
All right.
I have only one possible number and zero one zero is not in this set.
So this means that.
This is a valid one, right?
So it's like any other classic constructive algorithm, you just go increasingly with the positions
and first try the smallest lexical graphicly option.
And if that's a valid one, you stick with that.
If it's not, you remove how many integers would have been in that option.
And you are left with K minus that number and you have one there.
Right.
So just to recap, we are going to see the code then.
What I do is basically this thing.
So for.
Which is from one to M..
So I be.
The digits increasingly by the positions are in the order of importance from the most important to the
list to the least important.
I think there's the word yes, which position I first try.
Hmm.
What about the answer on that position?
Is your.
It'd be a zero.
Well, I find it.
Well, I have to do something like that from the total of to what power M minus.
That position number.
Right.
If we fixed the digit on position, boss, have a total of two power and minus plus integers subtracted
by how many of them.
How many.
On the set that is given in the input has exactly the same prefix of lamp posts as my answer.
So if the answer by now was zero zero one zero and then we don't know.
Right.
And we are here on post.
I need to know how many of the numbers in that set have this prefix of land for equal to mine.
And I'm gonna extract them because they are removed.
Let us know.
Compute this number.
Oh, I just try to zero.
Dysfunction, we are going to see how how to implement this function.
And let's call it X and.
If X is greater or equal, then K, this means that if I pick the zero, the number I'm looking for
is going to be in my range, which is cool.
So if.
Happens x greater or equal then?
And it's all good.
Answer on position, boss is for sure.
Zero and we can't.
If X is strictly less, then K, that means that the number I'm looking for is not in this range.
So I have to look further for greater numbers, which means that ends on POS.
It's not zero, but what?
And because it is one I have just passed through all those numbers, which would have been obtained
by setting this digital zero, so key is going to be subtracted by all those values because we won't
get to any of them anymore.
So K minus equals X.
Again, this is a classic or instructive algorithm.
You know, the deal basically, that's the whole template for these kind of things, right?
So, yeah, this is not a one or two.
This is the only thing that we have to check.
Right.
So we just check if this can be a zero or not.
And how many function as again, the limits are not very tight or something like that, like Emmies
60 and is 100.
You don't have to to have an optimal solution here.
Right.
If you wanted to be foster or optimal, you could use something like a try.
Right.
Which is that data structure that looks like a tree and has letter links.
Right.
You could use something of that or you could use some more fancy beat masks or something like that.
Right.
But here, because the limits are still pretty small, you could do something like a brute force.
So let's see what I did to compute the.
Those numbers, that's in the source code.
Right.
So what I did, I get.
Basically, let's start from here.
For each and every position, from one to M.
It's going to happen if I store a zero.
So I have how many zero equals how many of I.
And zero.
And this means how many numbers?
Are going to be equal.
To me right now, how many numbers are going to have the same prefix of length?
I with me, if I would have to store zero here, right.
So let's take a look at how many how many of posts and see and the counter is initially to add power
and minus plus.
As I've told you, and then we are going to subtract those numbers which were in that set and have a
prefix of land force equal to mine.
So what I do is that.
They basically try out each and every number from one to N.
And if that number is valid and is valid means that on the previous step it had the same prefix as me.
Right.
So if I want now to have the same prefix as me, this means that on the previous step it had the same
prefix as me.
And now these characters' is a zero, just like me or in my case, in this function C.
Right.
So what I did is that if is valid.
So the first post, minus one Characters' are the same and character boss is the same.
That counter minus minus because it's in that said it was removed.
So I have to remove it from this once too.
And I just returned the condo.
So I basically know that x how many numbers are in my range.
Right.
So this is the X and they just query if X is greater or equal than okay then I can stick with the zero.
I said the zero.
And they update volleyed while I do here is that of course after I said this is zero.
I'm going to need the new is valid array to be updated for the next step.
Right.
So I take all those valid strings which were true and some of them are going to be now false because
they went to the first post minus one ureters were okay, but not the posture or maybe is not.
So they are not valid anymore.
Right.
So what I do basically is that I know that I am going to have a zero in my solution and I update those
strings.
They are not going to be valid anymore.
And else, if this is less than K, then the number I'm looking for is not in this range.
So I just subtract X from K.
I said the answer to be one.
And again, I update valid.
And in the end I just bring the answer.
And that's a nice constructive algorithm.
Start small.
Start from the most important position and just decide on the spot.
If it's going to be a zero or one.