Saturday, June 16, 2007

Final Indonesia National Contest 2007 :: Problem H - Tree Median

ACM/ICPC Indonesia National Contest 2007

Problem H

Tree Median

Time Limit: 3s


A tree is a connected graph containing no cycles. A vertex is called a median vertex if the total cost to reach all vertices is minimal. There could be more than one median vertex in a tree, that's why we define median as the set of all median vertices. To find median in a tree with small number of vertices is fairly easy task as you can solve this by a simple brute force program.

In the left figure, we can see a weighted tree with 5 vertices. The tree median is {B} because the total cost from vertex B to all other vertices is minimal.

B-A = 2    B-D = 7
B-C = 1    B-E = 7 + 5 = 12

TOTAL = 2 + 1 + 7 + 12 = 22

What if the number of vertices is quite large? This might be a problem since brute force program cost too much time. Given a weighted tree with N vertices, output the total cost to reach all vertices from its median.

Input

Input consists of several cases. Each case begins with an integer n (1<= n <= 10,000) denoting the number of vertices in a tree. Each vertex is numbered from 0...n-1. Each of the next n-1 lines contains three integers: a, b, and w (1<= w <= 100), which means a and b is connected by an edge with weight w.

Input is terminated when n is equal to 0. This input should not be processed.

Output

For each case, output a line containing the sum of cost of path to all other vertices from the tree median.

Sample Input

5
0 1 2
1 2 1
1 3 7
3 4 5
6
0 1 1
1 2 4
2 3 1
3 4 4
4 5 1
0

Sample Output

22
21


Problem Setter: Suhendry Effendy



Pembahasan Problem H - Tree Median

Diberikan suatu graph berbentuk tree. Graph ini memiliki N (1 <= N <= 10000) nodes dan N-1 edges yang mempunyai weight W (1 <= W <= 100). Carilah satu dari N node untuk dijadikan "root" sehingga total distance dari root ke semua nodes adalah minimum. Untuk contoh jelasnya (dipandu dengan gambar) silahkan lihat problem statement diatas.

Salah satu cara menyelesaikannya adalah dengan bruteforce, yaitu dengan mencoba satu-persatu node untuk dijadikan "root" dan menghitung total distance dari root tersebut ke semua nodes. Kendalanya adalah bagaimana cara menghitung total distance dari root ke semua node dalam O(1)? Berikut adalah cara yang saya ketahui, yaitu dengan menggeser root yang sekarang ke node tetangganya dan meng-update total distance ke semua nodes. Dibawah adalah langkah-langkah untuk melakukannya:

Pilih salah satu node untuk dijadikan "root", misalkan node 0. Lalu pre-calculate semua distance weight dan count nodes dari root ke semua nodes. Definisi distance weight adalah berapa total distance untuk node tersebut beserta sub-tree dari node tersebut. Definisi count nodes adalah berapa banyak node anak yang dimiliki node tersebut (termasuk node itu sendiri). Pre-calculate ini bisa dilakukan dengan DFS (rekursi). Note: untuk input yang besar, misalkan N = 10000, maka kedalaman rekursi dari DFS ini akan menyebabkan stack-overflow kecuali anda sudah mengubah setting compiler untuk stack size menjadi lebih besar (32 MB cukup).

Setelah pre-calculate distance weight dan count nodes dari node 0, otomatis anda bisa mengetahui total distance dari root ini ke semua nodes dalam O(edges dari node 0). Lalu anda bisa melakukan DFS (rekursi) ke dua yang bertugas untuk menggerakan "root" (yang sekarang di node 0) ke semua node lainnya sembari mengupdate tabel distance weight dan count nodes supaya anda bisa tetap menghitung total distance dari root yang baru ke semua nodes juga dalam O(edges dari root tersebut).

Jadi, total complexity dari algoritma ini adalah O(N) untuk pre-calculate distance dan count. O(N) untuk menggeser "root" ke N-1 nodes yang lain sambil mengcalculate distance nya dalam O(edges dari root node baru tersebut). Dengan amortized analysis, complexity dari calculate total distance untuk suatu root adalah O(1), karena ada N-1 edges total dan N nodes.
Code untuk problem ini saya pecah menjadi dua: tree-rec.cpp dan tree-stack.cpp. Keduanya mengimplement code diatas. Tetapi yang menggunakan rekursi (tree-rec.cpp) hanya bisa untuk N yang kecil (karena terbatas stack size di compiler, kecuali anda naikkan stack size compiler anda). Untuk code yang menggunakan stack buatan (tree-stack.cpp) bisa menghandle input lebih besar tanpa mengubah settingan compiler karena data dialokasikan di heap memory.

Kedua code menggunakan STL map, set, vector. Kalau tidak, maka codingnya akan jauh lebih panjanggggg..... Anda bisa menggunakan problem ini untuk belajar STL maupun rekursi dengan stack buatan.

Untuk Andrian Kurniady: sharing donk algo "DP problem I" nya gimana? pake rekursi topdown? apa bottom up?

#include <stdio.h>
#include <string.h>
#include <set>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

#define FOREACH(it,arr) for (__typeof((arr).begin()) it=(arr).begin(); it!=(arr).end(); it++)

vector<map<int,int> > con;
vector<long long> dist;
vector<int> cnt;
long long res;
int n;

void calcCnt(int i, int p){
    cnt[i]++;
    dist[i] = 0;
    FOREACH(it,con[i]){
        int j = it->first;
        int w = it->second;
        if (j!=p){
            calcCnt(j,i);
            cnt[i] += cnt[j];
            dist[i] += cnt[j] * w + dist[j];
        }
    }
}

void rec(int i, int p, int c, long long v){
    long long sum = (p==-1)? 0 : (v + c * con[p][i]);
    FOREACH(it,con[i]){
        int j = it->first;
        int w = it->second;
        if (j!=p) sum += cnt[j] * w + dist[j];
    }
    res = min(res, sum);

    FOREACH(it,con[i]){
        int j = it->first;
        int w = it->second;
        if (j!=p) rec(j, i, n-cnt[j], sum-(dist[j] + cnt[j]*w));
    }
}

int main(){
    while (scanf("%d",&n)!=EOF && n){
        con = vector<map<int,int> >(n);
        for (int i=1,a,b,w; i<n; i++){
            scanf("%d %d %d",&a,&b,&w);
            con[a][b] = w;
            con[b][a] = w;
        }

        cnt = vector<int>(n);
        dist = vector<long long>(n);
        calcCnt(0,-1);

        res = 1000000000000LL;
        rec(0,-1,0,0);
        printf("%lld\n",res);
    }
}
#include <stdio.h>
#include <string.h>
#include <set>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

#define FOREACH(it,arr) for (__typeof((arr).begin()) it=(arr).begin(); it!=(arr).end(); it++)

vector<map<int,int> > con;
vector<long long> dist;
vector<int> cnt;
long long res;
int n;

void calcCnt(int i, int p){
    vector<pair<int,int> > stk;
    vector<bool> vis;
    stk.push_back(make_pair(i,p));
    vis.push_back(false);
    while (stk.size()>0){
        i = stk.back().first;
        p = stk.back().second;

        if (!vis.back()){
            vis.back() = true;
            FOREACH(it,con[i]){
                int j = it->first;
                int w = it->second;
                if (j!=p){
                    stk.push_back(make_pair(j,i));
                    vis.push_back(false);
                }
            }
        } else {
            cnt[i] = 1;
            dist[i] = 0;
            FOREACH(it,con[i]){
                int j = it->first;
                int w = it->second;
                if (j!=p){
                    cnt[i] += cnt[j];
                    dist[i] += cnt[j] * w + dist[j];
                }
            }
            stk.pop_back();
            vis.pop_back();
        }
    }
}

struct ipcv {
    long long i,p,c,v;
};

void rec(int i, int p, int c, long long v){
    vector<ipcv> stk;
    vector<bool> vis;
    stk.push_back((ipcv){i,p,c,v});
    vis.push_back(false);
    while (stk.size()>0){
        ipcv t = stk.back();
        i = t.i;
        p = t.p;
        c = t.c;
        v = t.v;

        if (!vis.back()){
            vis.back() = true;

            long long sum = (p==-1)? 0 : (v + c * con[p][i]);
            FOREACH(it,con[i]){
                int j = it->first;
                int w = it->second;
                if (j!=p) sum += cnt[j] * w + dist[j];
            }
            res = min(res, sum);

            FOREACH(it,con[i]){
                int j = it->first;
                int w = it->second;
                if (j!=p){
                    stk.push_back((ipcv){j, i, n-cnt[j], sum-(dist[j] + cnt[j]*w)});
                    vis.push_back(false);
                }
            }
        } else {
            stk.pop_back();
            vis.pop_back();
        }
    }
}

int main(){
    while (scanf("%d",&n)!=EOF && n){
        con = vector<map<int,int> >(n);
        for (int i=1,a,b,w; i<n; i++){
            scanf("%d %d %d",&a,&b,&w);
            con[a][b] = w;
            con[b][a] = w;
        }

        cnt = vector<int>(n);
        dist = vector<long long>(n);
        calcCnt(0,-1);

        res = 1000000000000LL;
        rec(0,-1,0,0);
        printf("%lld\n",res);
    }
}

