The thing is that you basically have an array of elements, but you don't know the values in that the
rate, you just know those subsets that are disjoint that he picked for the password.
He picks a subset, let's say, subset number one.
And the first character of the password is the maximum between all the elements that are not in that
subset.
Right.
So immediately I think about this when I have to pick the maximum between some subset of elements,
I think about the maximum in the whole array.
So I suppose, all right, I'm going to have an array of integers in this every I'm going to have a
maximum element.
Let's call it Max.
This max element is going to be on some positions, right?
Maybe I have four elements that are equal to Max.
I don't know where.
But let's suppose I have them.
First thing that clicked to me is that these subsets that he chose and we are given in the input are
disjoint.
Right.
So I'm thinking like, hmm.
If are disjoint and one all right, literally, just briefly, if this sub is are these joint right.
And this is the array which has an elements and let's say I have a video of Max here, another value
of Max here and another video of Max here.
Free Max is right.
If there is one subset, which let's say this subset.
Which basically contains two values of Max.
So if let's say subset number one, for example, has this in this is.
This means that there is no other subset as to as free dot, dot, dot s.
None of them is going to contain any more.
These values of Max.
So if none of this subsets contain these true values of Max that are contained by S1, this means that
the password for them be to be free.
Beghe is Max, because if they don't contain Max, this means that the maximum between every other element
is Max.
Right.
And that was the idea.
That was the whole thing, basically, because there are these joint.
If there is maybe not this one.
That's the problem.
I don't know if it's as one as two as free or some S.P., but or I now realize that I have my camera
here and you probably don't see.
All right, cool.
So maybe not as one, but if among these subsets as one is to S.P. Askey, if among all the subsets
that we are given, there is one of them, S.P..
Right.
Which contains one of these maxes from the array.
Right.
So if there is this S.P. and the max is part of S.P..
Right.
Let's call it Mexica because there are actually more keys.
One of the max is right.
If one of the maxi's is part of this S.P., this means that this Max is not part of the other ones.
Right.
So this Max K, let's call it.
Which is part of Espey is not going to be part of as one as two Dadda.
That is B minus one is P plus one Dhada that escape.
Right.
So all I need to find out is that is whether there exists some subset among these K subsets which contain
at least one value of max, which is the maximum between all the array.
If I find one Espey like that, I know for sure that all the values in the password are Max except the
value of this S.P., which could not be Max.
Right.
So basically what I do is that I have to find this S.P..
If I find this ASPEY, it's cool.
The password is Max.
So Max, Max, that adat on position B, it's not necessary, Max.
I have to find it.
And then Max.
Max, that that only Max is right.
And of course, if I find B, I'm just gonna do a usual query.
Right.
I take the S.P..
I take the other indices, which are not part of S.P..
I do that query.
I know that value.
Right.
So this is really easy to find.
What is hard about this problem is find this S.P..
I have to find one is B, which contains a value of Max.
Or find whether there is no way spee maybe.
Which contains Avella of Max.
If there is no subset which contains the max, the password is only Max Max maquilas.
If there is one, maybe that element is not Max.
And how do I find.
Right.
How do I find this S.P..
Which has the value of Max.
I'm gonna buy the research at.
How did I come up with that?
We can perform twelve queries, right?
So the problem says you are not allowed to perform more than 12 queries.
And the length of the array, not the length of K, the number of subsets is 1000.
So I have 1000 subsets.
I need to find a special subset.
We have only 12 queries, though.
It's binary search.
Right.
And I'm gonna tell you quick how we do the binary search.
And then you should be able to solve it by our own.
Basically, you take all the subsets A.
S, B is P plus one below escape.
And of course, this is the left initially.
This is the right.
You take the middle one.
Right.
And what you have to do is.
Ask ourselves this.
Is there between all these subsets, one subset which contains the maximum?
Well, if there is one subset here which contains a maximum value, this means that if I take these
subsets and unite them.
They create a new, bigger subset.
If I query on this, so query on this greater subset, this query has to give me maximum.
And that's how you do it.
Let it left is initially one.
Right is initially okay.
You take the middle.
And then each time you want to validate the middle, you take these subsets.
You unite them together.
So you are basically you will have a greater subset of indices and you query on that subset of indices.
If the maximum between all those indices is Max, that means that the value mix is somewhere.
If it is somewhere, that means that it is in some subset from this fourth peak.
So what you do basically is that you.
Suppose the answer is here and move and search in this range.
If these united don't have any maximum, this means that you have to look for right there once.
And that's it.
Right.
So we have twelve queries.
Log of K binary search.
Take the prefix.
Unite them.
We can do this brute force.
We have a for loop.
That's pretty simple query that greater subset.
And if the answer is Max then the answer, the S.P. is going to be there.
So you are going to limit the search of the by the research to that prefix and you start looking there
and do this over and over again.
Right.