ACM/ICPC Indonesia National Contest 2007

Problem C

Playing With Domino

Time Limit: 1s

A domino is a 2x1 rectangular tile with a line dividing its face into two squares, each with a certain number of dots from zero spots to six spots. As you might know, there are many different games which can be played using dominoes. In most games, dominoes are played by arranging them into a single chain where adjacent dominoes must have matching numbers (see example illustration below).

There are 28 possible faces in a complete set of domino: 0-0, 0-1, 0-2, 0-3, 0-4, 0-5, 0-6, 1-1, 1-2, 1-3, 1-4, 1-5, 1-6, 2-2, 2-3, 2-4, 2-5, 2-6, 3-3, 3-4, 3-5, 3-6, 4-4, 4-5, 4-6, 5-5, 5-6, 6-6. Of course you can play each domino in either direction. For example, you can play 1-6 as 1/6 or 6/1 depending on your need.

Write a program to find the longest chain that can be made from a given set of dominoes. There may be more than one domino with the same face.

Input

Input contains several cases. Each case begins with an integer N (1 <= N <= 1,000) denoting the number of available domino. Each of the following N lines contains a pair of number (0 to 6) which represents the domino. The first number in each pair is always smaller or equal to the second number.

Output

For each case, print in a single line the number of domino used in the longest domino chain.

Sample Input

Sample Output

4
1

Problem Setter: Ang Ing Ing

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:

Graph input domino mungkin disconnected. Kita harus memprocess satu-persatu connected graph.
Untuk masing-masing connected graph kita perlu menghitung berapa jumlah node yang ber-degree ganjil?
- Kalau node dengan degree ganjil berjumlah <= 2, maka semua edges di connected graph ini bisa terpakai untuk membuat satu path yang tanpa putus! (Euler Path)
- Kalau node dengan degree ganjil berjumlah > 2, maka kita harus membuang beberapa edges (sesedikit mungkin) sehingga degree ganjilnya turun menjadi <= 2.
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):

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.
Untuk menghitung jumlah degree (in-degree + out-degree) dari suatu node X, anda tinggal menghitung berapa banyak edges yang keluar dan masuk node X.
- Misalkan anda mengetahui bahwa suatu connected graph jumlah node ber-degree ganjil adalah <= 2. Maka semua edges di dalam connected graph ini bisa membentuk satu path panjang yang lurus tanpa putus. Nah bagaimana cara anda menghitung berapa banyak kartu domino dalam path ini? Jawabannya adalah total degree graph tersebut dibagi dengan 2 (karena satu kartu domino sebenarnya adalah satu edge di dalam graph dan jumlah edge dalam suatu graph itu adalah sama dengan dua kali jumlah degree dari graph tersebut).
- Bagian yang tersulit untuk di-implementasi adalah jika jumlah node ber-degree ganjil > 2. Untuk kasus ini anda harus membuang satu atau beberapa edges sehingga jumlah degree ganjil dari connected graph tersebut menjadi <= 2 sehingga anda bisa menghitung path terpanjang (atau jumlah kartu domino) nya sesuai cara diatas lagi. Berikut adalah caranya:
  Cari node yang ber-degree ganjil dan traverse dengan DFS dari node tersebut sambil membuang edge yang dilalui. Kalau ternyata setelah membuang edge tersebut node tujuan menjadi genap, maka anda berhasil membuang sebuah pasangan node ganjil. Dari sini anda bisa kembali ke nomor 1 diatas, dan mengeceknya lagi. Tetapi kali ini anda yakin bahwa jumlah node yang ber-degree ganjil sudah berkurang, dengan begini anda tidak perlu takut dengan endless loop.
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);
    }
}

Kembali ke halaman utama

Saturday, June 16, 2007

Final Indonesia National Contest 2007 :: Problem C - Playing With Domino