Kembali ke halaman utama

Final Indonesia National Contest 2007 :: Problem G - Sultan's Land

ACM/ICPC Indonesia National Contest 2007

Problem G

Sultan's Land

Time Limit: 1s


Sultan Al-Bandar, the ruler of Old West Sumatra Sultanate, has decided to give his land to his only son. Although the Sultan believes that his son will not misuse the land for some bad purposes, he still has some doubts on his son's capability to rule the land. Therefore, he decided to give his son a test, a puzzle test.

The Sultan drew N x N grids (virtually of course) on his land where any two adjacent grid intersections would have the same length. Then he placed some pillars on the land where each pillar was placed at one intersection. Then he summoned his son to come to the land.

"Well, my dear son, if you are to choose four pillars to form an area where each pillar serves as a corner of that area, how many possible selections are there?" asked the Sultan. His son replied him with a big smile. Just at the time the Sultan remembered that his son works for the Sultanate's Advance Combinatorial Ministry, so this problem might be too easy. Then he quickly added, "Oh! Each side of the area should be parallel to the grid I have drawn before."


To tell the truth, the Sultan himself actually had not prepared any answers since he spontaneously asked his after the big smile. Help this Sultan by writing a program to count how many possible selections can be made by applying the rules above.

Input

The input contains several test cases. Each case begins with two integers, N (2 <= N <= 100) the grid-size, and P (2 <= P <= N2) the number of pillars. Each grid will be numbered from 1 to N. The next P following lines each will contains two integers: r and c (1 <= r, c <= N) the row and column where the pillar is placed.

Input is terminated by a line containing two zeroes. This input should not be processed.

Output

For each case, output a line containing the number of possible selections can be made to form an area whose sides are parallel to the grid.

Sample Input

7 10
1 3
1 6
2 2
2 5
4 2
4 5
5 1
5 6
6 3
6 6
3 6
2 1
2 2
2 3
3 1
3 2
3 3
0 0

Sample Output

2
3


Problem Setter: Suhendry Effendy


Pembahasan Problem G - Sultan's Land

Diberikan banyak pilar-pilar berupa titik (1<=x<=100, 1<=x<=100) dalam suatu kartesian sistem. Suatu persegi bisa dibentuk oleh 4 pillar yang terletak di 4 sudut persegi tersebut. Berapa banyak persegi yang mungkin dibentuk?

Cara yang paling gampang adalah bruteforce 4 titik: untuk setiap 4 titik, dicek apakah membentuk persegi? kalau iya, maka tambahkan ke hasil. Tapi sayangnya jumlah titik bisa mencapai 100 x 100 dimana nCk(10000, 4) = 416416712497500 itu sangat besar. Sudah pasti kena time limit exceeded.

Cara kedua adalah juga bruteforce, tetapi sedikit lebih pintar: untuk setiap kombinasi 2 baris, carilah berapa banyak persegi yang bisa dibentuk? Banyaknya kombinasi baris yang mungkin adalah nCk(100,2) = 4950 kemungkinan. Untuk setiap kombinasi 2 baris, anda dapat menghitung kemungkinan persegi yang bisa dibuat dengan cara menghitung banyak nCk(titik yang bersekutu di kolom, 2). Dengan demikian, complexity dari bruteforce ini adalah O(N^3). Untuk implementasinya silahkan lihat kode rect.c dibawah.

Anda bisa mempercepat perhitungan jumlah titik yang bersekutu di kolom untuk baris i dan baris j dengan menggunakan 2 long long variable dan menghitung jumlah persekutuan kolomnya dengan melakukan bitwise operation AND untuk baris i dan j. Lalu untuk menghitung berapa bit yang ON bisa dilakukan dengan O(1) meskipun kodenya sangatlah criptic, anda bisa lihat di bithack article ini. Sehingga complexity dari bruteforce turun menjadi O(N^2). Bagaimanapun, algo brutforce O(N^3) diatas sudah cukup cepat untuk problem ini.

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

int N,P,pillar[100][100];

int main(){
    int i,j,k,r,c,res;
    while (scanf("%d %d",&N,&P)!=EOF && (N||P)){
        memset(pillar,0,sizeof(pillar));
        for (i=0; i<P; i++){
            scanf("%d %d",&r,&c);
            pillar[r-1][c-1] = 1;
        }

        res = 0;
        for (i=0; i<N; i++)
            for (j=i+1; j<N; j++){
                int c = 0;
                for (k=0; k<N; k++)
                    if (pillar[i][k] && pillar[j][k])
                        c++;

                res += c*(c-1)/2; // nCk(c,2) = c diambil 2 = c*(c-1)/2
            }
        printf("%d\n",res);
    }
}

Kembali ke halaman utama

Final Indonesia National Contest 2007 :: Problem F - Jakarta Traffic Jam

ACM/ICPC Indonesia National Contest 2007

Problem F

Jakarta Traffic Jam

Time Limit: 1s


The traffic in Jakarta is terrible. Streets in Jakarta may get congested with traffic jam during rush hour. This means it will take longer time to pass through those streets since you can only drive half your speed during rush hours. Therefore, you need to plan your trip carefully if you don't want to be late for your activities.

For example, consider a street from P to Q which will need 20 minutes to drive in a normal time. The street is congested with traffic at 15:00 until 16:00. Now, let's consider some sample conditions that might happen related to rush hours:
  1. If you start your trip 15 minutes before the rush hour (start from P at 14:45), then when the traffic starts to get congested, you can only drive half of your normal speed, thus, you will need 10 (2x5) more minutes to reach Q. Thus, the total time you need to go from P to Q is 15 + 10 = 25 minutes.

  2. If you start your journey at the last 5 minutes of the rush hour (start from P at 15:55), the distance you have reached in the first 5 minutes is equal to the distance you can reach in 2.5 minutes during normal hours. You will need 17.5 more minutes to get to Q. Thus, the total time you need to go from P to Q is 5 + 17.5 = 22.5 minutes.

  3. Other combinations of (a) and (b).
Given a map which has at most N intersections and M streets, find out how many minute(s) you need to go from s to d. You want to reach d as soon as possible without wasting any seconds or microseconds, or even nanoseconds.

Input

The input contains several test cases. Each case begins with two integers N (1<= N <=20) and M. Each intersection will be numbered from 0 to N-1.

The first three integers P, Q, and T (1<= T <=50) in each of the following M line means there is a street connecting intersection P to intersection Q which need T minutes driving in normal time. These integers will be followed by either character 'N' or 'R'. 'N' will not be followed by any characters and it means the street has no rush hours. 'R' will be followed by the starting and ending time of the rush hour in the format of hh:mm (00:00 to 23:59). No rush hours will rollover past midnight.

The last line of each case contains s - your starting point, d - your destination and w - current time.

Input is terminated by a line containing two zeroes. This line should not be processed.

Output

For each case, output a line containing the minimum time you need to go from s to d in minutes. Your output should always contain two digits after the decimal point.

Sample Input

2 1
0 1 20 R 15:00 16:00
0 1 14:45
3 3
0 1 20 R 15:00 16:00
1 3 10 N
2 1 35 R 16:30 17:00
0 2 15:55
0 0

Sample Output

25.00
72.50


Problem Setter: Danny Gunawan


Pembahasan Problem F - Jakarta Traffic Jam

Soal ini secara algoritma lebih mudah daripada soal Taxi di babak penyisihan, tetapi bobotnya dipindahkan ke matematika!

Ada N persimpangan dan M jalan. Setiap jalan mempunyai jam kemacetan dimana kalau anda melalui jalan tersebut saat macet maka kecepatan anda akan menurun setengah kecepatan awal. Pertanyaannya, berapakah waktu tercepat dari s ke d?

Anda tidak perlu A* seperti soal Taxi di penyisihan, algoritma umum Dijkstra bisa diterapkan untuk memecahkan soal ini karena anda hanya perlu meminimalisasi waktu dari source ke destination. Tepat seperti apa yang Dijkstra lakukan. Bagaimanapun juga, A* adalah versi superior dan kode nya pun tidak jauh beda dengan Dijkstra dan mungkin lebih gampang di implementasi. Untuk belajar A*, anda bisa buka pembahasan soal penyisihan Taxi. Untuk belajar Dijkstra anda bisa lihat pembahasan soal ini.

Saya akan coba menjelaskan Dijkstra secara kasarnya saja. Untuk cara formalnya, anda bisa baca dari buku Introduction to Algorithms atau cari sendiri lewat Google :)

Cara Dijkstra bekerja adalah dengan selalu memprocess node yang memiliki waktu tercepat dan berhenti saat semua node sudah diprocess. Dalam memprocess suatu node, node tersebut akan meng-update waktu yang dibutuhkan untuk tiba di node lain dari node tersebut. Saat suatu node diprocess, maka waktu tercepat untuk sampai ke node tersebut sudah diketahui dengan pasti. Silahkan lihat dibawah untuk implementasinya.

#include <stdio.h>

