Friday, December 14, 2007

ACM ICPC Singapore 2007

This is the first time NUS (National University of Singapore) host an ACM ICPC Regional. Singapore is a very strategic place for Asian teams because of free VISA (for ASEAN) and many direct planes to Singapore are available. This attracted many great teams all over Asia to join regional Singapore which made Regional Singapore one of the toughest Regional in Asia. The surprise prize for the champion team of this regional is 3 Lenovo (each worth around 3000 SGD)! This is a very attractive prize!! I'm sure the next 4 years (when NUS host the ACM ICPC Regional again), there'll be even more teams join Regional Singapore merely to get the prizes.

This time I represent NUS instead of BINUS UNIVERSITY. My team name is TOKIERS 020606 which consist of 3 TOKI (Tim Olimpiade Komputer Indonesia) members:

  1. Felix Halim, it's me from TOKI 2002 (Computer Science post-grad, first year).
  2. Aditya Kristanto Goenawan, from TOKI 2006 (Engineering under-grad, first year).
  3. Daniel Aris Pandu Prasetia, from TOKI 2006 (Engineering under-grad, first year).
FYI, TOKI is a government organization from Indonesia that manage, train, and select four Indonesian high-school students to be sent to IOI (International Olympiads in Informatics) contest every year. Surprisingly, there were a lot of TOKI alumnis (total 18 person) joined this year Singapore Regional contest. It's like a reunion of TOKI-ers :) If we count the total number of Indonesian contestants, it's is even greater: 6 universities from Indonesia (BINUS, ITB, Parahyangan, UI, USU, Telkom) + 1 from NUS (TOKIERS 020606) + 1 team from NTU (Ivory Gull), and several other teams also contains Indonesian contestant. Indonesian students are getting better and better in algorithm skills.


Left to Right: Aditya KG, Daniel APP, and Felix Halim

Registration and Practice Session - December 13, 2007

My brother, Steven Halim, is one of the Registration committee for this event. He is the one who gave you the ICPC Bag, T-Shirt, Name Tag, etc. So I think every team should've met my brother :). Since NUS were short in number of committee, the Registration committees ended up being "any" committee which took care of almost anything :(. They worked really hard to make this event sucessful. Thanks to them.

After registration, the 47 teams (except JiLin University who didn't manage to come due to VISA problem) went to the practice room. A bottleneck happened during the move so the practice session was delayed a bit. In this practice session, there were 3 easy problems given. However the last one is troublesome. My team and several other teams didn't manage to get it Accepted! The reason is the scanf problem. Those who used scanf("%d\n",&n) to read the number of testcases will never get this problem Accepted. Examine a C code below:

#include <stdio.h>

char s[1000];
int n;

int main(){
    scanf("%d\n",&n);
    for (int i=0; i<n; i++){
        gets(s);
        
        // process s here... 
        puts(s);
    }
}
If the input is something like:
3

felix
halim
Then the output is surprisingly wrong:
felix
halim
halim
The "\n" in scanf actually read two new lines! This is something unexpected. This is a lesson to never use scanf("%d\n", ...) if the input can be a blank line! There are several teams got trapped with this kind of thing including mine. Other than this issue, the rest of the practice session went smoothly.

ACM ICPC Regional Singapore - December 14, 2007

The contest starts at 8:30am and ends at 1:30pm. I got there Just in TimeTM :D to give a little excitement to the other teams. They thought I wouldn't come because probably I joined the last night SRM and was too tired to get up in the morning but then I dissapointed them by showing my face, hihihi. Whereas the fact is: I woke up late :P, causing panic to my own team :P (sori Daniel, Aditya)

Then the contest starts. As usual, I coded the template REP, FOR, using std, etc... just like TopCoder style (see my code below). Then the fun begins! The 7 problem statements of this regional contest can be found here.

Problem A - MODEX (Accepted in minute 7)

When I started reading, Aditya KG asked me if I know something about big-mod and pointed me to Problem A. With years of experience, looking at the big-mod was like going back to childhood :P. With no further ado, I coded and submit it. It's not a surprise that the other teams also get this problem accepted very quick.

The problem asked to compute x^y mod n. Where y can be as large as 2^31 - 1. The must-know-rule of big mod is: (a*b) mod c is equal to ((a mod c) * (b mod c)) mod c. The solution is to divide the y into two until it reaches the base case of y = 0. Then construct the solution based on the result of the smaller y. The dynamic programming goes like this:

x^y mod n is equal to

  • 1 (one) if y is equal to 0 (zero)
  • ((x^(y/2) mod n) * (x^(y/2) mod n)) mod n, if y is even
  • ((x^(y div 2) mod n) * (x^(y div 2) mod n) * x) mod n, if y is odd (where div is an integer division)
The C code is as follows:
#include <stdio.h>

int pow(int x, int y, int n){
    if (y==0) return 1;
    int t = pow(x,y/2,n);
    if (y%2==0) return (t*t) % n;
    return (((t*t)%n) * x) % n;
}

int main(){
    int nTC, x,y,n;

    scanf("%d",&nTC);
    while (nTC--){
        scanf("%d %d %d",&x,&y,&n);
        printf("%d\n",pow(x,y,n));
    }
}
What's intriguing about this problem is that, if you use Java, you can just use the BigInteger class! (Randy Sugianto told me this)
import java.util.*;
import java.math.*;
import java.io.*;

public class A {
    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);
        int nTC = scan.nextInt();
        while (nTC-- > 0){
            BigInteger x = BigInteger.valueOf(scan.nextInt());
            BigInteger y = BigInteger.valueOf(scan.nextInt());
            BigInteger n = BigInteger.valueOf(scan.nextInt());
            BigInteger z = x.modPow(y,n); // look ma, it's in the library ;)
            System.out.println( z );
        }
    }
}
Problem A was supposed to be a super bonus problem.

