Editorial for COCI '14 Contest 2 #3 Studentsko

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Let us examine a sample test (8 students, teams of 2 players):

3 2 1 6 7 5 8 4

Let us denote the students that must be in the same team with equal numbers:

2 1 1 3 4 3 4 2

Ante can take any number from the sequence and relocate it. With these operations, in the minimal number of steps, he needs to obtain the sequence:

1 1 2 2 3 3 4 4

Let us find the longest subsequence of elements that are in a relatively good order in the sequence:

2 1 1 3 4 3 4 2

This is actually the longest nondecreasing subsequence of the sequence. Now we can relocate all the elements that don't belong to this subsequence to corresponding locations, each in one minute.

It is easily shown that this solution is optimal and we leave this for the reader to practise. Finding the longest increasing subsequence is a typical problem that can be solved in either \mathcal O(N^2) or \mathcal O(N \log N) complexity using dynamic programming.

We recommend that you read the solution to this typical problem on this link.


There are no comments at the moment.