Editorial for Unusual Competitions,Two Teams Composing:

Problem Discussed Today:


Editorial



Idea:

Let the number of students with the skill i is cnti and the number of different skills is diff. Then the size of the first team can not exceed diff and the size of the second team can not exceed maxcnt=max(cnt1,cnt2,…,cntn). So the answer is not greater than the minimum of these two values. Moreover, let's take a look at the skill with a maximum value of cnt. Then there are two cases: all students with this skill go to the second team then the sizes of teams are at most diff−1 and maxcnt correspondingly. Otherwise, at least one student with this skill goes to the first team and the sizes are at most diff and maxcnt−1 correspondingly. So the answer is max(min(diff−1,maxcnt),min(diff,maxcnt−1)).

Solution Link: Solution



Idea: 

Obviously, if the number of opening brackets is not equal to the number of closing ones, then since the described operation does not change their number, it will be impossible to get the correct sequence. Otherwise, if their numbers are equal, you can take the entire string and rearrange its n characters so that the string becomes a right bracketed sequence, for example, "((((…))))".

Let pi be a prefix balance on the first i

characters, that is, the difference between the number of opening and closing brackets.

Consider an index i such that bali−1≤0, bali<0, or bali−1<0, bali≤0. Then, if the si character does not participate in any shuffle operation, the resulting string will have a ith or i−1th prefix balance negative, making the resulting sequence incorrect. This means that at least characters with such indexes i

must participate in at least one operation. It will be shown below how to use only them in shuffles to make a right bracketed sequence.

Let's represent this bracketed sequence as a polyline. It will start at the point with coordinates (0,0), end at the point with coordinates (2n,0), i - th vector of this polyline will be equal to (+1,+1), if si= ( and (+1,−1) otherwise. Then the above-described indexes i, which must participate in at least one operation — are exactly all the segments below the line x=0. To make the sequence correct, we will turn all consecutive segments of such brackets backwards. It's not hard to see that the sequence will become correct.


Solution Link: Solution

If there is an error or want to discuss your approach, then please feel free to drop in the comment section.

Comments