Problem C - ACORN (Accepted in minute 56)

Another DP (Dynamic Programming) problem. Hmm... It's really strange that this kind of problem is now becomes not interesting anymore. In early days when I was just starting to learn programming, I always thought that Dynamic Programming problems are hard, but nowdays these kind of problem starts to lose it's value. It's already becomes an easy-standard problems. Once you know the trick, the rest is just coding skills.

As we all know we have two ways to do DP: bottom-up and top-down. The bottom-up DP can save memory and more efficient but the code is not intuitive sometimes. The top-down DP is very easy to code (intuitive) but takes up more memory and run time. The code for both kinds of DP is presented below.

The problem is like this: There are t trees with the same height h. There are acorns distributed in different heights of any tree. A squirrel is currently at the top of a tree and want to go down and collect as many acorns as possible. The squirrel can choose to go down one step from height x to height x-1 or it can choose to fly to another tree from height x to height x-f (f is given). The question is what is the maximum number of acorns the squirrel can collect?

This is the bottom-up DP version:

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

#define REP(i,n) for (int i=0,_n=(n); i<_n; i++)
#define FORD(i,a,b) for (int i=(a),_b=(b); i>=_b; i--)

#define MAXN 2007

int dp[MAXN];
int tree[MAXN][MAXN];
int t,h,f,a,n,nTC;

int main(){
    scanf("%d",&nTC);
    while(nTC--){
        memset(dp,0,sizeof(dp));
        memset(tree,0,sizeof(tree));

        scanf("%d %d %d",&t,&h,&f);
        REP(i,t){
            scanf("%d",&a);
            REP(j,a){
                scanf("%d",&n);
                tree[i][n]++;
            }
        }

        FORD(i,h,1) REP(j,t){
            int best = tree[j][i+1]; // don't jump
            best >?= dp[i+f];        // jump
            best += tree[j][i];      // add current
            tree[j][i] = best;       // update
            dp[i] >?= best;          // update
        }
        printf("%d\n",dp[1]);   
    }   
}

This is the top-down DP version:

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

#define REP(i,n) for (int i=0,_n=(n); i<_n; i++)

#define MAXN 2001

int memo[MAXN][MAXN];
int tree[MAXN][MAXN];
int t,h,f,a,n,nTC;

int rec(int hi, int ti){
    if (hi>=h) return 0;
    int &ret = memo[hi][ti];
    if (ret!=-1) return ret;
    ret = tree[ti][hi] + rec(hi+1,ti);              // don't jump
    REP(i,t) ret >?= tree[ti][hi] + rec(hi+f, i);   // jump
    return ret;
}