// ini adalah function mematikan dari soal ini, membutuhkan sedikit if dan else + rekursi :)
double calculate(double waktuSekarang, double lamaPerjalanan, int rushStart, int rushEnd){
    double waktuTiba = waktuSekarang + lamaPerjalanan;

    if (rushStart <= waktuSekarang && waktuSekarang <= rushEnd){
        // waktu mulainya kena rush hour, case yang B

        // berapa lama lagi sampai rush hournya berhenti
        double lamanyaRushHour = rushEnd - waktuSekarang;

        if (lamanyaRushHour > lamaPerjalanan * 2){
            // sepanjang anda berjalan, macet melulu
            return lamaPerjalanan * 2;      
        } else {
            // ditengah-tengah perjalanan anda berhasil lolos dari rush hour
            double jarakTersisa = lamaPerjalanan - lamanyaRushHour/2;
            return lamanyaRushHour + jarakTersisa;
        }
    } else if (waktuSekarang <= rushStart && rushStart <= waktuTiba){
        // ditengah perjalanan anda terkena rush hour, case yang A
        
        // anda bisa jalan dengan kecepatan normal saat belum terkena rush hour
        double jalanNormal = rushStart - waktuSekarang;    
        
        // disinilah anda mulai terkena rush hour dan kalau dilihat, anda mirip Case B diatas
        // yaitu anda memulai dengan terkena rush hour! maka tinggal panggil aja calculate() sekali lagi ;)
        return jalanNormal + calculate(
            waktuSekarang + jalanNormal,    // waktu sekarang sudah bertambah sebanyak perjalanan yang ditempuh
            lamaPerjalanan - jalanNormal,   // lama perjalanan berkurang sebanyak yang ditempuh
            rushStart, rushEnd);            // waktu rush hour start dan end masih tetap sama
    } else {
        return lamaPerjalanan;              // anda mujur sekali tidak terkena rush hour
    }
}

int getTime(){
    int hh,mm;
    scanf("%d:%d",&hh,&mm);
    return hh*60 + mm;
}

int main(){
    int travel_time[20][20];     // travel_time[i][j] waktu normal berjalan dari i ke j
    int rush_start[20][20];      // rush_start[i][j] waktu mulai rush hour untuk jalan i ke j
    int rush_end[20][20];        // rush_end[i][j] waktu selesai rush hour untuk jalan i ke j
    double waktu[20];            // waktu[x] adalah waktu tercepat untuk sampai di node x
    int N,M,i,j,k,P,Q,T,s,d,pq[20],pqSize;
    char NR[2];

    while (scanf("%d %d",&N,&M)!=EOF && (N||M)){
        memset(travel_time,-1,sizeof(travel_time));
        memset(rush_start,-1,sizeof(rush_start));
        memset(rush_end,-1,sizeof(rush_end));

        for (i=0; i<M; i++){
            scanf("%d %d %d %s",&P,&Q,&T,NR);
            travel_time[P][Q] = travel_time[Q][P] = T;
            if (NR[0]=='R'){
                rush_start[P][Q] = rush_start[Q][P] = getTime();
                rush_end[P][Q] = rush_end[Q][P] = getTime();
            }
        }
        scanf("%d %d",&s,&d);

        for (i=0; i<N; i++){
            pq[i] = i;           // masukkan semua node ke Priority Queue
            waktu[i] = 1e10;     // waktu di semua node adalah tak terhingga
        }
        waktu[s] = getTime();    // set waktu dari starting intersection s
        
        // Dijkstra, process berdasarkan waktu yang paling pagi
        for (pqSize=N; pqSize>0; pqSize--){

            // cari node terpagi yang belum diprocess
            k = 0;
            for (i=1; i<pqSize; i++)
                if (waktu[pq[i]] < waktu[pq[k]])
                    k = i; // update k kalau ketemu node yang lebih pagi

            i = pq[k];               // pq[k] adalah node dengan waktu terpagi, simpan di i
            pq[k] = pq[pqSize-1];    // buang node k dari priority queue

            // process node i (node yang terpagi saat ini)
            for (j=0; j<N; j++){
                if (travel_time[i][j]!=-1){
                    double duration = travel_time[i][j];
                    
                    if (rush_start[i][j]!=-1){
                        duration = calculate(    // hitung durasi waktu yang diperlukan dari intersection i ke j
                            waktu[i],            // waktu saat ini
                            travel_time[i][j],   // waktu perjalanan normal dari i ke j
                            rush_start[i][j],    // jam mulai rush hour untuk jalan i ke j
                            rush_end[i][j]);     // jam selesai rush hour untuk jalan i ke j
                    }

                    // jika kita bisa travel ke j dari i lebih cepat, maka update waktu j
                    if (waktu[i] + duration < waktu[j]){
                        waktu[j] = waktu[i] + duration;
                    }
                }
            }
        }

        // waktu tercepat sampai di destination d adalah waktu di d dikurang dengan waktu di s
        printf("%.2lf\n", waktu[d] - waktu[s]);
    }
}

Kembali ke halaman utama

Final Indonesia National Contest 2007 :: Problem E - Panda Number

ACM/ICPC Indonesia National Contest 2007

Problem E

The Adventure in Panda Land Part I: Panda Number

Time Limit: 1s


In Panda Land, pandas have their own numeral system to represent a number. Surprisingly, this numeral system is similar to the famous Roman Numerals in our ancient civilization. Although pandas are aware about numeral system, they can not write (imagine how can a panda write!). Instead, they cut and arrange bamboos to form a number.

