All right, guys.
Hello again.
Guess the maximum.
Right.
Let's see how I've coded it, because during the contest I've had accepted, which is pretty cool as
we are.
Let's take a look.
Let me just decrease the volume in the music.
And yeah, it's quite a long source code because I've just was in a hurry during the contest and I didn't.
How's that would call?
Am I missing the word right now?
I didn't refactor it right because I have a lot of duplicate code, which, of course should be written
in a function.
That's the way we do it.
If you are a good coder.
But I've just hurry then copy paste all the way and I don't recommend you to do that.
But we are going to use that by format.
Right.
So let's see.
This is an interactive problem, as you know.
So I've actually haven't solved a couple of I mean, I haven't solved one interactive problem in years,
but especially on good forces.
So I was a little bit afraid that I wouldn't code it well, because I might get wrong answer sort a
runtime error from every angle.
But yeah, it was accepted from the start.
So I'm I'm pretty happy about it.
So let's see again, as usual, we read the number of tests and for each test we read the N and the
K.
And what they do here is that I construct a vector of vectors which are going to be the subsets.
Right.
So super simple for each and every subset.
Between one and K, I just, I read see the number of elements and four.
I read each element in variable X and I just push back in subsets of I.
Right.
So this is just the reading start.
The reading point.
It's cool.
Then what I do is that I query as we have seen.
I first of all query the whole, the whole array.
Right.
So I, I query the all the end elements.
Right.
Which is n and then each number I.
Between one and end.
Right.
So first of all, I should have already written this in a function.
I suggest to when you implement interactive problems to read the repetitive code such like performing
the query which is going to be very repetitive, you do that a lot of times repeating a function query
and having those parameters, having a vector of into the parameters, the elements that you're going
to query for this problem.
And yeah, it's way easier than what I did.
But anyways, I query the whole array and then what I do is that I read the answer, which is the max
Val.
And then here comes the binder research.
Right.
The special binary subject we have talked about.
It's pretty simple as like in any binder research.
We just initialize the end points, which is left equals one, right equals K.
And initially the answer is minus one because you never know if you don't find any answer.
It's okay to know that by having a value minus one in that variable.
So answer is initially minus one.
Now why left is less than or equal to right.
I compute the middle which is left plus right divided by two.
And then what I do is that here finally I have written a function because it was too much good and the
function is max from breath, which I have the parameter subsets and meet.
So basically what I do is that.
I take the first middle subsets union them together in a greater subset, of course, we vote duplicates
or something, and I query on that subset.
And I find the maximum value on that subset.
And effet is Max Vall, as we have seen.
This means that I have a possible answer.
So answer equals Smead, but I don't know.
For now, if this is going to be actually the smallest one.
Right.
So I just take into account by answer the court's meat.
But I continue the search.
We have smaller values, so.
Right becomes Maeder minus one.
So I restrict the searching area to smaller values, right?
Of course.
That means I don't need to look on left because I know those are not valid.
So all I have to do basically is look for greater ones because only those could be valid.
Right.
So, yeah, after the binary search terminates, I have basically two possible scenarios.
Either answer is minus one, so I haven't found anything.
But that doesn't.
That's possible.
That might be possible, I think.
All right.
Cool.
Or elsewhere, is that position right?
Let's actually take a look first at Max from Breadth to understand fully the binary search.
So, as I've told you, I just have here a vector of vectors, which is subsets.
Be very careful about the reference.
Because if you don't store the parameter, the argument of the function for reference, it is going
to be copied over and over again.
Right.
So by performing this, I just basically get rid of the copying of the elements, which could be really
expensive for, like, a lot of elements.
Right.
So, yeah, makes from prev of the vector of vectors, which are the subsets and B which is my my Neidl.
Right.
I think it's my me if I remember.
Yeah.
Which is my middle.
Right.
So which is the number of first subsets that I'm going to union.
So first thing that I do I'm union ing them how to do that.
It's really simple.
You can just iterate through each and every element of these first B subsets and marketers visited.
Then you just iterate through the whole visited array.
And you take the element that are revisited or that is marked with true this vector of Bodanis and you
store it into the final union subset.
Right.
So you can see what I've done here.
I have a vector vector which is subsets.
I have B I start with the vector of visited which has LEMS.
And plus one and all the elements are false initially.
And then I iterate through each and every subset between one and B, iterate each and every element
in that subset.
Remember this total which is pretty good.
And I visit that value.
So basically here I have marked each and every value that in that appears in at least one subset.
After doing that, I start to build the query subset.
So I have vector of integer query, which is initially empty.
Then I go through each and every position between one and end, and if it's visited from here, I just
push it into the query, the final vector.
And after doing that, I just print the query, which again, I should have written in a function or
something.
But yeah, basically I have query that size and for each element in query I print the query and the
little flash I read the answer C an X and I return.
Right.
So that's what happens.
Yeah.
All of this code.
It's better to write it in a function like you can have a function perform query.
Which only should have this argument if you have this argument.
It's really enough and could return this X, which is the answer.
Right.
And we do that.
Right.
So at this point, after finishing the binary search here, I already know that the value that I'm looking
for and since I know the value, everything's quite clear.
I take into account of the possibility that the answer is minus one or not.
So let's see, first of all, let's see the second scenario.
So if answer is not minus one here, sorry, if answer is not minus one.
Right.
I again start we have a vector visited initially false.
I again iterate for each and every subset from answer.
Again this can be also written in a function like function union subsets or something which is going
to unit on your subsets.
Again I just copy paste all the way.
So yeah, just mark all the values in the subsets as visita as visited or true.
And then iterate for each and every value between one and N.
And if it's not visited now remember we take the compliment.
If it's not visited we push it into query.
Then after performing this we are able to perform the query again, query that size each element.
And we read the answer, which is X and result of answer equals X.
And that's it.
Right.
As we have discussed, the solution pretty straightforward.
After finding the answer, we union.
We query the compliment.
And we know the result for answer.
And then.
Here.
This is going to happen either if answer is equal or not, with minus one, which is the good thing,
right?
Because you have to bring the answer.
Basically, we know the answer.
We know the result.
Which initially was equal to Mack's civil rights, so let's remember this.
Initially, the result is Maxwell, right?
All the way.
And if the answer is not equal to minus one, this means we have found and sort of the position in which
the result is going to be change is going to be different and will have value X.
And if it's not, you can just print the result.
We have all the values of Maxwell and everything's fine, right?
So again, try to refactor codes as much as possible, especially in practice.
I really suggest you do take a look at my source code.
Why not try to implement it yourself, but try to refactor, read and write code?
Very, very.
And more elegant.
That's what I did in the contest.
Right.
So it works.
Even if it's ugly, it works.
You're gonna write it better.
You're gonna write it more structured and.
Yeah.
Now everything should be clear.
See you on the next on.