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