Decimal Panda Number Required Bamboo
1I1
5V2
10X2
50L2
100C3
500N3
1,000M4
5,000E4
10,000W4
50,000F3
100,000Y3
500,000K3
1,000,000H3
5,000,000T2
10,000,000A3
  These are the production rules of Panda Number:
  • Letters which represent powers-of-ten (I, X, C, M, W, Y, H, A) can be repeated at most three times. The others (V, L, N, E, F, K, T) can not be repeated.
  • If one or more letters are placed after another letter of greater value, add that amount. The letters should be written in descending order from the largest to the least value. For example:
    FXVIII = 50000 + 10 + 5 + 1 + 1 + 1 = 50018
  • If a letter is placed before another letter of greater value, subtract that amount. Only subtract one letter from another. For example:
    XIV = 10 + (5 - 1) = 14
    CIX = 100 + (10 - 1) = 109
    MECIX = (5000 - 1000) + 100 + (10 - 1) = 4109
  • Only powers-of-ten can be used to subtract a value (that is, you can subtract I from V, or X from L, but not V from X (V is not powers-of-ten.)
  • Do not subtract a letter from one that is more than 10 times greater (that is, you can subtract I from X, but not I from L -- there is no such number as IL.)

The aforementioned rules imply that there is exactly one representation in Panda Number for each number in decimal system.

Unlike those Roman Numerals, pandas do recognize zero and negative number (which prove pandas are more advanced than our ancient Romans). To represent a negative number, they add one bamboo as a negative sign in front of the letters. Zero is a special number which doesn't fall into any rules above. To form a zero, pandas need five bamboos.

The number of bamboos needed to form a number is the sum of required bamboos for each letter that appears in that number. For Example:
4108 = 4000+100+8 = (5000-1000)+100+5+1+1+1 = MECVIII (16 bamboos).
4109 = 4000+100+9 = (5000-1000)+100+(10-1) = MECIX (14 bamboos).
-205 = [-], 200+5 = 100+100+ 5 = -CCV (9 bamboos)

Given two numbers A and B, find out how many bamboos needed by panda to form (remember, they can't write) all number between A and B inclusively.

Input

The input begins with a single positive integer T in a line indicating the number of test cases. Each case contains two numbers A and B (-25,000,000 <= A <= B <= 25,000,000) in a line.

Output

For each case, print in a single line the number of needed bamboos to form all numbers between A and B (inclusive).

Sample Input

7
-1 1
4018 4019
-25000000 25000000
-100 -57
-100 0
0 100
43 100

Sample Output

8
28
2121000021
399
778
678
434


Problem Setter: Evan Leonardi


Pembahasan Problem E - Panda Number

Anda diberikan sistem angka untuk Panda yang mirip sistem angka pada Roman. Diperlukan jumlah bambu tertentu untuk membentuk suatu angka. Untuk range A..B (-25 juta <= A < B < 25 juta), anda diminta untuk menghitung berapakah jumlah bambu yang diperlukan untuk membentuk semua angka dari A sampai B? Untuk lebih jelasnya silahkan lihat problem statement diatas.

Menurut pemahaman saya, setiap angka di decimal number system bisa diubah menjadi roman/panda system secara terpisah berdasarkan letak dari significant digit masing-masing angka tersebut.

Contoh:

3      = 3 * 10^0  -> III
30     = 3 * 10^1  -> XXX
300    = 3 * 10^2  -> CCC
3000   = 3 * 10^3  -> MMM
30000  = 3 * 10^4  -> WWW
...

4      = 4 * 10^0  -> IV
40     = 4 * 10^1  -> XL
400    = 4 * 10^2  -> CN
4000   = 4 * 10^3  -> ME
40000  = 4 * 10^4  -> WF
...

8      = 8 * 10^0  -> VIII
80     = 8 * 10^1  -> LXXX
800    = 8 * 10^2  -> NCCC
8000   = 8 * 10^3  -> EMMM
80000  = 8 * 10^4  -> FWWW
...

dan yang lain dan seterusnya

Dari contoh diatas, terlihat pattern:
Sebenarnya I,X,L,C,M,W,Y,H,A itu semua sama saja, yang membedakannya adalah pangkat 10 nya, begitu pula dengan V,L,N,E,F,K,T.
Jadi, format angka 80 itu sama saja dengan angka 80000, hanya saja L diganti F, dan X diganti W. Otomatis kita tinggal membuat tabel:
Untuk pangkat 10 tertentu, apakah simbol yang bersangkutan? atau
Untuk pangkat 10 tertentu, berapa bambu yang dibutuhkan?
Untuk soal ini, kita tidak perlu tahu simbolnya, tapi hanya jumlah bambunya saja. Anda bisa lihat function bamboo(d,p) dibawah untuk menghitung berapa bamboo yang diperlukan untuk digit d dimana digit tersebut ada di posisi 10^p. Contoh:
Untuk menghitung banyak bambu untuk angka 80000 = 8 * 10^4, tinggal panggil bamboo(8,4).

Karena range A, B begitu besar, maka anda perlu mem-precalculate hasil untuk semua range. Ini bisa dilakukan dengan menggunakan dynamic programming (membuat tabel dp) yang meng-akumulasi jumlah bamboo dari 1 sampai n. Untuk menghitung jumlah bambu dari range A sampai B, anda tinggal menghitung dp[B] - dp[A-1] dimana A dan B harus positive. Kalau A atau B adalah negative atau nol, maka diperlukan sedikit if-else. Lihat dibawah untuk semua kemungkinan A dan B beserta perhitungannya.

Ada cara untuk menghitung akumulasi bambu dari 1..n on-the-fly hanya dalam O(banyak nya digit di input ^ 2). Saya diberi tahu cara ini oleh Stephen Kohar dari tim NoMoreAC. Caranya adalah (nanti saya jelaskan), kalian coba liat source code nya dulu dech dibawah (dengan nama panda-on-the-fly.c). Function bamboo dan main function tidak berubah sama sekali, yang berubah adalah dp[i] tidak lagi di-precalculate, tapi dihitung on-the-fly dp(i).

#include <stdio.h>
#include <math.h>

#define MAXN 25000000

int need[8][2] = { {1,2}, {2,2}, {3,3}, {4,4}, {4,3}, {3,3}, {3,2}, {3,0} };

// berapa bamboo yang diperlukan untuk digit d dimana digit tersebut ada di 10^p
int bamboo(int d, int p){
    switch (d){
        case 0: return 0; // special case
        case 1: return 1 * need[p][0] + 0 * need[p][1]; // I
        case 2: return 2 * need[p][0] + 0 * need[p][1]; // II
        case 3: return 3 * need[p][0] + 0 * need[p][1]; // III
        case 4: return 1 * need[p][0] + 1 * need[p][1]; // IV
        case 5: return 0 * need[p][0] + 1 * need[p][1]; // V
        case 6: return 1 * need[p][0] + 1 * need[p][1]; // VI
        case 7: return 2 * need[p][0] + 1 * need[p][1]; // VII
        case 8: return 3 * need[p][0] + 1 * need[p][1]; // VIII
        case 9: return 1 * need[p][0] + 0 * need[p][1] + 
                       1 * need[p+1][0] + 0 * need[p+1][1]; // IX
    }
}

int dp[MAXN+1]; // dp[i] adalah jumlah bamboo untuk membentuk angka angka dari 1 sampai i

void precalculate(){
    int i,j,k,p,base,need;

    // precalculate table dp untuk menghindari time limit
    // perhitungan DP ini memang agak sulit dijelaskan maupun dimengerti
    // tetapi dengan pengalaman dan latihan, anda akan bisa memahaminya :D
    dp[0] = 0;
    for (p=0,i=1; p<9; p++,i*=10){
        for (j=0; j<10; j++){
            if (i*j > MAXN) break;
            base = i*j;
            need = bamboo(j,p);
            for (k=0; k<i; k++){
                if (base+k > MAXN) break;
                dp[base+k] = need + dp[k];
            }
        }
    }

    for (i=1; i<=MAXN; i++) dp[i] += dp[i-1];               // akumulasi
}

int main(){
    int T,A,B;

    precalculate();

    scanf("%d",&T);
    while (T--){
        scanf("%d %d",&A,&B);
        if (A<0){
            A = abs(A);
            if (B<0){
                B = abs(B);
                printf("%d\n", dp[A] - dp[B-1] + (A-B+1));  // A <= B < 0
            } else {
                printf("%d\n", A + dp[A] + 5 + dp[B]);      // A < 0 <= B
            }
        } else { // 0 <= A <= B
            if (A==0){
                printf("%d\n", dp[B] + 5);                  // 0 == A <= B
            } else {
                printf("%d\n", dp[B] - dp[A-1]);            // 0 < A <= B
            }
        }
    }
}
#include <stdio.h>
#include <math.h>

#define MAXN 25000000

int need[8][2] = { {1,2}, {2,2}, {3,3}, {4,4}, {4,3}, {3,3}, {3,2}, {3,0} };

// berapa bamboo yang diperlukan untuk digit d dimana digit tersebut ada di 10^p
int bamboo(int d, int p){
    switch (d){
        case 0: return 0; // special case
        case 1: return 1 * need[p][0] + 0 * need[p][1]; // I
        case 2: return 2 * need[p][0] + 0 * need[p][1]; // II
        case 3: return 3 * need[p][0] + 0 * need[p][1]; // III
        case 4: return 1 * need[p][0] + 1 * need[p][1]; // IV
        case 5: return 0 * need[p][0] + 1 * need[p][1]; // V
        case 6: return 1 * need[p][0] + 1 * need[p][1]; // VI
        case 7: return 2 * need[p][0] + 1 * need[p][1]; // VII
        case 8: return 3 * need[p][0] + 1 * need[p][1]; // VIII
        case 9: return 1 * need[p][0] + 0 * need[p][1] + 
                       1 * need[p+1][0] + 0 * need[p+1][1]; // IX
    }
}

int dp(int n){
    int p=0, digit=n, power=1, remaining=0, result=0, i;

    if (n<=0) return 0;
    while (digit>9) power *= 10, digit /= 10,  p++;
    remaining = n - digit*power;
    result = dp(remaining) + bamboo(digit,p) * (remaining+1) + dp(power-1) * digit;
    for (i=1; i<digit; i++) result += bamboo(i,p) * power;
    return result;
}

int main(){
    int T,A,B;

    scanf("%d",&T);
    while (T--){
        scanf("%d %d",&A,&B);
        if (A<0){
            A = abs(A);
            if (B<0){
                B = abs(B);
                printf("%d\n", dp(A) - dp(B-1) + (A-B+1));  // A <= B < 0
            } else {
                printf("%d\n", A + dp(A) + 5 + dp(B));        // A < 0 <= B
            }
        } else { // 0 <= A <= B
            if (A==0){
                printf("%d\n", dp(B) + 5);                    // A==0, A <= B
            } else {
                printf("%d\n", dp(B) - dp(A-1));            // 0 < A <= B
            }
        }
    }
}

Kembali ke halaman utama

Final Indonesia National Contest 2007 :: Problem D - Email from The Professor

ACM/ICPC Indonesia National Contest 2007

Problem D

Email from The Professor

Time Limit: 1s


Being a judge in a programming contest like ACM/ICPC INC sometimes means trouble. They have to prepare challenging and interesting problems, and most importantly, they should keep the problems secret before the contest day. Usually, the judges use email as a main device to communicate and discuss on problems. As you might think, this is not a secure way to communicate confidentially since emails can be unintentionally sent to unexpected recipients, e.g. his/her student or worst, the contestant.

Considering those issues, Prof. Nash V. Ruhdney, one of the judges, has proposed a method to communicate confidentially amongst judges. Supposed there is a message of length n, write the message in a rectangle of width k, row by row, and read it column by column in a permuted order. The order of columns will then be the encryption key for the message. For example,
Message     : I am Prof. Nash V. Ruhdney
Key         : 3 7 4 1 2 6 5
Plain Text  : I   a m   P r
              o f .   N a s
              h   V .   R u
              h d n e y * *     note: '*' means blank and is not part of the message.
Column      : 11112222333344445556667777
Cipher Text : m .e N yIohha.VnrsuPaR f d
Prof. Nash then send this encrypted message (cipher text) through email, while the encryption key is sent through other means, such as phone or SMS. This way he can reduce the risk of erroneously sent email.

Of course there is no way that the professor would use paper & pencil to encrypt those messages. So, would you be kind to help him while he is preparing a nice problem for you?

Input

Input consists of several test cases. The first line of each test case contains a message of length n (1 <= n <= 1,000) in a line (the message consists of ASCII characters). The next line contains k, (1 <= k <= 1,000) the width of rectangle, followed by k integer(s) separated by a single space, the permutation of 1 to k which represents the encryption key.

Output

For each message, output the encrypted message in a single line.

Sample Input

I am Prof. Nash V. Ruhdney
7 3 7 4 1 2 6 5
give no easy problem this year.
5 1 4 3 2 5

Sample Output

m .e N yIohha.VnrsuPaR f d
gnso  .eepeiav  lheioybty armsr


Problem Setter: Suhendry Effendy


Pembahasan Problem D - Email from the Professor

Diberikan string plaintext, dan sebuah key untuk meng-enkripsi-nya. Cara meng-enkripsi plaintext tersebut adalah dengan me-wrap around plaintext dengan width K (sehingga tercipta K columns of characters dan R baris). Lalu pengkodeannya adalah dengan membaca column (a1,a2,a3..aK) dari baris paling atas ke paling bawah dimana a1..aK adalah permutasi dari 0..K-1.

Soal ini hanya men-simulasikan apa yang ada di soal, jadi pintar-pintarnya kalian membuat program tanpa bug. Algoritmanya simple, anda cukup melakukan inverse dari key yang diberikan, lalu tinggal anda print per kolom dari baris pertama sampai terakhir, tetapi hati-hati dengan baris terakhir, bisa jadi sudah melebihi panjang string inputnya. Untuk lebih jelasnya lihat source code dibawah.

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

int idx[1000], inv[1000];
char s[1001];

int main(){
    while (gets(s)){
        int i,j,k,row,len=strlen(s);

        scanf("%d",&k);
        for (i=0; i<k; i++)
            scanf("%d",&idx[i]);
        scanf("\n");                             // baca ending new line

        for (i=0; i<k; i++)
            inv[idx[i]-1] = i;                   // inverse idx, tampung di inv

        row = (len+k-1)/k;                       // berapa baris yang tercipta, dibulatkan keatas

        for (i=0; i<k; i++)                      // looping pertama, untuk setiap kolum dari 0..k-1
            for (j=0; j<row; j++){               // looping kedua, print dari baris atas sampai bawah
                if (inv[i]<len)                  // hati hati, cek apakah index sekarang melebihi input?
                    printf("%c",s[inv[i]]);
                inv[i] += k;                     // lanjutkan ke baris berikutnya
            }
        
        puts("");
    }
}

Kembali ke halaman utama

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

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

6
2 5
0 1
1 6
2 3
1 2
4 5
2
0 1
3 5

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:

  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?
    • 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.
  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.
    • 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.
  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);
    }
}