int main(){
    scanf("%d",&nTC);
    while(nTC--){
        memset(memo,-1,sizeof(memo));
        memset(tree,0,sizeof(tree));

        scanf("%d %d %d",&t,&h,&f);
        REP(i,t){
            scanf("%d",&a);
            REP(j,a){
                scanf("%d",&n);
                tree[i][n-1]++;
            }
        }

        int res = 0;
        REP(i,t) res >?= rec(0,i);
        printf("%d\n",res);
    }
}
Daniel coded this problem using bottom-up dynamic programming and got it accepted in the first try.

Problem B - JONES (Accepted in minute 102, penalty 5 x 20)

IIRC, Aditya KG was doing problem F and I was doing problem G while Daniel was looking for another problem. The ranklist at this time is not good :( Our team solved 2 problems while more than ten other teams solved 3+ problems. What made me hot was that YoiMon was above us! This team should not be allowed to go any further!! :P

Problem G was also a typical problem: given a simple graph, you must select and remove a set of edges from the graph such that the graph has no cycle in it and the total weight of the removed edges is minimum. I thought problem G can be solved using greedy by finding the smallest edge (smallest weight) and check whether it is possible to create a cycle using that edge (using DFS). If can then I can just remove that edge and find the second smallest edge and so on. When I submit it, I got Wrong Answer. I was quite sure that this should work. Many teams already got this problem accepted, I was quite frustrated and decided to try the other problem.

Then Aditya KG took over the keyboard to code problem F while I'm hunting for another problem. Problem B (Jones) got my attention. By this time, Aditya KG had submit problem F several times but keep getting Wrong Answer.

Problem B is about Indiana Jones want to cross a river by hopping through stones. Each stones can sink at certain interval and can resurface in another interval or stand still. The exact interval of the sink/resurface is given. The question is what is the earliest time Indiana Jones can reach the other side of the river by jumping through these "magic" stones.

Problem B seemed too simple at the beginning and I was underestimating the problem. I thought the solution was just a simple DP (again): The Indiana Jones can jump forward to the next stone anytime he can or wait for the next stone to resurface (if it's currently sinking) and choose the best outcome. I robbed the keyboard and coded simple top-down DP "in no time" and then submit it (when I said "in no time", it actually consumes about 5 to 15 minutes :P). Then gave the keyboard back to Aditya KG as if Problem B already accepted, hehe :P.

To my surprise, my solution for problem B got Wrong Answer. I was too confident. When I printed the code, I realized that my code is totaly wrong: the variable name was switched (doh!). I fixed it and resubmit. Those of you who know the solution should know already that this submission will also get Wrong Answer. My algorithm was missing something important. That is: Indiana Jones can also jump back to the previous stones besides waiting or jumping forward. Realizing this mistake, I slipped in a few lines of code to the top-down DP to allow Indiana Jones to jump backward, and resubmit. At this time, the code was having too many patches and got Wrong Answer again :(. During this time, I bothered Aditya KG several times when he coded problem F. Maybe this is the reason he couldn't get problem F accepted :D, sorry Aditya. I calmed myself, and start to simplify Problem B code, resubmit and got it accepted at last. This is the code:

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

#define REP(i,n) for (int i=0,_n=(n); i<_n; i++)
#define FOR(i,a,b) for (int i=(a),_b=(b); i<=_b; i++)

int nTC,s,t;
char con[550][550], temp[10];
int memo[550][550];

int rec(int time, int idx){
    if (idx==s) return time;
    if (time>=t) return 1000;
    int &ret = memo[time][idx];
    if (ret!=-1) return ret; else ret = 1000;
    if (con[time][idx]==0) return ret;
    
    FOR(i,time,t-1){
        if (con[i][idx]==0) break;
        if (con[i][idx+1]) ret <?= rec(i+1, idx+1);
        if (idx>0 && con[i][idx-1]) ret <?= rec(i+1, idx-1);
    }
    return ret;
}

int main(){
    scanf("%d",&nTC);
    while (nTC--){
        scanf("%d %d",&s,&t);
        memset(con,0,sizeof(con));
        REP(i,t){
            REP(j,s){
                scanf("%s",temp);
                con[i][j] = temp[0];
            }
            con[i][s] = 1;
        }
        REP(i,s){
            int c = 1;
            REP(j,t){
                if (con[j][i]=='u'){
                    con[j][i] = c;
                } else if (con[j][i]=='r'){
                    con[j][i] = c = 1;
                } else {
                    con[j][i] = c = 0;
                }
            }
        }
        con[t][s] = 1;

        memset(memo,-1,sizeof(memo));
        int res = 1000;
        REP(i,t-1) if (con[i][0]) res <?= rec(i+1,0);
        if (res>=1000) puts("-1");
        else printf("%d\n",res);
    }
}

Problem F - USHER (Accepted in minute 129, penalty 3 x 20)

The ranklist at this point was also not good, no need to tell the details (I'm embarrassed :P). Feeling guilty to Aditya which keyboard got robbed by me several times, I decided to rob his problem as well (how cruel me!!) since I didn't have clue for other problems yet. I asked Daniel to re-explain the problem F again. He explained to me: There is a box which can be inserted up to certain amount of dollar coins in it. This box is passed from the usher to several parishioners and the parishioners can add certain amout of dollar in it and pass it back to usher or other parishioners and so on. The box passing stops when the box is full of coins. Every time the usher get the box, he will remove one coin, add it to his pocket and the passing continues. Usher never add coin to the box. The question is what is the maximum number of coins the usher can get?

Floyd Warshall algorithm immediatelly popped out from my mind (FYI, it's another DP algorithm). That is, just find the minimum cost cycle from usher to parishoioners and back to the usher again. The result is the box capacity divided by the cycle cost. I immediatelly coded it "in no time" again and submit it. I had a feeling that simple division wouldn't work but Daniel was fine-fine aja with that so I submit it anyway. It's my fault that I didn't tell Daniel my doubt :(. After got Wrong Answer, Daniel then remembered that he forgot to tell me that after dividing the box capacity with the shortest cycle length (or cost), we need to calculate again the possibility of having more cycle (because the usher removed a coin). Thus, the usher may end up having more coins. Aditya KG already have the formula to calculate this, I can just use his, resubmit and got it accepted. It was just a slight error, anyway, good work Aditya and Daniel. Below is our code for problem F:

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

#define REP(i,n) for (int i=0,_n=(n); i<_n; i++)
#define FOR(i,a,b) for (int i=(a),_b=(b); i<=_b; i++)

int nTC, cost, n, box, con[510][510], nr, a,b;

int main(){
    scanf("%d",&nTC);
    while (nTC--){
        scanf("%d %d",&box,&n); n++;

        memset(con,-1,sizeof(con));

        scanf("%d",&nr);
        REP(i,nr){
            scanf("%d",&b);
            con[0][b] = 0;
        }
        
        FOR(i,1,n-1){
            scanf("%d",&nr);
            REP(j,nr){
                scanf("%d %d",&a,&b);
                if (con[i][b]==-1 || a<con[i][b]) con[i][b] = a;
            }
        }
        
        // Floyd Warshall
        REP(k,n) REP(i,n) if (con[i][k]!=-1)
            REP(j,n) if (con[k][j]!=-1){
                if (con[i][j]==-1 || con[i][j] > con[i][k] + con[k][j])
                    con[i][j] = con[i][k] + con[k][j];
            }
        
        int cycleLen = 1000000000;  
        FOR(i,1,n-1) if (con[0][i]!=-1 && con[i][0]!=-1)
            cycleLen <?= con[0][i] + con[i][0];

        // Aditya KG's formula
        cycleLen--;
        int tot = box/cycleLen;
        while ((tot*cycleLen) + cycleLen+1 >= box) tot--;
        printf("%d\n",tot+1);
    }
}

Problem G - RACING (Accepted in minute 164, penalty 1 x 20)

This time, our team was still below YoiMon but we have the same number of solved problems :). However the rank was still bad enough, we need to solve more problems to get to the top 10.

Fortunately, out of the blue, Daniel mentioned something about Minimum Spanning Tree for problem G. When I think about it again, the algorithm seemed fit to the problem! Since we need to remove the cycles from the graph by removing edges, this description is like creating a tree. When I think about what the tree should look like, it "clicks" with the Maximum Spanning Tree. Knowing this, coded problem G, again, "in no time", submit it and got it accepted, Yatta!! At least there wass some period of time where TOKIERS 020606 managed to surpass YoiMon :D Below is our code for problem G:

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

using namespace std;

#define REP(i,n) for (int i=0,_n=(n); i<_n; i++)
#define FOR(i,a,b) for (int i=(a),_b=(b); i<=_b; i++)

#define MAXN 10010

// Union-Set algorithm
int pset[MAXN];
void initset(){ REP(i,MAXN) pset[i] = i; }
int findSet(int i){ return (pset[i]==i)? i: (pset[i] = findSet(pset[i])); }
void merge(int i, int j){ pset[findSet(i)] = findSet(j); }
int sameSet(int i, int j){ return findSet(i)==findSet(j); }

int nTC,n,m;
char vis[MAXN];

int main(){
    scanf("%d",&nTC);
    while (nTC--){
        scanf("%d %d",&n,&m);
        vector<pair<int,pair<int,int> > > junc;
        REP(i,m){
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c); a--; b--;
            junc.push_back(make_pair(c,make_pair(a,b)));
        }

        // sort edges descending by weight
        sort(junc.rbegin(), junc.rend());

        // Maximum Spanning Tree
        memset(vis,0,sizeof(vis));
        initset();
        int res = 0;
        REP(i,junc.size()){
            int a = junc[i].second.first;
            int b = junc[i].second.second;
            int c = junc[i].first;
            if (sameSet(a,b)) res += c;
            else merge(a,b);
        }
        printf("%d\n",res);
    }
}

The rest of the contest

I already found the algorithm for problem D which runs in O(n^2 log n) also problem E which is kind of gambling (unsure if my algo will pass the time limit). The remaining time is about 1 hour and 20 minutes, I decided to go with problem D and told Aditya and Daniel to think of faster algorithm for problem E.

It turned out to be a bad idea, problem D is quite hard to implement and I got bugs in the code I couldn't find :(, now it's 30 minutes left, the ranklist was freezed. This was really a problematic situation. If I recoded problem D, it won't finish in time. Aditya and Daniel couldn't find faster algorithm for problem E either. So I focused on problem D but still didn't managed to pass the sample case :(. I guess this is the end of our strength.


TOKIERS 020606 in Action!

After contest

Many teams asked me what's wrong with their solution for Problem B. Why they got so many Wrong Answers. They asked me what was the tricky case? I was surprised since I didn't find any tricky case for Problem B. I got WA previously because my algo and code was wrong and there were so many changes before I got it accepted. So I couldn't remember which one I changed to make it accepted. When I looked at the standings, the top teams also didn't manage to get it accepted and there were exceptionaly so many Wrong Answers on problem B! I suspect there is something fishy about this problem. Maybe there is an unwritten boundary case? But why some of the team got it accepted? The judges at that time concluded that the judge output was correct. Nobody could figure out what's wrong with Problem B.

After having lunch and city tour in the afternoon, the award ceremony begins. Only the top 5 teams got awards. The award ceremony was merged with the other three SoC competitions. This made ACM ICPC Singapore looked a lot less prestigious (seemed only a small part of SoC event). It was funny to see high-schoolers and middle-schoolers came up from nowhere, got awarded then paired with the champion team of ACM ICPC. We were totaly un-aware of those competitions and it felt awkward. Anyway, below is the official standings. The light-green-ed teams contain Indonesian contestants.

RankUniversity NameTeam NameCitation# SolvedTime
1Shanghai Jiao Tong UniversityPrimeFirst Place7569
2Zhejiang UniversityOthelloSecond Place7641
3Shanghai Jiao Tong UniversitySofasquadThird Place6470
3Peking UniversityExcaliburThird Place6603
4Zhongshan(Sun Yat-sen) UniversityZSU_PhecdaFourth Place6650
5Fudan UniversityMetaphorFifth Place6757
5BINUS UNIVERSITYYoiMonFitth Place6765
5National Tsing Hua UniversityB.F.WFifth Place61044
8Nanyang Technological UniversityNTU Ivory GullEighth Place5328
8Taiwan Universityrand N-SATEighth Place5379
8Nanyang Technological UniversityNanyang EaglesEighth Place5607
8National University of SingaporeTOKIERS 020606Eighth Place5812
9Institut Teknologi BandungGanesha ITBNinth Place5813
9University of the Philippines DilimanUP Fighting MoronsNinth Place5854
9Shanghai UniversityLarvaNinth Place5871
10Saitama UniversityMaximum-CoffeeTenth Place5925
10Saitama UniversityMaximum_TGMTenth Place5934
11National University of Singapore12TIN@NUSEleventh Place51046
13National University of SingaporeeagleThirteenth Place4382
14National University of SingaporeCode WarriorFourteenth Place4488
14Nanyang Technological UniversityKhANFourteenth Place4664
15Nanyang Technological UniversityY2FFifteenth Place4718
15National University of SingaporeNUSSOCFifteenth Place4719
15Nanyang Technological UniversityGeJeFifteenth Place4778
15BINUS UNIVERSITYACMonFifteenth Place4847
15City University of Hong Kong9.99 AcceptedFifteenth Place3219
15Nanyang Technological UniversityHiWorldFifteenth Place3234
15National Tsing Hua UniversityROHFifteenth Place3369
15Kasetsart University, ThailandT2BFifteenth Place3385
16Nanyang Technological UniversityTMNQSixteenth Place3393
16International Islamic University MalaysiaAl-KhawarizmiSixteenth Place3440
16Parahyangan UniversityH&&HSixteenth Place3495
17Soongsil UniversityInspirationsSeventeenth Place3525
18Universitas IndonesiaMakaraEighteenth Place3532
21University of Sumatera UtaraUSU - The Last OneTwenty-first Place284
22National Chiao Tung UniversityFreshfoxTwenty-second Place2168
23Parahyangan UniversityKiWiChanTwenty-third Place2307
Ateneo de Manila UniversitycxxCHonorable Mention
Informatics EducationPolymorphicHonorable Mention
University of Sumatera UtaraUSU - The Last TwoHonorable Mention
National University of SingaporeCoding BunniesHonorable Mention
Soongsil UniversityNewFaceHonorable Mention
Multimedia University, Malaysia!Honorable Mention
Nanyang Technological UniversityCODE BREAKERSHonorable Mention
Multimedia University, MalaysiaInfinityHonorable Mention
Prince of Songkla UniversityPSU-PKTHonorable Mention
Sekolah Tinggi Teknologi TelkomSTT01Honorable Mention

The truth about Problem B weirdness

The judge reference solution was wrong. The reference solution assumed that Indiana Jones cannot jump at Interval 0 (zero). Thus for a certain testcase which has a possible path using Interval 0 (zero), the reference solution won't select that path. The judges should've suspect something fishy when the top teams which can get a problem accepted in a single submission, got this problem wrong for more than 10 submissions!

As the result, few days after the contest was over, all the solutions submitted for Problem B was re-judged and the ranklist was updated. The above ranklist is the latest and final one. This is a very common problem in programming contests. Even in ACM ICPC World Finals, this kind of mistakes still happened. The best way to deal with this problem is that the judges must be aware of fishy problems during the contest. For example by examining the source codes of the contestants, not only by looking at their output only. It's possible that their code will give hints to find out the problems (especialy top teams codes!).

However, if the judges didn't manage find the mistakes during the contest time and after the award ceremony... Then there are two choices to remedy this problem: Leave the standing as if there was no problem and decide it's final or keep trying to find out the fishy problem and try to fix (if possible, re-judge) and annouce it to the contestants. I'm happy that NUS Contest Director chose the latter. The changes of the standings will impact on the wild-card decision later on (which is crucial for some top teams).

Looking at the changes of the standings, I can tell that the re-judge was done by removing the test-cases which contains Interval 0 (zero) solution. By removing test-cases which solutions involving Interval 0 (zero), this will Accept both solutions that consider or not consider Interval 0 (zero). In other words, those teams who already got Accepted will still remain get Accepted and those teams that got Wrong Answer may get Accepted after it's re-judged.

My comment about the contest

Other than the Problem B issue, I enjoyed the ACM ICPC Singapore since I can meet the other Indonesian coders and have fun with them. The problem set in overall was very easy. If there were no issue with Problem B, perhaps the champion team can solve all the 7 problems in only three out of five hours. Those teams literally code "in no time" :D.


Indonesian teams took photo together before going back.

Special Thanks

  • Dr Sun Teck TAN, Contest Director, ACM ICPC Singapore Site
  • Registration (any) committees, Steven Halim et. all.
  • Judges, Melvin Zhang et. all. and the problem setters.
  • Photographer from YoiMon, Andrian Kurniady. Thanks kur for the great camera and also thanks to Suhendry who took the pictures for me and my team.

External links

Let me know if there are any other blogs/news.

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.