Final Indonesia National Contest 2007 :: Problem A - Minimum Swap

ACM/ICPC Indonesia National Contest 2007

Problem A

Minimum Swap

Time Limit: 1s

Sorting a sequence either into ascending or descending order is a common problem in real world.

One of the most common methods in sorting algorithm is comparing and swapping any two elements in the sequence. Supposed I have invented a new sorting algorithm which uses this swapping method. I need to compare the number of swaps occurred in my algorithm with the minimum number of swaps that actually needed to sort some sequences.

Help me determine the minimum number of swaps needed to transform a sequence of characters into a sorted sequence in ascending order. In this problem, you may assume that each character will appear at most once in the sequence.

Input

Each line contains a sequence of lowercase characters S (1 <= | S | <= 26). There will be no repeated characters in S and each ith character (0 < i < | S |) is in range ['a'...'z']. Input is terminated by EOF.

Output

For each test case, output a line containing the minimum number of swaps to transform it into a sorted sequence of characters in ascending order.

Sample Input

abc
cba
acb
bdca
fedcba

Sample Output

0
1
1
2
3

---

Problem Setter: Lego Haryanto

---

Pembahasan Problem A - Minimum Swap

Diberikan kurang dari 27 huruf yang berisikan alphabet 'a' sampai 'z' secara acak dan unik (tidak berulang) dalam satu baris. Anda harus menukar dua posisi dari huruf di baris tersebut sehingga semua huruf menjadi terurut menaik. Berapa jumlah minimum pertukaran yang harus anda lakukan?

Perlu diketahui bahwa suatu permutasi kalau kita ikuti jejaknya, dia akan membentuk suatu cycle.

Contoh:

Ini adalah salah satu permutasi dari 10 angka dari 0..9:

8 2 9 5 4 6 3 1 0 7

Anda dapat membayangkan permutasi ini disimpan dalam array:

index: 0 1 2 3 4 5 6 7 8 9
array: 8 2 9 5 4 6 3 1 0 7

Dari sini anda bisa melihat ada 4 cycles. Suatu cycle terbentuk dari 
hubungan antara index dengan isi dari array tersebut yang menunjuk ke 
index lain dan seterusnya sampai kembali ke index awal.

0 -> 8 (-> 0)
1 -> 2 -> 9 -> 7 (-> 1)
3 -> 5 -> 6 (-> 3)
4 (-> 4)

Untuk setiap cycle dengan length C, anda hanya perlu C-1 swap untuk membenarkannya.
Jadi dalam contoh diatas, ke-empat cycle memiliki length:

0-8         // cycle length = 2
1-2-9-7     // cycle length = 4
3-5-6       // cycle length = 3
4           // cycle length = 1

Total minimum swap yang dibutuhkan adalah: 1 + 3 + 2 + 0 = 6 swaps

Untuk problem Minimum Swap ini, anda dipersulit sedikit dengan cara mengubah angka 0..N-1 diatas menjadi alphabet 'a' sampai 'z' dan ada alphabet yang tidak dipakai (lompat-lompat). Contohnya ada input seperti: "thznlqjgfs" dimana sebenarnya input ini bisa di-translate menjadi percis contoh diatas dan jawabannya adalah 6. Dibawah saya sertakan kode konversi alphabet menjadi permutasi array 0..N-1 untuk memudahkan pencarian cycle.

Ada cara kedua yang lebih mudah, yaitu anda hanya tinggal menghitung berapa banyak swap yang terjadi kalau anda melakukan selection-sort algorithm terhadap input tersebut. Jumlah swap untuk selection sort selalu minimum kalau element yang di-sort adalah unik (tidak ada duplikat). Karena ke-unik-an-nya ini, maka hanya ada satu kemungkinan swap yaitu swap element yang berada di posisi yang salah dengan element yang menempati posisi tersebut. Itulah yang dilakukan selection sort:

Dari kiri ke kanan menukarkan element i (kalau element i tidak pada tempatnya) dengan element yang seharusnya ada disana.

Kode solusi ini bisa dilihat dibawah dengan nama swap-selection-sort.c.

Apakah ada yang menemukan cara lain selain dua cara diatas?

#include <stdio.h>

int m[26], a[26];
char s[27];

int cycle(int i){
    if (a[i]!=i){
        int j = a[i];
        a[i] = i;
        if (a[j]!=j) return 1 + cycle(j);
    }
    return 1;
}

int main(){
    while (gets(s)){
        int i,j=0,res=0;
        for (i=0; i<26; i++) m[i] = 0;
        for (i=0; s[i]; i++) m[s[i]-'a'] = 1;
        for (i=0; i<26; i++) if (m[i]) m[i] = j++;   // mapping alphabet ke 0..N-1
        for (i=0; s[i]; i++) a[i] = m[s[i]-'a'];     // convert alphabet 'a'..'z' di s menjadi angka 0..N-1 di a
        for (i=0; s[i]; i++) res += cycle(i)-1;      // jumlah swap minimum adalah total semua individual cycleLength - 1
        printf("%d\n",res);
    }
}

#include <stdio.h>

char s[27];

int main(){
    while (gets(s)){
        int i,res=0;
        for (i=0; s[i]; i++){
            int j,k=i;
            for (j=i+1; s[j]; j++)
                if (s[j]<s[k]) k = j;
            if (k!=i){
                char t = s[i];
                s[i] = s[k];
                s[k] = t;
                res++;
            }
        }
        printf("%d\n",res);
    }
}

Kembali ke halaman utama