Kembali ke halaman utama

Final Indonesia National Contest 2007 :: Problem B - GCD!

ACM/ICPC Indonesia National Contest 2007

Problem B

GCD!

Time Limit: 1s


The greatest common divisor of two numbers is defined as the largest integer that divides both numbers without leaving any reminder. For example, the greatest common divisor of 8 and 12, written as GCD(8,12) is 4, as 4 is the largest integer that divides both 8 and 12 (the common divisors of 8 and 12 are 1, 2, and 4).

Meanwhile, the factorial of a natural number is the product of all positive integers less than or equal to that number. For example, the factorial of 5, written as 5! is 1*2*3*4*5, which equals to 120. By convention, 0! is 1.

Given two integers, n and k, you should find the greatest common divisor of n! and k. For example, if n = 3 and k = 10, then GCD(n!,k) = GCD(3!,10) = GCD(1*2*3,10) = GCD(6,10) = 2. Write a program to find this number!

Input

Each line contains two integers, n (0 <= n <= 1,000,000,000) and k (1 <= k <= 1,000,000,000) respectively.

Output

For each line of input, output one line containing the GCD of n! and k.

Sample Input

3 10
10 240
12 364
100 2351
629 163547

Sample Output

2
240
28
1
67


Problem Setter: Suhendry Effendy


Pembahasan Problem B - GCD!

Hitunglah GCD(n!,k)

GCD (Greatest Common Divisor) dalam bahasa Indonesia adalah FPB (Faktor Persekutuan Terbesar). Untuk mencari GCD(A,B) anda bisa memfaktorisasi A dan B dalam bentuk faktor-faktor prima mereka, dan kemudian memilih faktor berpangkat paling kecil dan mengalikannya kembali.

Contoh:

A = 543312
B = 24570
GCD(A,B) = ?

Kita bisa faktorisasi A dan B menjadi faktor prima mereka:

A = 543312 =  2^4 * 3^2       * 7^3 * 11
B = 24570  =  2^1 * 3^3 * 5^1 * 7^1      * 13

Berikutnya, untuk setiap faktor prima yang bersekutu (common) antara A dan B,
ambil yang berpangkat lebih kecil, kalikan semuanya, itulah hasil GCD(A,B):

GCD(A,B) = 2^1 * 3^2 * 7^1 = 126

Ok, itu gampang... tapi pertanyaannya bukan GCD(N,K) tetapi GCD(N!,K). Bagaimana sekarang?

Untuk ini, anda perlu jurus baru:

Cara menghitung banyaknya faktor X di dalam N faktorial.
Ada cara cepat menghitung hal tersebut, anda bisa lihat artikelnya disini. (blum sempet nyari, internet bapuk)
Setelah anda tahu jurus ini, sisanya sama seperti cara diatas:
Untuk setiap faktor prima P dari K, anda cari ada berapa faktor prima P dalam N!
Lalu ambil yang berpangkat terkecil, kalikan ke dalam hasil akhir.
Silahkan lihat code dibawah untuk lebih jelasnya.

Ada satu trik lagi untuk menghindari time limit dalam pencarian faktor prima P dari K:

Carilah hanya sampai square-root dari K
Karena lebih dari itu, K sudah pasti bilangan prima.

#include <stdio.h>

// ini adalah jurus baru yang dimaksud diatas:
// menghitung jumlah faktor x dalam n!
int factorialPower(int n, int x){
    int res = 0;
    while (n>0){
        res += n/x;
        n /= x;
    }
    return res;
}

int main(){
    int n, k, i, p;

    while (scanf("%d %d",&n,&k)!=EOF){
        int result = 1; // GCD dari 2 bilangan positive apapun minimal adalah 1

        // kita hanya perlu looping p dari 2 .. sqrt(k)
        // untuk mencari faktor-faktor prima p dari k.
        for (p=2; p*p <= k; p++){
            int pPower = 0;
            while (k % p == 0){
                k /= p;   // p disini adalah bilangan prima di penjelasan diatas
                pPower++; // mencari berapa banyak faktor p dalam k
            }
            
            // memilih faktor yang berpangkat lebih kecil antara faktor-faktor dari k
            // dengan faktor-faktor dari n!, tampung pangkat terkecilnya di pPower
            if (pPower > factorialPower(n,p))
                pPower = factorialPower(n,p);

            // kalikan p ke hasil sebanyak pangkat terkecil yang bersekutu (pPower)
            for (i=0; i<pPower; i++) result *= p;
        }

        // sisa k disini adalah bilangan prima (berpangkat 1) dan kalau k lebih kecil
        // atau sama dengan n, maka k termasuk bagian dari GCD
        if (k <= n) result *= k;
        printf("%d\n",result);
    }
}

Kembali ke halaman utama

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

Final Indonesia National Contest 2007

Babak Final, 16 Juni 2007

Juara-juara Indonesia National Contest 2007 (INC 2007) kali ini adalah:

  1. Champion - kurniady (Andrian Kurniady, Dennis Andika Suryawijaya, Peter Suryaatmaja) Solve 6 problems.
  2. Gold Medal - NoMoreAC (Timotius Sakti, Stephen Kohar, Surya Sujarwo) Solve 4 problems.
  3. Silver Medal - nelkichan (Nelson Kurniawan, Kikita Yoshehana, Chandra Diharja) Solve 4 problems.
  4. Silver Medal - Tweety (Cun Cun Lim, Eko Wibowo, Stefan A.Y.) Solve 3 problems.
  5. Bronze Medal - PGK (Gunawan, Kenny Hartono, Pascal Gerardus Angriawan) Solve 3 problems.
  6. Bronze Medal - hura-hura (Pascal Alfadian, Yoseph Ronald Soetanto, Yosia Setyo Susabdo) Solve 3 problems.
Untuk complete list dari tim-tim finalis INC 2007 beserta score mereka bisa dilihat disini, nama anggota untuk masing-masing team bisa dilihat disini.

Perlu diketahui, bahwa salah satu anggota tim dari tim Juara Champion INC 2007 (tim kurniady) ini adalah Andrian Kurniady yang berhasil membawa tim Bina Nusantara (dengan nama tim YoiAC) bersama saya (Felix Halim) dan Andoko Chandra ke tingkat dunia dalam event ACM ICPC World Final 2007 di Jepang dengan menjuarai ACM ICPC Regional Kaohsiung 2006 di Taiwan. Dan juga tim NoMoreAC dari BiNus yang menyapu bersih soal penyisihan mendapat peringkat kedua (Gold Medal) di babak final ini. Itu semua bisa dicapai karena ketekunan mereka bertahun-tahun melatih kemampuan algoritma mereka. Just want you to know that: Saya bangga dengan prestasi kalian :)

