{ Solution for task SORT3 -------- --- ---- ----- The basic idea behind our solution is the following. Compute first the number of appearances Na[x] for elements x=1, 2, 3 in the input sequence. Then the sorted sequence consists of Na[1] number of 1's followed by Na[2] number of 2's and then Na[3] number of 3's. We say that an element x is in the place of y's if the current position of x equals the position of an element y in the sorted sequence. We use the abbreviation x:y to denote an element x in place of y's. Next compute NEP[x,y], the number of elements x's in the place of y's for all x and y. Consider the following algorithm written in pseudo-code. 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 Ch(S)=Min(NEP[1,2], NEP[2,1])+ Min(NEP[1,3], NEP[3,1])+ Min(NEP[2,3], NEP[3,2])+ 2*Abs(NEP[1,2]-NEP[2,1]) After performing Min(NEP[x,y], NEP[y,x]) exchange operations for all x<>y the resulting sequence contains NEP[1,2]-NEP[2,1] number of elements 1:2, 2:3, 3:1 if NEP[1,2]>NEP[2,1] and 1:3, 2:1, 3:2 if NEP[1,2]1. Let S be a sequence and OCh(S)=k. Consider an optimal sequence of exchange operations that makes S sorted. Assume that the first exchange operation exchanges elements x1:y1 and x2:y2 ( or x1:y2 and x1:y1) and denote by S' 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 Ch(S')=Ch(S)-1 in case C1 and Ch(S')>=Ch(S) in case C2. In case C1 we obtain by the inductive hypotheses that the algorithm performs Ch(S)=Ch(S')+1=OCh(S')+1=OCh(S) exchange operations. Case C2 contradicts to the optimality condition, therefore an optimal sequence of exchange operations can only start with an exchange specified in case C1. In order to develop efficient algorithm that constructs a sequence of exchange operations, we introduce the array First, that First[x,y] always contains the first position of x in place of y's. First[x,y] is computed by the preprocess procedure and is updated after each exchange operation. } Program Sort3; Const MaxN =1000; { max number of elements to sort } Type ElemType = 1..3; ArrayType= Array[1..MaxN] Of ElemType; Matrix = Array[ElemType, ElemType] of Integer; Var N : Word; { number of elements to sort } S : ArrayType; { array of elements to sort } Na: Array[ElemType] Of Word;{ Na[x] is the number of x's in the input } NEP : Matrix; { NEP[x,y] is the number of x's } { in place of y's } First: Matrix; { First[x,y] is the first position of x } { in place of y's } NoCh: Word; { number of exchange operations } OutFile: Text; Procedure ReadInput; { Global output variables: N, S, Na } Var InFile: Text; i,j: Word; Begin Assign(InFile, 'input.txt'); Reset(Infile); ReadLn(InFile, N); For i:=1 To 3 Do Na[i]:=0; For i:=1 To N Do Begin ReadLn(InFile,S[i]); Inc(Na[S[i]]); End; Close(InFile); End { ReadInput }; Function Min(X,Y: Word):Word; Begin If X0 Then Begin Repeat Inc(First[i1,i2]); Until S[First[i1,i2]]=i1; End; End { Next }; Procedure Pairs; Var M,i,x,y :Word; Begin For x:=1 To 3 Do For y:=x+1 To 3 Do Begin M:=Min(NEP[x,y], NEP[y,x]); For i:=1 To M Do Begin WriteLn(OutFile, First[x,y],' ',First[y,x]); Next(x,y); Next(y,x); End; End; End { Pairs }; Procedure Triples; Var M,i: Word; Begin If NEP[1,2] > 0 Then Begin M:=NEP[1,2]; For i:=1 To M Do Begin WriteLn(OutFile, First[3,1],' ',First[1,2]); WriteLn(OutFile, First[1,2],' ',First[2,3]); Next(3,1); Next(1,2); Next(2,3); End; End Else Begin M:=NEP[2,1]; For i:=1 To M Do Begin WriteLn(OutFile, First[2,1],' ',First[1,3]); WriteLn(OutFile, First[1,3],' ',First[3,2]); Next(2,1); Next(3,2); Next(1,3); End; End; End; Begin { Program } ReadInput; Preprocess; Assign(OutFile, 'output.txt'); Rewrite(OutFile); WriteLn(OutFile,NoCh); Pairs; Triples; Close(OutFile); End. { Scientific Committee IOI'96 }