Pembahasan Problem C - Playing With Domino

Diberikan N (N <= 1000) kartu domino yang memiliki angka dari 0 sampai 6. Anda harus menyusun kartu domino tersebut sambung menyambung sepanjang mungkin. Berapakah panjang dari rangkaian domino terpanjang? Untuk penjelasan lebih lengkapnya silahkan lihat di problem statement diatas.

Ini adalah soal tersulit di babak final. Bukan saja sulit dalam hal algoritma apa yang harus dipakai, tetapi juga sulit dalam hal implementasinya. Yang saya maksud sulit dalam hal implementasi bukanlah jumlah baris kodenya, tetapi alur dari kode tersebut. Implementasi saya (setelah melihat solusi juri -> Suhendry) adalah dengan menggunakan 2 fungsi rekursif yang saling memanggil satu sama lain. Selain itu anda juga harus bisa memaintain state global/lokal yang dipakai berulang-ulang dalam pemanggilan rekursi tersebut.

Untuk menyelesaikan soal ini, dibutuhkan pengetahuan tentang Euler Path:

Dalam suatu connected graph, untuk bisa membentuk suatu path menggunakan semua edges yang ada di dalam graph tersebut, graph tersebut haruslah memiliki <= 2 node/vertices yang ber-degree ganjil. Definisi degree suatu node adalah total semua incoming dan outgoing edges untuk node tersebut.

Soal domino ini, bisa diubah menjadi soal Euler Path diatas. Caranya adalah dengan membuat graph (possibly disconnected) yang nodes nya terdiri dari angka 0 sampai 6. Dan edges yang menghubungkan kedua node i dan j diberi weight sebanyak kartu domino (i,j) yang ada di input. Definisi dari disconnected graph adalah jika suatu graph tersebut ada 2 node yang tidak terhubung oleh suatu path.

Dari pengetahuan diatas dan pemahaman soal domino, kita bisa simpulkan hal-hal berikut:

  1. Graph input domino mungkin disconnected. Kita harus memprocess satu-persatu connected graph.
  2. Untuk masing-masing connected graph kita perlu menghitung berapa jumlah node yang ber-degree ganjil?
  3. Diantara semua connected graphs yang mungkin terbentuk, kita harus memilih satu connected graph yang bisa menghasilkan satu path terpanjang. Inilah jawabannya.

Coba anda berhenti sejenak, dan lihat ke-3 kesimpulan diatas. Kira-kira seberapa sulit untuk membuat codenya? Berikut saya bahas implementation issue (cara mengimplementasi-nya):

  1. Untuk mencari satu connected graph, bisa dilakukan dengan cara memilih salah satu node X, dan men-traverse graphnya dan menandai node mana saja yang reach-able dari node X (secara langsung maupun tidak langsung). Graph traversal dapat dilakukan dengan cara BFS (Breadth First Search) atau DFS (Depth First Search). Untuk hal ini, DFS saya rasa jauh lebih mudah.
  2. Untuk menghitung jumlah degree (in-degree + out-degree) dari suatu node X, anda tinggal menghitung berapa banyak edges yang keluar dan masuk node X.
  3. Ini bagian termudah, untuk setiap connected graph catatlah dan update jumlah path terpanjang yang bisa dibentuk.

Bagi beberapa orang, mungkin dengan melihat code akan lebih mengerti daripada melihat penjelasan. Silahkan lihat code dibawah. Dua rekursif function yang saling memanggil satu sama lain adalah removeOddPair() dengan longestPath().

#include <stdio.h>
#include <string.h>

int used[7]; // used[i] == 1 artinya rangkaian domino yang mengandung angka i sudah terpakai
int c[7][7]; // c[i][j] menunjukkan berapa banyak domino i-j
int n; // jumlah domino

// gabungan out-degree dan in-degree dari node x
int degree(int x){
    return c[x][x] + c[x][0] + c[x][1] + c[x][2] +
            c[x][3] + c[x][4] + c[x][5] + c[x][6];
}

int oddDegree(int x){
    return degree(x) % 2 == 1;
}

// menghilangkan odd-pair dari suatu graph dengan cara
// mencari semua kemungkinan dari 2 end-point node ganjil
// dan memilih yang menyisakan rangkaian domino terpanjang
int removeOddPair(int i, int vis[7]){
    int longestPath(int);
    int j,ret=0,temp;

    if (!oddDegree(i)) return longestPath(i);
    if (vis[i]) return 0; else vis[i] = 1;

    for (j=0; j<7; j++)
        if (c[i][j]>0 && i!=j && !vis[j]){
            c[i][j]--; c[j][i]--;
            temp = removeOddPair(j,vis);
            c[i][j]++; c[j][i]++;
            if (temp>ret) ret = temp;
        }
    return ret;
}

// menandai node mana saja yang reachable dari node i
void dfs(int i, int vis[7]){
    int j;
    vis[i] = 1;
    for (j=0; j<7; j++)
        if (c[i][j]>0 && !vis[j])
            dfs(j,vis);
}

// mencoba menghitung rangkaian domino yang memiliki node/angka i
// dengan status domino yang sekarang (global variable c)
int longestPath(int i){
    int oddCount = 0;
    int totDegrees = 0;
    int vis[7] = { 0 };
    int j;

    dfs(i,vis);

    for (j=0; j<7; j++)
        if (vis[j]){
            used[j] = 1; // node j sudah terpakai di salah satu rangkaian
            if (oddDegree(j)) oddCount++;
            totDegrees += degree(j);
        }

    if (oddCount<=2){
		// jika node ganjil kurang dari 2, artinya semua domino 
		// bisa dipakai untuk menjalin suatu rangkaian lurus.
        // total dominoes == total all degrees / 2
        return totDegrees / 2; 
    } else {
		// jika node ganjil > 2, kita coba membuang pair node ganjil
		// dan memilih yang bisa membentuk rangkaian lurus terpanjang
        int res = 0;
        for (j=0; j<7; j++)
            if (oddDegree(j)){
                memset(vis,0,sizeof(vis));
                int temp = removeOddPair(j,vis);
                if (temp > res) res = temp;
            }
        return res;
    }
}

int main(){
    while (scanf("%d",&n)!=EOF){
        int i,a,b,res=0;

		// membuat graph untuk domino
        memset(c,0,sizeof(c));
        for (i=0; i<n; i++){
            scanf("%d %d",&a,&b);
            c[a][b]++;
            if (a!=b) c[b][a]++;
        }

        memset(used,0,sizeof(used));
        for (i=0; i<7; i++) if (!used[i]){ 
			// rangkaian dengan angka i belum digunakan/dicari
			// berapakah rangkaian lurus terpanjang menggunakan node/angka i?
            int length = longestPath(i); 
            if (length > res) res = length;
        }

        printf("%d\n",res);
    }
}