Champion dari INC 2007, tim kurniady, menceritakan pengalaman tim-nya selama final INC 2007 beserta pembahasan solusi mereka memecahkan problem-problem dalam blognya. Untuk tim-tim lain, kalian bisa sharing pengalaman kalian selama INC 2007 ini? Just let me know kalau kalian sharing di blog kalian, silahkan di-post link-nya di chat-box kanan atas halaman ini.

Sewaktu penutupan acara, salah satu anggota juri, Suhendry, menjelaskan algoritma yang dipakai untuk "solve" ke delapan problems yang diberikan di babak final ini. Tetapi karena tidak ada "papan tulis" mungkin agak susah menjelaskan hanya dengan lisan. Saya akan mencoba menganalisa kembali dengan penjelasan se-sederhana mungkin untuk mereka yang miss penjelasan dari juri. Berikut adalah soal, pembahasan, dan solusi untuk babak final:

Nama Soal Pembuat Soal Pembahasan Solusi
A Minimum Swap Lego Haryanto Ad Hoc
B GCD! Suhendry Effendy Mathematics
C Playing With Domino Ang Ing Ing Euler Path
D Email from the Professor Suhendry Effendy Simulation
E Panda Number Evan Leonardi Recurrence
F Jakarta Traffic Jam Danny Gunawan Shortest Path
G Sultan's Land Suhendry Effendy Brute Force
H Tree Median Suhendry Effendy Dynamic Programming

Notes:

Jika anda tertarik terhadap lomba programming seperti ini, maka anda mungkin tertarik juga pada lomba-lomba lainnya seperti: TOKI, IOI, ACM ICPC, TopCoder, Google Code Jam, USACO, Imaginecup, Codecup, etc... Karena semua soal-soal di lomba seperti itu mirip seperti apa yang anda lihat di lomba INC 2007 ini.

Sunday, June 10, 2007

Penyisihan Indonesia National Contest 2007

Babak Penyisihan, 10 Juni 2007

Hallo para peserta/mahasiswa/i atau siapapun yang tertarik untuk melihat soal-soal beserta pembahasan lomba Bina Nusantara Programming Contest 2007 (BNPCCS 2007) yang sekarang berubah nama menjadi Indonesia National Contest (INC 2007).

Saya tahun ini tidak eligible untuk ikut lomba tersebut, tetapi saya tetap antusias dengan perkembangan lomba programming. Senang sekali bisa ikut penyisihan INC 2007 sebagai peserta bayangan (terima kasih kepada tim juri yang membuatkan ID bayangan). FYI, peserta bayangan tugasnya hanya membayang-bayangi peserta lainnya :) tetapi tidak mendapat hadiah apapun kalo menang (note: tidak sembarang orang bisa mendaftar menjadi peserta bayangan).

Ok cukup basa-basinya, berikut adalah 5 soal dikeluarkan untuk babak penyisihan berikut pembahasannya dan code solusi saya:

Nama Soal Pembuat Soal Pembahasan Solusi
A The Chosen Sub Matrix Bong Win Ce Brute Force
B Avoiding Financial Nightmare Bong Win Ce Binary Search
C No Pause Telegraph Bong Win Ce Greedy
D Burger, French Fries, Soft Drink Suhendry Effendy Combinatorics
E Taxi! Suhendry Effendy Dynamic Programming

Kalau menurut saya, tingkat kesulitan diurutkan dari paling gampang ke paling susah adalah: C, A, D, B, E.

Di babak final nanti saya akan terbang ke Indo untuk ikut membayang-bayangi NoMoreAC! (satu satunya tim yang menyapu bersih soal penyisihan dan mendapatkan keadaan dimana "No More AC").

Penyisihan Indonesia National Contest 2007 :: Problem E - Taxi!

ACM/ICPC Indonesia National Contest 2007 - Qualification

Problem E

Taxi!

Time Limit: 1s


Taxi Driver:  "Where to go, sir?"
Passenger:  "Kemanggisan, Binus Campus, please."
Taxi Driver:  "Okay, and which way to go?"
Passenger:  "Just take the fastest one."

This kind of conversation usually happens when we take a taxi. Many people think that the fastest way would mean the cheapest one as well. But it's not always true! Sometimes the fastest way could be more expensive than the slower one and vice versa, some factors are: toll fee, longer road without traffic jam, etc.

We will model this kind of situation on this problem. The city has n intersections and m bidirectional roads connecting pairs of intersections. Each road will cost you a certain time and money (taxi fare). Write a program to find the minimum time to take you to your destination however the travel expenses must not exceed your money.


Input Specification

The first line of each case contains two integers, n (1 <= n <= 100) intersections and m roads. The intersections are numbered from 0 to n-1. The next m lines will each contains four integers: u, v, t, and c (1 <= t,c <= 100), means that there is a road from intersection u to intersection v and vice versa which will cost you t minute(s) and c Rupiah(s). The last line of each case will contains three integers: s, d, and r (1 <= r <= 100), means that you want to go to d (your destination point) from s (your starting point) while you only have r Rupiah(s).


Output Specification

For each case, output in a single line the minimum time to reach your destination while the total cost doesn't exceed your money.


Sample Input

3 3
0 2 16 19
0 1 9 12
1 2 5 13
0 2 20
4 5
0 1 2 11 
1 2 7 27
2 3 4 10
0 3 6 25
3 1 5 12
0 2 35

Sample Output

16
10


Problem Setter: Suhendry Effendy


Pembahasan Problem E - Taxi!

Diberikan N persimpangan dan M jalan yang menghubungkannya. Anda ingin berpergian dari persimpangan A ke persimpangan B, tetapi anda hanya mempunyai uang sebanyak R rupiah. Setiap M jalan yang menghubungkan 2 persimpangan, tercatat harga dan waktu untuk melewati jalan tersebut (arahnya tidak masalah). Anda tidak peduli uang anda habis terpakai semua atau tersisa (tetapi tidak boleh negative!), anda hanya peduli waktu tercepat yang mungkin dari A ke B menggunakan uang R rupiah. Berapakah waktu tercepat tersebut?

Ini adalah soal tersulit di babak penyisihan. Karena untuk menyelesaikannya, anda setidaknya harus bisa rekursi + memo (dp topdown) atau A* complete search. Dijkstra yang hanya berdasarkan waktu tidak mempan disini karena ada kasus dimana waktu tercepat membutuhkan uang melebihi R rupiah, jadi anda harus memilih waktu ke-2 atau ke-3 tercepat, dst.. sampai waktu ke-x tercepat dimana hanya membutuhkan uang kurang atau sama dengan R rupiah.

Dynamic Programming dengan topdown approach (rekursi + memo) merupakan cara paling gampang untuk menyelesaikan problem ini. State dari Dynamic Programmingnya adalah fastest[P][U], artinya: berapa waktu tercepat untuk sampai ke tujuan dari posisi P, dengan sisa uang U. Jika anda bisa mengisi semua tabel ini, maka jawabannya adalah fastest[A][R]. Cara mengisi tabel tersebut, bisa menggunakan rekursi. Untuk lebih jelasnya, lihat source code taxi-dp-topdown.c dibawah.

A* adalah suatu cara pencarian yang komplit (complete search), artinya semua possibility akan dipertimbangkan. Kelemahannya adalah state space nya akan meluas dengan cepat (boros memory) dan agak lambat sedikit (ada faktor log(n) dari priority queue sewaktu insert ataupun extractMin). Tetapi A* akan sangat cepat jika solusinya selalu ada dan heuristic yang dipakai bagus.

Untuk problem ini, A* nya bisa dilakukan dengan meng-generate semua possible paths, dan menjalankan terlebih dahulu jalan yang paling murah. Untungnya, di problem ini A* nya bisa dibantu dengan sedikit "memo" sehingga bisa berjalan cepat. Memo nya adalah jangan memproses lagi path yang melalui suatu persimpangan yang time nya lebih besar dari sebelumnya. A* ini akan berjalan sekitar O(N^2). Memo ini akan berhasil karena jika ada path lain yang mengunjungi node yang sudah pernah dikunjungi, berarti costnya sekarang lebih mahal (karena A* selalu memproses yang costnya murah dahulu). Kalau cost sekarang lebih mahal, kita tinggal lihat apakah waktu sekarang lebih cepat? kalau tidak lebih cepat, maka tidak perlu lagi dilanjutkan (akan selalu rugi).

Yang membuat soal ini agak susah adalah, anda harus membuat Priority Queue data structure sendiri untuk mengimplementasinya jika tidak mau maka anda harus menguasai STL priority_queue di C++. Soal ini bukan soal mudah :) Saya sertakan kode A* dengan Priority Queue bikinan sendiri (yang lebih lambat, versi O(N)) dan kode A* dengan STL priority_queue (yang lebih cepat, O(log(N))).

Solusi Java untuk A* mungkin lebih mudah dimengerti daripada versi C/C++ karena Java 5 juga support Priority Queue

Note: A* diatas tidak ada heuristic functionnya, jadi bisa dibilang A* degenerate menjadi Dijkstra biasa.

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

int n,A,B,inf=1000000000;
int waktu[100][100];
int harga[100][100];
int memo[100][101];

