Editorial for IOI '96 P4 - Sorting a Three-Valued Sequence
Submitting an official solution before solving the problem yourself is a bannable offence.
The basic idea behind our solution is the following.
Compute first the number of appearances for elements in the input sequence. Then the sorted sequence consists of number of 's followed by number of 's and then number of 's.
We say that an element is in the place of 's if the current position of equals the position of an element in the sorted sequence. We use the abbreviation to denote an element in place of 's.
Next, compute , the number of elements 's in the place of 's for all and . Consider the following algorithm written in pseudocode.
NoCh:=0;
While Not Sorted(S) Do Begin
If there are x and y in each other's place Then Begin
Inc(NoCh);
Exchange x and y;
Update NEP[x,y] and NEP[y,x];
End Else Begin
If (NEP[1,2]>0) And (NEP[3,1]>0) Then Begin
Exchange a pair of elements 3:1 and 1:2 ;
Update NEP[1,2] And NEP[3,1];
Inc(NoCh);
End;
If (NEP[2,1]>0) And (NEP[1,3]>0) Then Begin
Exchange a pair of elements 2:1 and 1:3 ;
Update NEP[2,1] And NEP[1,3];
Inc(NoCh);
End;
End;
End;
First, we show that the number of exchange operations performed by the algorithm can be given by the expression:
After performing exchange operations for all , the resulting sequence contains number of elements , , if and , , if . In the first case, the algorithm makes exchange and , which results in an element in place of . Therefore in the next iteration, an exchange of and will be performed. The second case is similar. We conclude that the expression is correct for the number of exchange operations performed by the algorithm.
Let us denote by the minimal number of exchange operations needed to make the sequence sorted. We shall prove that . The proof is by induction on the value .
If then the statement obviously holds.
Assume that for all if , for some . Let be a sequence and .
Consider an optimal sequence of exchange operations that makes sorted. Assume that the first exchange operation exchanges elements and (or and ) and denote by the resulting sequence. We distinguish the following two cases:
C1: x1=y2 and x2=y1 or
NEP[1,2]>NEP[2,1] and x1=1, y1=2, x2=3, y2=1 or
x1=1, y1=2, x2=2, y2=3 or
x1=3, y1=1, x2=2, y2=3 or
NEP[1,2]>NEP[2,1] and x1=2, y1=1, x2=3, y2=2 or
x1=2, y1=1, x2=1, y2=3 or
x1=3, y1=2, x2=1, y2=3 or
C2: all other combinations for x1, y1, x2, y2.
We can verify by a routine calculation that in case C1 and in case C2. In case C1, we obtain by the inductive hypotheses that the algorithm performs exchange operations.
Case C2 contradicts the optimality condition, therefore an optimal sequence of exchange operations can only start with an exchange specified in case C1.
In order to develop an efficient algorithm that constructs a sequence of exchange operations, we introduce the array , that always contains the first position of in place of 's. is computed by the preprocess procedure and is updated after each exchange operation.
Comments