int fastest(int P, int R){
    int i, ret = inf;
    if (P==B) return 0;
    if (memo[P][R]!=-1) return memo[P][R];

    for (i=0; i<n; i++){
        if (waktu[P][i]!=-1 && R>=harga[P][i]){
            int t = waktu[P][i] + fastest(i,R-harga[P][i]);
            if (t < ret) ret = t;
        }
    }
    return memo[P][R] = ret;
}

int main(){
    int m,u,v,t,c,i,R;
    
    while (scanf("%d %d",&n,&m)!=EOF){
        memset(waktu,-1,sizeof(waktu));
        memset(harga,-1,sizeof(harga));
        for (i=0; i<m; i++){
            scanf("%d %d %d %d",&u,&v,&t,&c);
            waktu[u][v] = waktu[v][u] = t;
            harga[u][v] = harga[v][u] = c;
        }
        scanf("%d %d %d",&A,&B,&R);
        memset(memo,-1,sizeof(memo));
        printf("%d\n",fastest(A,R));
    }
}
#include <stdio.h>
#include <stdlib.h>

#define MAXN 105
#define INF 1000000

typedef struct {
    int harga, waktu, pos;
} Node;

int nodecmp(const void *a, const void *b){
    Node *na = (Node*) a;
    Node *nb = (Node*) b;
    return na->harga - nb->harga;
}

Node pq[100000];
int harga[MAXN][MAXN];
int waktu[MAXN][MAXN];
int bestTime[MAXN];

int main(){
    int n,m,u,v,t,c,duit,i,pqSize;

    while (scanf("%d %d",&n,&m)!=EOF){
        for (u=0; u<n; u++){
            for (v=0; v<n; v++) waktu[u][v] = -1;
            bestTime[u] = INF;
        }

        for (i=0; i<m; i++){
            scanf("%d %d %d %d",&u,&v,&t,&c);
            waktu[u][v] = waktu[v][u] = t;
            harga[u][v] = harga[v][u] = c;
        }
        scanf("%d %d %d",&u,&v,&duit);

        pq[0] = (Node){0,0,u};
        pqSize = 1;
        while (pqSize > 0){
            qsort(pq,pqSize,sizeof(Node),nodecmp); // sort berdasarkan harga termurah
            Node node = pq[0];
            pq[0] = pq[--pqSize]; // timpa elemen pertama dengan terakhir

            if (bestTime[node.pos] <= node.waktu) continue;
            bestTime[node.pos] = node.waktu;
            if (node.pos == v) continue;

            for (i=0; i<n; i++) {
                if (waktu[node.pos][i]==-1) continue;
                if (node.harga + harga[node.pos][i] > duit) continue;
                pq[pqSize++] = (Node){
                    node.harga + harga[node.pos][i],
                    node.waktu + waktu[node.pos][i],
                    i
                };
            }
        }
        
        printf("%d\n",bestTime[v]);
    }
}
#include <stdio.h>
#include <queue>

using namespace std;

#define MAXN 105
#define INF 1000000

typedef struct Node {
    int harga, waktu, pos;

    bool operator<(Node const &that) const {
        return harga > that.harga;
    }
} Node;

int harga[MAXN][MAXN];
int waktu[MAXN][MAXN];
int bestTime[MAXN];

int main(){
    int n,m,u,v,t,c,duit,i;

    while (scanf("%d %d",&n,&m)!=EOF){
        for (u=0; u<n; u++){
            for (v=0; v<n; v++) waktu[u][v] = -1;
            bestTime[u] = INF;
        }

        for (i=0; i<m; i++){
            scanf("%d %d %d %d",&u,&v,&t,&c);
            waktu[u][v] = waktu[v][u] = t;
            harga[u][v] = harga[v][u] = c;
        }
        scanf("%d %d %d",&u,&v,&duit);

        priority_queue<Node> pq;
        pq.push((Node){0,0,u});
        while (!pq.empty()){
            Node node = pq.top(); pq.pop();

            if (bestTime[node.pos] <= node.waktu) continue;
            bestTime[node.pos] = node.waktu;
            if (node.pos == v) continue;

            for (i=0; i<n; i++) {
                if (waktu[node.pos][i]==-1) continue;
                if (node.harga + harga[node.pos][i] > duit) continue;
                pq.push((Node){
                    node.harga + harga[node.pos][i],
                    node.waktu + waktu[node.pos][i],
                    i
                });
            }
        }
        
        printf("%d\n",bestTime[v]);
    }
}
import java.util.*;

public class TaxiAStar {
    class Node implements Comparable<Node> {
        int harga, waktu, pos;

        public Node(int harga, int waktu, int pos){
            this.harga = harga;
            this.waktu = waktu;
            this.pos = pos;
        }

        public int compareTo(Node that){
            return this.harga - that.harga;
        }
    }

    int[][] harga;
    int[][] waktu;
    int[] bestTime;

    public void solve(){
        Scanner scan = new Scanner(System.in);

        while (scan.hasNextInt()){
            int N = scan.nextInt();
            int M = scan.nextInt();

            harga = new int[N][N];
            waktu = new int[N][N];
            bestTime = new int[N];

            for (int i=0; i<N; i++){
                for (int j=0; j<N; j++)
                    waktu[i][j] = -1;
                bestTime[i] = 1000000000;
            }

            for (int i=0; i<M; i++){
                int u = scan.nextInt();
                int v = scan.nextInt();
                int t = scan.nextInt();
                int c = scan.nextInt();
                waktu[u][v] = waktu[v][u] = t;
                harga[u][v] = harga[v][u] = c;
            }

            int A = scan.nextInt();
            int B = scan.nextInt();
            int R = scan.nextInt();

            PriorityQueue<Node> pq = new PriorityQueue<Node>();
            pq.offer(new Node(0,0,A));
            while (pq.size()>0){
                Node node = pq.poll();

                if (bestTime[node.pos] <= node.waktu) continue;
                bestTime[node.pos] = node.waktu;
                if (node.pos == B) continue;

                for (int i=0; i<N; i++){
                    if (waktu[node.pos][i]==-1) continue;
                    if (node.harga + harga[node.pos][i] > R) continue;
                    pq.offer(new Node(
                        node.harga + harga[node.pos][i],
                        node.waktu + waktu[node.pos][i],
                        i
                    ));
                }
            }
            
            System.out.printf("%d\n",bestTime[B]);
        }

        scan.close();
    }

    public static void main(String[] args){
        new TaxiAStar().solve();
    }
}

Back to Home

Penyisihan Indonesia National Contest 2007 :: Problem D - Burger, French Fries, Soft Drink

ACM/ICPC Indonesia National Contest 2007 - Qualification

Problem D

Burger, French Fries, Soft Drink

Time Limit: 1s


Anna works as a waitress at a popular fast-food restaurant in Indonesia, "Om Burger". Her job is much easier than any waiters/waitresses at other fast-food restaurants, because Om Burger owns an automatic fast-food machine.

Om Burger serves only a single combo-menu package named Paket Uenak, which consists of three items: 1 Burger (B), 1 French Fries (F), and 1 Soft Drink (S). Each customer would be given a card to write the number of Paket Uenak packages to be ordered. The card should be given back to Anna who will insert it into the machine. The machine will prepare all items of each package one by one according to the written number on the card, but not necessary in any particular order of item. For example, if the number 2 (means 2 Paket Uenak packages are ordered by a customer) is written on the card, the machine will prepare items in the sequence of BBFFSS, or any of its permutation (BFSBFS, BBFSFS, etc). There could be more than one card to be processed by the machine at a time. However the machine will process all cards sequentially. That means it will not proceed to the next card before finishing the current card.

One day, some customers are queuing to put their orders. While they make a quite long queue, it gives Anna an idea. Instead of inserting the card one by one, she initiatively inserts more than one card at a time. Brilliant, isn't she? Well, let's see what happens next. The machine does work well, but now she doesn't have any idea which item belongs to which card, because the machine doesn't give any separations to separate packages from different cards.

Fortunately, Anna still remembers the number of cards inserted and its sequence (which card belongs to whom). However, she doesn't remember the number of Paket Uenak packages written on each card.

For example, if there are two cards inserted into the machine:
Prepared : B B F S S F S F B B F S
Possibility-1 : (B B F S S F) ( S F B B F S), the first customer ordered 2 Paket Uenak packages, and the second customer ordered 2 Paket Uenak packages.
Possibility-2 : (B B F S S F S F B) (B F S), the first customer ordered 3 Paket Uenak packages, and the second customer ordered 1 Paket Uenak package.

No need to tell, that now she's apologizing and questioning all customers for what they have been ordering again. But this problem has aroused her curiosity as she is also a student in Computer Science. Help Anna to find how many possible order arrangements could be found from any given condition(s).


Input Specification

Each line of input contains an integer N (1 < N < 30) denoting the number of card(s) inserted, and a string which contains character(s) of B, F, and S (no spaces) denoting the order of items prepared by the machine. You may assume that the length of each string is less than 100.


Output Specification

For each line of input, print the number of possible order arrangements could be found. If there is no possible order arrangement, output "Impossible" (without quotes).


Sample Input

2 BBFSSFSFBBFS
2 BBFSSFSFBB

Sample Output

2
Impossible


Problem Setter: Suhendry Effendy


Pembahasan Problem D - Burger, French Fries, Soft Drink

Anda diberikan urutan paket yang dikeluarkan oleh mesin seperti ini: BBFSSFSFBBFSSBFFSBBSF. Suatu pesanan dianggap valid jika jumlah B sama dengan jumlah F dan S. Misalkan diberi tahu ada N pesanan (N < 30), berapakah "kombinasi" pesanan yang mungkin terjadi kalau mesinnya mengeluarkan output seperti diatas?

Problem ini sengaja disamarkan dengan tidak menggunakan keyword "combination". Kembali ke contoh output mesin diatas, misalkan N = 3 (ada 3 pesanan). Maka kalau dilihat output dari mesin tersebut: BBFSSFSFBBFSSBFFSBBSF, terlihat ada 6 kemungkinan pesanan kecil-kecil yang valid: BBFSSF | SFB | BFS | SBF | FSB | BSF. Berikut adalah 10 possibilities dari pesanan tersebut:

  • (BBFSSF) (SFB) (BFSSBFFSBBSF)
  • (BBFSSF) (SFBBFS) (SBFFSBBSF)
  • (BBFSSF) (SFBBFSSBF) (FSBBSF)
  • (BBFSSF) (SFBBFSSBFFSB) (BSF)
  • (BBFSSFSFB) (BFS) (SBFFSBBSF)
  • (BBFSSFSFB) (BFSSBF) (FSBBSF)
  • (BBFSSFSFB) (BFSSBFFSB) (BSF)
  • (BBFSSFSFBBFS) (SBF) (FSBBSF)
  • (BBFSSFSFBBFS) (SBFFSB) (BSF)
  • (BBFSSFSFBBFSSBF) (FSB) (BSF)

Kalau anda melakukan analisa lebih dalam, akan terlihat rumus nCk berlaku (n choose k). Dalam kasus diatas, jawaban 10 didapat dari nCk(6-1, 3-1) -> (5 choose 2) -> 10 kombinasi pesanan. Kenapa ada -1? anda harus menganalisannya sendiri ;)

Ada cara lain untuk menyelesaikan soal ini tanpa pikir panjang. Yaitu dengan Dynamic Programming versi topdown atau boleh disebut juga rekursi + memoization. Cara ini sangat mudah bagi mereka yang sudah terbiasa melakukan DP Topdown :) Hampir tidak perlu berpikir panjang untuk menyelesaikan soal ini :) Silahkan lihat kode dp-topdown dibawah :)

#include <stdio.h>

int nChooseK(int n, int k){
    long long ret = 1, i;
    for (i=0; i<k; i++)
        ret = ret * (n-i) / (i+1);
    return (int) ret;
}

int main(){
    char s[101];
    int n;

    while (scanf("%d %s",&n,s)!=EOF){
        int G=0,B=0,F=0,S=0,i;

        for (i=0; s[i]; i++){
            if (s[i]=='B') B++;
            else if (s[i]=='F') F++;
            else S++;

            if (B==F && B==S) G++;
        }
        
        if (B!=F || B!=S || G<n)
            puts("Impossible");
        else
            printf("%d\n",nChooseK(G-1,n-1));
    }
}
#include <stdio.h>
#include <string.h>

char s[101];
int len, memo[101][35];

int ok(int L, int R){
    int B=0,F=0,S=0,i;
    for (i=L; i<=R; i++){
        switch (s[i]){
            case 'B' : B++; break;
            case 'F' : F++; break;
            case 'S' : S++; break;
        }
    }
    return B==F && F==S && B>0;
}

int rec(int idx, int n){
    int ret=0, i;

    if (idx>=len) return 0;
    if (n==1) return ok(idx,len-1);
    if (memo[idx][n]!=-1) return memo[idx][n];

    for (i=idx+2; i<len; i++)
        if (ok(idx,i))
            ret += rec(i+1,n-1);

    return memo[idx][n] = ret;
}

int main(){
    int n;

    while (scanf("%d %s",&n,s)!=EOF){
        len = strlen(s);
        memset(memo,-1,sizeof(memo));

        if (rec(0,n)==0)
            puts("Impossible");
        else
            printf("%d\n",rec(0,n));
    }
}

Back to Home

Penyisihan Indonesia National Contest 2007 :: Problem C - No Pause Telegraph

ACM/ICPC Indonesia National Contest 2007 - Qualification

Problem C

No Pause Telegraph

Time Limit: 1s


Several hundreds years ago in a country, there was a war between the colonialist and the military of the country. In the war, telegraph machine was used to communicate between the country and its allied cities around the country. The Morse code was used to send messages through telegraph machine. In Morse, letters are represented only by "." (dot) and "-" (dash). Between letters there is a pause to avoid mistranslation of letters.

In that era with the popularity of telegraph machine, there was wariness that the enemy could read the messages, if the messages were accidentally sent to them. Being aware of the threat, a machine was created to encode the messages. It was called No Pause Telegraph. This new telegraph machine was similar to the regular machine, only that the machine encoded the messages with no pause between letters.

After doing some researches on old relics, our archeologist has analyzed the code being used successfully. The archeologist so far has found 7 letters that been used on the found relics, those are:
A .-- dot dash dash
B -. dash dot
C --- dash dash dash
D .. dot dot
E --.. dash dash dot dot
F --.- dash dash dot dash
G .-. dot dash dot
Your task is to translate several messages encoded by the machine on the remaining relics. You should be careful that any ambiguousity may arise when translating those messages. For example: If the code for X were "." and the code for Y were "..", then two dots in a row could be either XX or Y. For this particular reason, you should output only the least alphabetical solution.


Input Specification

Each line of input is a code encoded by No Pause Telegraph. The line will consists of only characters of . (dot(s)) and - (dash(es)).


Output Specification

For each line of input, print the least alphabetical possible message in one line. If there is no possible message, print "could not be translated" (without quotes).


Sample Input

.---.-
.---.---..--..--.-.-.

Sample Output

could not be translated
ABCDEFG


Problem Setter: Bong Win Ce


Pembahasan Problem C - No Pause Telegraph

Soal ini memberikan anda kode morse. Anda harus men-translasi kode tersebut menjadi huruf-huruf sesuai pengkodean berikut:

A  .--
B  -.
C  ---
D  ..
E  --..
F  --.-
G  .-.
Kode morse "jejadian" diatas adalah unik karena tidak ada prefix dari kode morse yang satu merupakan prefix dari kode morse yang lain. Jadi, suatu rangkaian kode-kode morse yang menggunakan pengkodean diatas pasti dapat ditranslasi menjadi hasil yang unik. Untuk melihat soal lengkapnya, silahkan click link problem statement diatas.

Untuk menyelesaikan soal ini, solusinya straight forward: anda bisa men-translasi satu-persatu kode morse di input menjadi huruf dan menampungnya ke dalam suatu temporary variable. Jika ada input yang tidak ada kode morsenya, maka anda tinggal print "could not be translated" dan berhenti. Jika semua input berhasil ditranslasi, maka print-lah temporary variable-nya. Kodenya dapat dilihat dibawah ini, tersedia 2 versi (C dan Java). Kedua source code ini melakukan hal yang sama dan mempunyai function yang sama. Tetapi solusi Java lebih terlihat manusiawi di function getMorse() karena Java mempunyai built-in method startsWith() di object String yang sangat sesuai untuk problem ini (untuk mengecek apakah suatu kode morse merupakan prefix dari input saat ini).

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

char input[1000], temp[1000];
char *morse[7] = {".--","-.","---","..","--..","--.-",".-."};

int get_morse(int idx){
    int i,a,b;
    for (i=0; i<7; i++){
        for (a=idx,b=0; ; a++,b++){
            if (morse[i][b]=='\0') return i;
            if (input[a]=='\0' || input[a] != morse[i][b]) break;
        }
    }
    return -1; // kode morse tidak ketemu!
}

char* translate(){
    int i,j,k;
    for (i=j=0; input[i]!='\0'; ){
        k = get_morse(i);
        if (k==-1) return "could not be translated";
        temp[j++] = 'A'+k;
        i += strlen(morse[k]);
    }
    temp[j] = '\0';
    return temp;
}

int main(){
    while (gets(input)){
        puts(translate());
    }
}
import java.util.*;

public class NoPause {
    String[] morse = new String[]{".--","-.","---","..","--..","--.-",".-."};

    public int getMorse(String prefix){
        for (int i=0; i<morse.length; i++)
            if (prefix.startsWith(morse[i])) return i;

        return -1; // kode morse tidak ketemu!
    }

    public String translate(String input){
        String temp = "";
        for (int i=0,j=0; i<input.length(); ){
            int k = getMorse(input.substring(i)); 
            if (k==-1) return "could not be translated";
            temp += (char) ('A'+k);
            i += morse[k].length();
        }
        return temp;
    }

    public void solve(){
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextLine())
            System.out.println(translate(scan.nextLine()));
        scan.close();
    }

    public static void main(String[] args){
        new NoPause().solve();
    }
}

Back to Home