Felix Halim .NET  
Google 
Name:  Message:

ACM ICPC Regional Jakarta (Dec 1, 2010) - Analysis

I was one of the problem setters and judges for this event as well as reviewers for some of the problems. I figured it would be better to share my alternate solutions for others to learn and see if others can come up with better solutions. Together, we can get better, faster :) Here is the problem set and the input/output. I encourage you to share your experience as well. If you have written some blogs about this event, please share it via the chatbox on the top right of this page.

PS: You may want to check out analysis for problem J below. STL<vector> is slow. Of course, probably the most interesting problem is problem H - Serial Numbers :) I spent > 5 hours to write the analysis that problem. Enjoy :D


Analysis Problem A - Worst Locations

Problem summary: given a tree and two starting node Xa and Xb at two different leaf of the tree, and two distances Ya and Yb. Find whether there exist a node A with distance exactly Ya steps away from Xa and another node B with distance exactly Yb steps away from Xb such that distance between A and B is bigger than Z.

After some quick sketch, you will discover that there can be up to O(2^N) possible locations for A and B. Further analysis will discover the pattern of the locations of the nodes with "exactly Y distance away from leaf X". Suppose you are exactly Y distance away from X and the tree height is N, the possible locations are: Go up the tree D steps and from there, the possible locations are all the nodes in the other subtree (not the subtree where you go up from) with height Y-D away. Now, D can vary between 0 to Y, but not all D are valid since the distance has to be exact. A distance D is valid if the height of the other subtree of the possible location is bigger or equal to the remaining distance Y-D (this will ensure the existance of such possible nodes).

Since there is at most N possible values for D, we can do brute force on both pandas' starting nodes and check for two possible pair of subtrees whether the there exists a node with distance > Z. This check is easy: suppose you have two subtrees Sa and Sb and the possible locations are Da and Db steps away from the root of the subtree, respectively. The subtree Sa and Sb have a least common ancestor C. Then the maximum distance between a possible node in the subtree Sa with another possible node in the subtree Sb is Da + Db + distance(Sa's root, C) + distance(Sb's root, C), where distance(x,y) is the distance between two node in the tree. See sample code below.

#include <stdio.h>

struct Subtree { // a Subtree with possible locations
    int L, I, D, P; // a Subtree consist of level, index, distance, and previous child
    bool valid(int N){ return N - L >= D; }     // current height must be >= D
    bool up(){ return L > 1 && D > 0; }         // can move up one level?
    void go_up(){ L--; D--; P = I; I >>= 1; }   // move to parent node
    bool down(){ return P !=- 1 && D > 0; }     // can move down one level?
    void go_down(){ L++; D--; I <<= 1; if (I==P) I++; P = -1; } // move to other child
};

// returns the maximum distance between any possible node 
// in subtree a with any possible node in subtree b
int dist(Subtree Sa, Subtree Sb){ 
    if (Sa.down()) Sa.go_down(); // must travel to the other subtree if possible
    if (Sb.down()) Sb.go_down(); // must travel to the other subtree if possible
    int ret = Sa.D + Sb.D; // downward distance of node Sa + downward distance of node Sb
    while (Sa.L != Sb.L || Sa.I != Sb.I){ // computing distance of root of Sa to root of Sb
        if (Sa.L > Sb.L) Sa.go_up(); else Sb.go_up();
        ret++; // distance of Sa and Sb to reach lca(Sa,Sb)
    }
    return ret;
}

int main(){
    int T,N,Xa,Ya,Xb,Yb,Z;
    scanf("%d",&T);
    while (T--){
        scanf("%d %d %d %d %d %d",&N,&Xa,&Ya,&Xb,&Yb,&Z);
        bool possible = false;
        for (Subtree Sa = (Subtree){ N, Xa-1, Ya, -1 }; !possible; Sa.go_up()){
            for (Subtree Sb = (Subtree){ N, Xb-1, Yb, -1 }; !possible; Sb.go_up()){
                if (Sa.valid(N) && Sb.valid(N) && dist(Sa,Sb) > Z) possible = true;
                if (!Sb.up()) break;
            }
            if (!Sa.up()) break;
        }
        puts(possible?"YES":"NO");
    }
}

Analysis Problem B - Counting BST

Problem summary: given a Binary Search Tree (BST) which shape depends on the given insertion order, and the possible range of labels to use. You are to count how many different insertion order (using the available labels) such that the resulting shape BST is the same with the given BST.

This is a combinatoric problem: among M possible labels, we want to choose N of them and use it to construct a BST. Whatever N labels we pick, we can always form a BST. Now we have pick N labels, the second problem is to count how many BST insertion orders of the N labels that will produce the same shape as the given BST.

The first problem is easily solved by computing N choose K using Dynamic Programming (again). To answer the second problem, we need to imagine how we can insert a new node to a BST. First the new node arrive at the root of the tree, we have a choice to insert a new node to the left subtree or the right subtree. So, how many ways can we do this insertion? Remember that the resulting subtree must match the shape of the given BST. So, we can look at the given BST, how many child are there in the left subtree, and the number of ways we can insert to the left is nCk[S][L], where S is the number of available labels to be inserted (which must be equal to the the number of nodes in the left + right subtree of the node) and L is the number of nodes in the left subtree of the node. The remaining S - L nodes must go to the right subtree. Of course, this has to be applied recursively on the left and the right subtree. See the function f() in the sample code below.

#include <stdio.h>

#define MAXN 1001

struct Node {
    int V;      // node's value
    int L,R;    // pointer to left and right child
    int nL,nR;  // the number of nodes in the left and right subtree
} n[MAXN];

int nCk[MAXN][MAXN], S, M = 1000003;

void add(int &root, int val){
    if (root==-1){
        n[root = S++] = (Node){ val,-1,-1,0,0 };    // new node
    } else {
        Node &r = n[root];
        if (val < r.V)              // insert to the left if the value is < root's
            add(r.L, val), r.nL++;  // insert to the left, and increment left node count
        else
            add(r.R, val), r.nR++;  // insert to the right, and increment right node count
    }
}

long long f(int root){
    if (root==-1) return 1;
    Node &r = n[root];
    long long ret = nCk[r.nL + r.nR][r.nL]; // how many ways can we insert
    ret = ret * f(r.L) % M;     // applied recursively
    ret = ret * f(r.R) % M;     // applied recursively
    return ret;
}

int main(){
    nCk[0][0] = 1;
    for (int i=1; i<MAXN; i++){
        nCk[i][0] = 1;
        for (int j=1; j<MAXN; j++)
            nCk[i][j] = (nCk[i-1][j-1] + nCk[i-1][j]) % M; // Dynamic Programming
    }

    int TC;
    scanf("%d",&TC);
    while (TC--){
        int N,T,val,root=-1; S = 1;
        scanf("%d %d",&N,&T);
        for (int i=0; i<N; i++) scanf("%d",&val), add(root,val);
        printf("%d\n", int( f(root) * nCk[T][N] % M )); // choose N labels out of available T
    }
}

Analysis Problem C - Playing with Stones

NIM game has become so popular in programming contests recently thanks to TopCoder's Algorithm Games tutorial. To my surprise, this is the first problem solved in the contest (in 12 minutes)! This could mislead other teams to think that this problem is that easy. Well, it becomes easy only when you already learn about Grundy Numbers beforehand. I recommend you to read the TopCoder's tutorial above if you do not know about NIM game or Grundy Numbers.

So, this problem is obviously a variant of a NIM game. What we have to do is to map this problem into an equivalent NIM game via Grundy Numbers. For certain game state in this problem, it is equivalent to a certain Grundy Number. You will need to sketch how the Grundy number is formed in this problem. After you've figured it out, the solution is just to xor all the Grundy numbers just like a NIM game.

#include <stdio.h>

long long Grundy(long long x){
    return x%2==0 ? x/2 : Grundy(x/2);
}

int main(){
    long long T,N,res,A;
    scanf("%lld",&T);
    while (T--){
        scanf("%lld",&N);
        for (int i=res=0; i<N; i++){
            scanf("%lld",&A);
            res ^= Grundy(A);
        }
        puts(res?"YES":"NO");
    }
}

Analysis Problem D - Arm Wrestling Tournament

Well, I have nothing to say here. This problem is just to simulate what the problem statement says.

#include <vector>
#include <algorithm>

using namespace std;

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

struct Dummy {
    int P0;   // initial strength
    int P;    // current strength
    int num;  // contestant number
} A[1<<16];

vector<int> beat[1<<16]; // keeps track who beats who
int T,N,K;

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d %d",&N,&K);
        REP(i,1<<N){
            scanf("%d",&A[i].P0);
            A[i].P = A[i].P0;   // initial strength = current strength
            A[i].num = i;       // contestant number
            beat[i].clear();    // reset the beats
        }
        for (N=1<<N; N>1; N>>=1){
            int j = 0;
            REP(i,N) if (i%2==0){
                if (A[i].P < A[i+1].P) swap(A[i], A[i+1]);     // A[i] is the winner
                A[i].P = min(A[i].P0, A[i].P - A[i+1].P + K);  // winning rules
                beat[A[i].num].push_back(A[i+1].num);          // track who beat who
                A[j++] = A[i];                                 // array compaction
            }
        }
        printf("%d\n",A[0].num+1);       // the winner
        vector<int> B = beat[A[0].num];  // the contestants that are beaten
        REP(i,B.size()-1) printf("%d ",B[i]+1);
        printf("%d\n",B.back()+1);
    }
}

Analysis Problem E - Lightning Energy Report

I am the problem setter for this problem. Well.. I made this problem so that it's supposed to be solved using Heavy-Light tree decomposition + Segment Tree. But, because of the limitation of PC2's output, the input has to be small enough to produce small enough output. As the result, a number of tricks manage to get Accepted. I will first discuss my solution first and then discuss what are the tricks that are used by the teams who solved this problem.

First observation is that, the input is a tree. So, it is a special kind of graph and usually there are tricks to speedup computations. One trick is to use Heavy-Light tree decomposition (you can Google it). This will decompose a tree into line segments so that if you are in any node in the tree and want to travel to the root of the tree, you only need to cross at most log(N) line segments. After decomposing the tree into line segments, we can build a segment tree for each line segment so that we can manipulate the values in a certain range of the line segment in O(log(N)).

The problem asks to increment all the node values between node A and B in the tree. So, there are at most O(2 * log(N)) line segments to update and only need O(log(N)) to update a range in the line segment, thus to process one update query the complexity is O(log^2(N)). See the sample code for the sample implementation.

The other teams solved this problems using tricks like:

  1. Cleverly pick the root so that the tree height is minimum. Sadly, the judge's testcase doesn't contain a linear linked list -_-, so this solution run moderately fast (as the time limit is set to quite large).
  2. Precalculate the path to the root so that for each query, only need to spend as needed steps from the two house to the least common ancestors of both house in respect to the root. This is the simplest way to code.
  3. Well.. there is a clever way to aggregate the lightning. For each lightning query, update the tree state in O(1) by marking the nodes only. Then just before printing, a DFS is performed to actually apply the value for each node. This probably is the ideal way to solve this problem. To my surprise, many teams uses this trick!

The first and second tricks should not have got Accepted, but since the Judge's testcase is weak (because of PC2's limitation) a few teams got it accepted. Only one team uses my way... it's the hard way... :P

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

using namespace std;

#define MAXN 100001

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

struct Node { int L,R,V,T; };
vector<vector<Node> > ns;
vector<vector<int> > as;

class SegmentTree {
public:
    int idx, root;
    SegmentTree(int ii){
        ns.push_back(vector<Node>());
        as.push_back(vector<int>());
        idx = ii;
    }
    void add(int v){ as[idx].push_back(v); }
    void build(){ root = rec_build(0, as[idx].size()-1); }
    void update(int x, int y, int v){ rec_update(root, 0, as[idx].size()-1, 0, x, y, v); }
    int query(int x, int y){ return rec_query(root, 0, as[idx].size()-1, 0, x, y); }

private:
    int rec_build(int x, int y){
        vector<Node> &n = ns[idx];
        vector<int> &a = as[idx];
        n.push_back((Node){0,0,0});
        int id = n.size()-1;
        if (x==y){
            n[id].T = 0;
            n[id].V = a[x];
        } else {
            int z = (x+y)/2;
            int tmp = rec_build(x,z); // if you don't use tmp -> crash!
            n[id].L = tmp;
                
            tmp = rec_build(z+1,y); // this also
            n[id].R = tmp;
            n[id].V = val(n[n[id].L],x,y) + val(n[n[id].R],x,y);
        }
        return id;
    }

    int rec_update(int r, int x, int y, int t, int qx, int qy, int v){
        assert(qx<=qy);
        vector<Node> &n = ns[idx]; n[r].T += t;
        if (qx<=x && y<=qy){ n[r].T += v; return 1; }
        if (y<qx || qy<x) return -1;
        int z = (x+y)/2; t = n[r].T; n[r].T = 0;
        int ret = rec_update(n[r].L, x,z,t, qx,qy,v) | rec_update(n[r].R, z+1,y,t, qx,qy,v);
        n[r].V = val(n[n[r].L],x,y) + val(n[n[r].R],x,y);
        return ret;
    }

    int rec_query(int r, int x, int y, int t, int qx, int qy){
        vector<Node> &n = ns[idx]; n[r].T += t;
        if (qx<=x && y<=qy) return val(n[r],x,y);
        if (y<qx || qy<x) return 0;
        int z = (x+y)/2; t = n[r].T; n[r].T = 0;
        int L = rec_query(n[r].L, x,z,t, qx,qy);
        int R = rec_query(n[r].R, z+1,y,t, qx,qy);
        return L + R;
    }

    int val(Node &n, int x, int y){
        return n.V + (y-x+1) * n.T;
    }
};

vector<int> con[MAXN];
int t[MAXN]; // t[i] = deepest child for node i

int rec(int r, int p=-1){
    int md = -1;
    REP(i,con[r].size()){
        int j = con[r][i];
        if (j==p) continue;
        int d = rec(j, r);
        if (d > md) md = d, t[r] = i;
    }
    return md + 1;
}

struct Location { int num, pos, par; };
vector<SegmentTree> sts;
Location loc[MAXN];

// r = the root index
// snum = segment tree index
// spos = root position in the current segment tree snum
// spar = parent of this segment tree snum
// p = parent of this tree traversal
void build(int r, int snum, int spos, int spar, int p){
    loc[r] = (Location){ snum, spos, spar };
    sts[snum].add(0);
    int leaf = 1;
    REP(i,con[r].size()) if (con[r][i]!=p){
        if (t[r] == i){ // i is the deepest child
            build(con[r][i], snum, spos+1, spar, r);
        } else {
            sts.push_back(SegmentTree(sts.size()));
            build(con[r][i], sts.size()-1, 0, r, r);
        }
        leaf = 0;
    }
    if (leaf) sts[snum].build();
}

int main(){
    int T;
    scanf("%d",&T);
    for (int TC=1; TC<=T; TC++){
        int root = 0, n,q,a,b,c;
        scanf("%d",&n);

        REP(i,n) con[i].clear();
        ns.clear(); as.clear(); sts.clear();

        REP(i,n-1){
            scanf("%d %d",&a,&b);
            con[a].push_back(b);
            con[b].push_back(a);
        }
        rec(root); // calculate subtree size for building the Heavy-Light tree

        sts.push_back(SegmentTree(sts.size())); // root line segment
        build(root,0,0,-1,-1); // build Segment-Tree on Heavy-Light tree

        scanf("%d",&q);
        map<int,int> spos;
        REP(i,q){
            scanf("%d %d %d",&a,&b,&c);
            spos.clear();
            for (int x=a; x!=-1; x=loc[x].par){
                int s = loc[x].num, p = loc[x].pos;
                sts[s].update(0,p,c);
                spos[s] = p;
            }
            for (int x=b,f=1; x!=-1; x=loc[x].par){
                int s = loc[x].num, p = loc[x].pos;
                if (spos.count(s)){
                    if (f){
                        f = 0;
                        if (spos[s] < p){
                            sts[s].update(0,spos[s],-c);
                            sts[s].update(spos[s],p,c);
                        } else if (p>0){
                            sts[s].update(0,p-1,-c);
                        }
                    } else {
                        sts[s].update(0,p,-c);
                    }
                } else {
                    sts[s].update(0,p,c);
                }
            }
        }

        printf("Case #%d:\n",TC);
        REP(i,n) printf("%d\n",sts[loc[i].num].query(loc[i].pos, loc[i].pos));
    }
}

Analysis Problem F - Transitive Closure

This is another bonus problem: given a graph, find out which node is reachable from which node.
Count how many pairs (i,j) where i!=j so that i is reachable from j.
A simple O(N*M) can do. That is by doing simple DFS from each node.

#include <vector>

using namespace std;

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

vector<int> con[MAXN];
int T,N,M,A,B;
char V[MAXN];

void dfs(int i){
    if (V[i]) return; else V[i] = 1;
    REP(j,con[i].size()) dfs(con[i][j]);
}

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d %d",&N,&M);
        REP(i,N) con[i].clear();
        REP(i,M){
            scanf("%d %d",&A,&B);
            con[A-1].push_back(B-1);
        }
        int cnt = 0;
        REP(i,N){
            memset(V,0,sizeof(V));
            REP(j,con[i].size()) dfs(con[i][j]);
            REP(j,N) if (i!=j && V[j]) cnt++;
        }
        printf("%d\n",cnt);
    }
}

Analysis Problem G - Just Sum It

Problem summary: given the number of available digit of 1 to 9, sum all possible numbers generated from those digits.

This is another combinatoric problem, but a bit harder than problem B. The idea is to sum individual digit by picking a digit and try to count how many ways the other available digits can be placed on the left side of it and the rest on the right side. We also need to try for all possible length for the resulting number. The maximum length of a number is the sum of all available digits (at most 81).

Suppose we want to count the sum of all possible numbers of length L using the available digits, we can focus one digit at a time. The sum of all possible number of length L with digit d fixed on a certain position p (from the least significant digit) is b * 10^(p-1) * C, where C is the number of distinct number of length L-1 that can be formed with the available digits excluding one digit d (since we already use/fix this digit). So, all we need is to sum all posibile position p on a number with length L, for all digit d. See function calc() in the sample code below. To calculate the number of distinct number with length L that can be formed with the current available digits minus one digit d, we can use Dynamic Programming. See function f() in the sample code below.

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

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

int nCk[MAXS][MAXS], memo[MAXS][10][10], T, P[10], M = 1000000007;

// returns how many ways we can form L digits,
// assuming the repository is missing one digit P[E].
// O(81 * 9 * 9 * 9)
long long f(int L, int E, int I=0){
    if (I > 9) return L == 0;
    int &ret = memo[L][I][E];
    if (ret!=-1) return ret; else ret = 0;
    int digits = P[I] + (I==E? -1 : 0); // exclude 1 digit P[E]
    for (int i=0; i<=digits && i<=L; i++)
        ret = (ret + nCk[L][i] * f(L - i, E, I+1)) % M;
    return ret;
}

// O(81 * 9 * 81)
int calc(int total){
    int sum = 0;
    REP(length, total){ // for all length 0 to total-1
        // pick one digit 'd' if it has at least 1 in the repository
        for (int d=1; d<=9; d++) if (P[d-1]>0){ 
            // cnt = count how many ways we can form a number with 'length' digits long,
            //       assuming one digit 'd' is missing form repository
            long long cnt = f(length,d-1), pw = 1;

            // try place digit d to all possible positions in a number with 
            // 'length' digits long (there are 'length+1' possible positions)
            for (int j=0; j<=length; j++){ // try placing the digit 'd' from right to left

                // the value for this digit is d * pw, where pw is 10^digits_on_the_right
                long long value = d * pw % M;

                // multiply this value with 'cnt' and add the value to global 'sum'
                sum = (sum + value * cnt) % M;

                pw = pw * 10 % M; // advance one digit to the left
            }
        }
    }
    return sum;
}

int main(){
    nCk[0][0] = 1;
    for (int i=1; i<MAXS; i++){
        nCk[i][0] = 1;
        for (int j=1; j<MAXS; j++)
            nCk[i][j] = (nCk[i-1][j-1] + nCk[i-1][j]) % M;
    }

    scanf("%d",&T);
    while (T--){
        int total = 0;
        REP(i,9) scanf("%d",&P[i]), total += P[i];
        memset(memo,-1,sizeof(memo));
        printf("%d\n", calc(total));
    }
}

It turns out the function calc() can be optimized in order of 81. That is by aggregate the digits d and possible positions p in a single loop. See the improved calc() function below.

// O(9 * 81)
int calc(int total){
    int sum = 0;
    for (int d=1; d<=9; d++) if (P[d-1]>0){
        long long pw = d;
        REP(length, total){ 
            sum = (sum + pw * f(length,d-1)) % M;
            pw = (pw * 10 + d)% M;
        }
    }
    return sum;
}

Analysis Problem H - Serial Numbers

First of all, I'd like to say that I really like this problem :) As I suspected, this is the hardest problem in this contest.

This problem is the generalization of Superstitious Skylab Tower problem which appeared in INC 2008, set by the same author: Ryan Leonel Somali. The Superstitious Skylab Tower problem only have two "opcodes", while this Serial Numbers can be up to 10 opcodes. Even though the solutions for both problems are similar (using Dynamic Programming), the difficulties arise on how to implement it efficiently. When we have only have 2 opcodes, these opcodes can be hard-coded in the DP state transitions, however if we have variable number of opcodes, K (<= 10), hard-coded solution will become too complex to write.

When I first coded an alternate solution for this problem, I think of a Binary Search + Dynamic Programming, but the states are string (the laziest and easiest-to-code DP state) and it ran too slow (> 900 seconds). Then I replaces the states into integers only (but the transitions still using strings) and it ran about 200 seconds. Finally, I precalculate the opcode string transitions, removing any string operations when computing the DP table, and it ran in less than 1 second :). Note that all these variants are based on the same DP idea: the DP states are a prefix of some opcodes, and the number of digits to be constructed.

I will disscuss 5 versions: #1 is Brute Force, #2-4 is the idea above (BS + DP), #5 is the solution used by ManiAC during the contest.

Update: from ManiAC's blog, a similar problem appeared in NorthWestern Regional Contest 2004. Seeing the ranklist, it seemed that they have solved that problem recently (just 2 months before this regional contest) and got the fastest solution?

NoAlgorithmComplexityRuntime
#1Brute ForceO(T * N * 2^31-1)Don't bother to run :P
#2Binary Search + DP with string states and transitionsO(T * N * 31 * K^7)> 900 seconds
#3Binary Search + DP with integer states and string transitionsO(T * (K^6 + N * 31 * K^3)> 200 seconds
#4Binary Search + DP with integer states and transitionsO(T * (K^6 + N * 31 * K)0.8 seconds
#5DP with integers (ManiAC's solution)O(T * (K^4 + N * K * K))0.02 seconds
Click on the corresponding row above to see the details.

#1. Brute Force

The simplest approach is to loop from number 0 to infinity and maintain the count of valid numbers. The count is incremented when the current number is valid (i.e, no opcode contained in that number). If the count have reached the target, print the current number. Of course, this very simple solution will get TLE. See the sample solution below.

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

using namespace std;

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

string op[11];
char num[20];
int K;

int brute_force(int X){
    int cnt = 0;
    for (int i=1; ; i++){
        sprintf(num,"%d",i);
        REP(j,K) if (strstr(num,op[j].c_str())) goto fail;
        if (++cnt==X) return i;
        fail:;
    }
}

int main(){
    int T,N,X;
    scanf("%d",&T);
    while (T--){
        scanf("%d",&K);
        REP(i,K) scanf("%s",num), op[i] = num;

        scanf("%d",&N);
        REP(i,N){
            scanf("%d",&X);
            printf("%d%c",brute_force(X),i+1==N?'\n':' ');
        }
    }
}

#2. Binary Search + Dynamic Programming
(with string states and transitions)

Let f(x) be a function which returns the number of valid serial numbers that are <=x.
A number is a valid serial number if there is no opcode appears in the substrings of the number.

The answer is min(Y) where f(Y) = B, where B is the batch production number, and Y = [0 .. 2^31-1].
Since the function f(x) is a non-decreasing function, a binary search can be performed to find Y.
Now, the problem is how to implement f(x) efficiently.

This solution implements f(x) using a Dynamic Programming which computes f(x) digit-by-digit from the first until the last digit. When processing the first digit, we try generate new numbers [1..9] avoiding opcodes and set the initial count = 1. When we proceed to the next digit, we try appending the previously generated numbers with a new digit [0..9] and increment the count. We need to carefully append the digits by checking whether the number is forming an opcode or becomes a prefix of some opcodes. We store the numbers that are a prefix of some opcodes in separate DP state and there can only be O(K*K) such states (i.e, there are at most O(K*K) possible opcode prefix-es).

We can calculate the state transition in O(K*K*K). That is, given a string s, find an opcode which has the longest prefix that matches one of the suffixes of s. See the function is_op() in sample code below.

The total complexity is O(T * N * 31 * K^7). That is, for each testcase T, and N queries, we perform a binary search in range [0..2^31-1]. Each binary search, we compute f(x) for each O(K) digits, where the number of states in each digit is up to O(K*K), the transition is to append O(K) digits to the current state, and after appending, we check the opcode transition in O(K*K*K). If T=100, N=100, K=10, it would take O(31 * 10^11) operations. Really slow, isn't it? :).

#include <map>
#include <string>
#include <algorithm>

using namespace std;

#define REP(i,n) for (int i=0,_n=n; i<_n; i++)
#define FORE(i,a) for (__typeof(a.begin()) i=a.begin(); i!=a.end(); i++)

map<long long, long long> memo;
string op[11];
char num[20];
int K;

// return 2:forbidden number, 1:potential to be forbidden, 0:clean
int is_op(string &s){ // O(K*K*K)
    REP(i,K) if (s.find(op[i])!=string::npos) return 2; // s is a forbidden number
    while (s.length() > 0){
        REP(i,K) if (op[i].find(s) == 0) return 1;      // s contains a prefix of some opcode
        s = s.substr(1,s.length()-1);
    }
    return 0;   // s is clean
}

// returns how many valid numbers that are <= x
long long f(long long x){
    if (memo.count(x)) return memo[x];
    sprintf(num,"%lld",x);
    map<pair<string,bool>,long long> dp; // DP[s][below] = how many valid number <= x
    for (int i=0; num[i]; i++){          // s = some opcode prefix, below = the number <= x
        map<pair<string,bool>,long long> ndp;
        for (int d=1; d<10 && (i>0 || d<=num[0]-'0'); d++){  // assume a new number is formed
            string s = ""; s += '0'+d;
            if (is_op(s)==2) continue;
            bool below = i>0 || d < num[0]-'0';
            ndp[make_pair(s,below)] += 1;
        }
        FORE(mi,dp){                     // try appending the previous numbers with new digits
            string s = mi->first.first;
            bool below = mi->first.second;
            long long cnt = mi->second;
            for (int d=0; d<10 && (below || d<=num[i]-'0'); d++){ // d = digit to be appended
                string ns = s; ns += '0'+d;
                if (is_op(ns)==2) continue;
                bool nbelow = below || (d < num[i]-'0');
                ndp[make_pair(ns,nbelow)] += cnt;
            }
        }
        dp = ndp;
        assert(dp.size() <= (K+1)*(K+1)*2 + 4); // the number of DP states per digit is O(K*K)
    }
    long long ret = 0;
    FORE(i,dp) ret += i->second;
    return memo[x] = ret;
}

long long bsearch(int B){
    long long lo=0, hi=1024, res=-1;
    while (f(hi) < B) lo=hi, hi*=2; hi++;    // just to find the initial (lo,hi)
    while (lo<=hi){
        long long mid = (lo+hi)/2, cnt = f(mid);
        if (cnt < B) lo = mid+1; else res = mid, hi = mid-1;
    }
    return res;
}

int main(){
    int T,N,B;
    scanf("%d",&T);
    while (T--){
        scanf("%d",&K);
        REP(i,K) scanf("%s",num), op[i] = num;

        memo.clear();
        scanf("%d",&N);
        REP(i,N){
            scanf("%d",&B);
            printf("%lld%c",bsearch(B),i+1==N?'\n':' ');
        }
    }
}

#3. Binary Search + Dynamic Programming
(with integer states and string transitions)

The general idea is still the same with algorithm #2, but the states is changed to integers, therefore the DP can be implemented using plain array rather than STL <map>. This gives minor O(log(K*K)) performance improvement. This can be done because the substring must be in one of the opcodes, therefore, instead of storing a string, we can store it as integers pointing to an opcode index and its starting position. Another DP state from algorithm #2 that can be removed is the below. We don't need to keep track whether it's currently below x or not by never generating numbers larger than x.

Changing the way we compute the DP matters. It turns out that the "DP on the fly" in algorithm #2 is not leveraging memoization technique. While it can do DP with only O(K*K) states, it will have to recalculate for every query (there are N queries). So, it's better to include the length of the remaining digits into the DP states so that each query can use the memo. Thus, we can save an order of O(k) for one of the inner loop in function f().

The total complexity is O(T * (K^6 + N * 31 * K^3). For each testcase, the memoization will need O(K^6) (see the rec() function) to be filled in. Assuming the memo already filled in and returns in O(1), then for each query we only need to do binary search O(31) with O(K*K*K) for computing f(x). If N=100, K=10 then it is O(T * 31 * 10^5). So, it's about 3 million operations per testcase. It should be fast enough, but since we are still using string for the transitions, the constant factor the innermost operations is too large. The next algorithm #4 fixes this problem.

#include <string>
#include <vector>

using namespace std;

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

int memo[11][11][11]; // uses plain array
vector<string> op;
char num[20];

// return -1 if s is an opcode
// return the index of an opcode which has the longest prefix
//        that matches one of the suffixes of s.
// return 0 if s doesn't contain any opcode prefix
int is_op(string &s){
    REP(i,op.size()) if (s.find(op[i])!=string::npos) return -1;
    while (s.length() > 0){
        REP(i,op.size()) if (op[i].find(s) == 0) return i;
        s = s.substr(1,s.length()-1);
    }
    return 0;
}

// rem = remaining digits to be processed
// s = string with possible an opcode prefix (if exists)
// O(K * K*K * K*K*K)
int rec(int rem, string s){ // parameter size is O(K * K*K)
    int oidx = is_op(s);    // translate string s to (oidx, opos) in O(K*K*K)
    if (oidx==-1) return 0;
    if (rem==0) return 1;
    int opos = oidx==op.size()? 0 : s.length();
    string p = oidx<op.size()? op[oidx].substr(0,opos) : "";
    int &ret = memo[rem][oidx][opos];
    if (ret!=-1) return ret; else ret = 0;
    REP(d,10) ret += rec(rem-1, p + string(1,'0'+d)); // try append new digits
    return ret;
}

// O(K * K * K)
int f(int x){
    if (x==0) return 0;
    sprintf(num,"%d",x);
    string p = "";
    int ret = 0;
    for (int i=0,len=strlen(num); i<len; i++){   // never generate number > x
        REP(d,10) if (i!=0 || d!=0){
            if (i>0 && d>0) ret += rec(len-i-1, string(1,'0'+d));
            if ('0'+d < num[i]) ret += rec(len-i-1, p + string(1,'0'+d));
        }
        p += num[i];
    }
    if (is_op(p)!=-1) ret++; // here is_op() uses O(K*K*K)
    return ret;
}

int bsearch(int B){
    int lo=0, hi=2147483647;
    while (lo+1 < hi){
        int mid = lo + (hi-lo)/2;
        if (f(mid) < B)
            lo = mid;
        else
            hi = mid;
    }
    return hi;
}

int main(){
    int T,K,N,X;
    scanf("%d",&T);
    while (T--){
        scanf("%d",&K);
        op.clear();
        REP(i,K) scanf("%s",num), op.push_back(num);
        
        memset(memo,-1,sizeof(memo));
        scanf("%d",&N);
        REP(i,N){
            scanf("%d",&X);
            printf("%d%c",bsearch(X),i+1==N?'\n':' ');
        }
    }
}

#4. Binary Search + Dynamic Programming
(with integer for both states and transitions)

As you may have noticed in algorithm #3 that the bottleneck is on the is_op() function which takes O(K*K*K) which is used in subroutines for the rec() function. The last optimization is to precalculate the transitions (the is_op() function), so that each transition can be done in O(1). In a sense, algorithm #3 is also flying some DP states, in this case: whether the current state is the first digit. By incorporating this into the memoization, the function f(x) can be made faster from O(K*K) to O(K).

The total complexity is O(T * (K^6 + N * 31 * K). For each testcase, the precalculation will need O(K^6) (see the precalculateTransitions() function). Assuming the memo already filled in and returns in O(1), then for each query we only need to do binary search O(31) with O(K) for computing f(x). If N=100, K=10 then it is O(T * 10^6), that is O(10^6) per testcase at worst. Note that this solution has far lower constant factor than algorithm #3 since no string operations involved. The complexity of computing the DP transition can be improved using trie and suffix link like structure, but this is not needed to get AC.

I've spent ~5 hours to refine my code from algorithm #2, to #3 then to #4. I'm surprised there was a team that could solve this problem in contest time. Moreover, the team (ManiAC) solved it with even better complexity (see algorithm #5).

#include <string>
#include <vector>

using namespace std;

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

int memo[11][11][11][2][11]; // memo states are in integer
int trans[11][11][11][2];    // transitions are in integer
vector<string> op;
char num[20];

// O(10*10*10*2*10*10)
int rec(int rem, int oidx, int opos, int first, int mx){
    if (rem==0) return 1;
    int &ret = memo[rem][oidx][opos][first][mx];
    if (ret!=-1) return ret; else ret = 0;
    REP(d,mx) if (!first || d>0){
        int noidx = trans[oidx][opos][d][0];
        int nopos = trans[oidx][opos][d][1];
        ret += noidx==-1? 0 : rec(rem-1, noidx, nopos, 0, 10);
    }
    return ret;
}

// O(10)
int f(int x){
    if (x==0) return 0; else sprintf(num,"%d",x);
    int ret=0, oidx=op.size(), opos=0, len=strlen(num);
    REP(i,len){
        if (i>0) ret += rec(len-i, op.size(), 0, 1, 10);
        if (oidx!=-1){
            ret += rec(len-i, oidx, opos, i==0, num[i]-'0');
            int a = trans[oidx][opos][num[i]-'0'][0];
            int b = trans[oidx][opos][num[i]-'0'][1];
            oidx = a; opos = b;
        }
    }
    return ret + (oidx!=-1);
}

// O(31 * 10)
int bsearch(int X){
    int lo=0, hi=2147483647;
    while (lo+1 < hi){
        int mid = lo + (hi-lo)/2;
        if (f(mid) < X)
            lo = mid;
        else
            hi = mid;
    }
    return hi;
}

// O(10*10*10)
int is_op(string &s){
    REP(i,op.size()) if (s.find(op[i])!=string::npos) return -1;
    while (s.length() > 0){
        REP(i,op.size()) if (op[i].find(s) == 0) return i;
        s = s.substr(1,s.length()-1);
    }
    return op.size();
}

// O(10*10*10 * 10*10*10)
void precalculateTransitions(){
    REP(d,10){
        string s = string(1,'0'+d);
        int &a = trans[op.size()][0][d][0]; a = is_op(s);
        int &b = trans[op.size()][0][d][1];
        b = (a==op.size() || a==-1)? 0 : s.length();
    }
    REP(oidx,op.size()){
        string s1 = "";
        REP(opos,op[oidx].length()){
            s1 += op[oidx][opos];
            REP(d,10){              // try append digit d to current op codes
                string s = s1 + string(1,'0'+d);
                int &a = trans[oidx][opos+1][d][0]; a = is_op(s); // O(K*K*K)
                int &b = trans[oidx][opos+1][d][1];
                b = (a==op.size() || a==-1)? 0 : s.length();
            }
        }
    }
}

int main(){
    int T,K,N,X;
    scanf("%d",&T);
    while (T--){
        op.clear();
        scanf("%d",&K);
        REP(i,K) scanf("%s",num), op.push_back(num);

        precalculateTransitions();      // O(10*10*10 * 10*10*10)
        memset(memo,-1,sizeof(memo));   // O(10*10*10 *  2*10*10)

        scanf("%d",&N);
        REP(i,N){
            scanf("%d",&X);
            printf("%d%c",bsearch(X),i+1==N?'\n':' ');
        }
    }
}

#5. Dynamic Programming
(with integer states and transitions)

Team ManiAC solved this problem elegantly. They use trie and employ some kind of suffix links to build the transitions in O(K^4). They use two DP tables: the one is storing the count of serial numbers with possible leading zeros, the other is the count of serial numbers without leading zeros. Both DP states are dp[length][transition-state] = count of serial numbers. As discussed in algorithm #2, the number of state-transitions is O(K*K).

To answer a query, they don't use binary search. Instead, they first find the length L of the answer by looking up from the second DP table, terminating at the first length that exceeds the query number. To get the exact serial number, they loop L times to construct L digits. For each digit, they use the first DP table to find the first digit that have serial number count >= x. Thus the complexity to answer a query is O(K*K).

The total complexity is O(T * (K^4 + N * K * K). It runs blindingly fast.

Analysis Problem I - Romantic Date

Greedy strategy works. For each Wibowo card, find the highest of his girlfriend's card that is lower than the Wibowo's card (if any) and win it. Other strategies that yields the highest number of win can be reordered to match this strategy.

#include <stdio.h>

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

int T,V,has[100];
char C[10];

int main(){
    scanf("%d",&T);
    while (T--){
        REP(i,60) has[i] = 0;
        REP(i,26){
            scanf("%s",C);
            switch (C[0]){
                case 'T' : V = 8; break;
                case 'J' : V = 9; break;
                case 'Q' : V = 10; break;
                case 'K' : V = 11; break;
                case 'A' : V = 12; break;
                default : V = C[0]-'2';
            }
            V *= 4;
            switch (C[1]){
                case 'D' : V += 0; break;
                case 'C' : V += 1; break;
                case 'H' : V += 2; break;
                case 'S' : V += 3; break;
            }
            has[V] = 1;
        }

        int res = 0;
        for (int i=60; i>=0; i--) if (has[i]==1)
            for (int j=i-1; j>=0; j--) if (has[j]==0)
                { has[j] = 2; res++; break; }
        printf("%d\n",res);
    }
}

Analysis Problem J - Fire Drill

This problem can be decomposed into two sub-problems. The first is to calculate the shortest path from the starting point to all volunteers. The second is to calculate the minimum time to get as many points as possible given a limited time. The first sub-problem is easily solved using BFS, and the second sub-problem is the classical DP knapsack.

There is an interesting slowness phenomenon of using vector is discussed below.

#include <queue>

using namespace std;

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

int dr[] = {-1,1,0,0};
int dc[] = {0,0,-1,1};
char B[11][101][102];
int vis[11][101][102];
int P[11][101][102];
int T,L,H,W,N,S;

struct Node {
    int floor, row, col;
    int state(){ return B[floor][row][col]; }
    int points(){ return P[floor][row][col]; }
    int canVisit(){
        if (row<0 || row>=H || col<0 || col>=W || 
            state()=='X' || vis[floor][row][col]) return false;
        return vis[floor][row][col] = true;
    }
};

int main(){
    clock_t sc = clock();
    scanf("%d",&T);
    while (T--){
        scanf("%d %d %d %d %d",&L,&H,&W,&N,&S);
        REP(i,L) REP(j,H) scanf("%s",B[i][j]);
        REP(i,N){ int f,r,c,p;
            scanf("%d %d %d %d",&f,&r,&c,&p);
            B[f-1][r-1][c-1] = 'V';
            P[f-1][r-1][c-1] = p;
        }
        
        queue<Node> q;
        memset(vis,0,sizeof(vis));
        REP(i,L) REP(j,H) REP(k,W) if (B[i][j][k]=='S')
            q.push((Node){i,j,k}), vis[i][j][k] = 1;

        vector<pair<int,int> > timepoint; // the time to rescue a volunteer and its point
        for (int dis=0; q.size(); dis++)
            REP(qq,q.size()){
                Node cur = q.front(), next = cur; q.pop();
                switch (cur.state()){
                    case 'V' : timepoint.push_back(make_pair(dis*3, cur.points())); break;
                    case 'U' : next.floor++; if (next.canVisit()) q.push(next); break;
                    case 'D' : next.floor--; if (next.canVisit()) q.push(next); break;
                }
                REP(k,4){
                    next = (Node){ cur.floor, cur.row + dr[k], cur.col + dc[k] };
                    if (next.canVisit()) q.push(next);
                }           
            }

        vector<int> dp(S+1); // DP knapsack
        REP(i,timepoint.size()){
            for (int s=S; s>0; s--){
                int t = timepoint[i].first;
                int p = timepoint[i].second;
                if (s - t >= 0) dp[s] >?= dp[s-t] + p;
            }
        }
        printf("%d\n",dp[S]);
    }
    fprintf(stderr,"%.3lf\n",1.0*(clock()-sc)/CLOCKS_PER_SEC);
}

If you run the above code using this input, the runtime is around 7.8 seconds (on my laptop).
Now, if you change the DP knapsack a bit to:

    vector<int> dp(S+1); // DP knapsack
    REP(i,timepoint.size()){
        int t = timepoint[i].first;
        int p = timepoint[i].second;
        for (int s=S; s>0; s--){
            if (s - t >= 0) dp[s] >?= dp[s-t] + p;
        }
    }
    printf("%d\n",dp[S]);

The runtime improves to 4.5 seconds. Well... it makes sense, but 3 seconds difference is kinda huge, don't you think?
If you change the vector using plain array like this:

    int dp[10010] = {0}; // DP knapsack
    REP(i,timepoint.size()){
        int t = timepoint[i].first;
        int p = timepoint[i].second;
        for (int s=S; s>0; s--){
            if (s - t >= 0) dp[s] >?= dp[s-t] + p;
        }
    }
    printf("%d\n",dp[S]);

The runtime becomes 1.5 seconds. Whoaa... does vector allocation THAT slow?
If STL <vector> is THAT slow... how about other STLs?!?!
Anyone can confirm this? post something on the chatbox at the top right of this page.

Based on this observation, we increased the timelimit only for this problem.

Rank Team Name Solved Time A B C D E F G H I J Total att/solv
1 +1 ironwood branch
National Taiwan University
9 670 1/170 1/69 1/22 1/37 2/28 1/60 1/115 5/-- 1/56 1/93 15/9
2 Halo
Shanghai Jiaotong University
9 1106 5/241 1/112 1/65 1/31 2/106 1/69 1/134 0/-- 1/48 3/160 16/9
3 ManiAC
Chinese University of Hong Kong
9 1128 3/123 1/152 1/24 1/34 1/72 3/204 12/-- 2/225 1/25 3/129 28/9
4 YummyBomb
Shanghai Jiaotong University
9 1151 1/209 1/185 1/106 1/62 1/148 1/115 1/162 5/-- 2/40 1/104 15/9
5 NTU GladiaToRs
Nanyang Technological University
9 1205 4/241 1/102 2/35 1/41 2/74 1/104 2/174 0/-- 1/16 6/198 20/9
6 IsolatE
Chinese University of Hong Kong
9 1224 2/194 2/206 1/12 2/43 1/122 2/75 3/293 0/-- 1/47 2/92 16/9
7 Saklar Lhompat
University of Indonesia
8 1101 9/-- 1/140 1/35 1/17 2/173 1/121 3/259 0/-- 2/60 2/196 22/8
8 NTU Diversity
Nanyang Technological University
8 1253 4/-- 3/286 1/52 1/57 3/185 1/78 1/223 0/-- 1/27 4/205 19/8
9 Dongskar Pedongi II
Institut Teknologi Bandung
8 1291 12/-- 1/188 2/78 3/78 1/111 1/149 2/267 1/-- 1/37 8/163 32/8
10 40010
Tokyo Institute of Technology
7 925 0/-- 2/260 1/30 1/62 1/206 1/82 0/-- 0/-- 1/42 4/163 11/7
11 Hope
Bina Nusantara University
7 1066 0/-- 2/278 1/44 1/58 1/219 1/88 3/-- 0/-- 1/37 5/242 15/7
12 M-Queen
Chinese University of Hong Kong
6 730 0/-- 0/-- 1/65 1/56 7/-- 1/84 1/224 0/-- 1/27 4/214 16/6
13 Arcadia
Chinese University of Hong Kong
5 698 0/-- 3/-- 1/74 5/123 0/-- 1/108 0/-- 0/-- 1/66 3/207 14/5
14 Puissance
Chinese University of Hong Kong
5 721 0/-- 0/-- 1/39 1/57 0/-- 4/174 0/-- 0/-- 1/18 6/273 13/5
15 H2S
Bina Nusantara University
4 541 0/-- 0/-- 0/-- 2/49 0/-- 1/137 0/-- 0/-- 1/72 2/243 6/4
16 ein
Gadjah Mada University
4 571 0/-- 0/-- 0/-- 1/26 0/-- 3/158 0/-- 0/-- 2/44 3/243 9/4
17 TePeBe
Institut Teknologi Bandung
4 592 0/-- 1/279 8/-- 1/16 1/255 1/-- 0/-- 0/-- 1/42 2/-- 15/4
18 Eleazar
University of Indonesia
4 627 0/-- 0/-- 1/131 1/24 1/-- 6/-- 0/-- 0/-- 1/42 8/290 18/4
19 Joglosemar
Institut Teknologi Bandung
4 659 0/-- 0/-- 0/-- 2/70 2/280 1/155 0/-- 0/-- 1/114 0/-- 6/4
20 Deadlock
Bina Nusantara University
4 691 0/-- 0/-- 4/-- 1/64 1/-- 2/288 0/-- 0/-- 1/87 2/212 11/4
21 NTUsiasm
Nanyang Technological University
3 110 0/-- 2/-- 0/-- 1/35 7/-- 1/54 0/-- 0/-- 1/21 1/-- 13/3
22 Jambanan
Nanyang Technological University
3 184 0/-- 6/-- 0/-- 1/26 0/-- 1/114 0/-- 0/-- 1/44 0/-- 9/3
23 Faith
Bina Nusantara University
3 230 0/-- 0/-- 2/47 2/30 0/-- 2/-- 0/-- 0/-- 1/113 8/-- 15/3
24 CUStar02
Chulalongkorn University
3 238 0/-- 0/-- 2/-- 2/61 2/-- 2/89 0/-- 0/-- 1/48 1/-- 10/3
25 ITT Vida
Institut Teknologi Telkom
3 418 0/-- 0/-- 0/-- 2/62 0/-- 6/-- 0/-- 0/-- 1/95 1/241 10/3
26 Larva 1
Shanghai University
3 547 0/-- 5/-- 4/-- 1/33 0/-- 0/-- 0/-- 0/-- 3/74 7/280 20/3
27 kulikoding
Universitas Pelita Harapan
3 564 0/-- 0/-- 3/-- 3/93 3/-- 1/286 0/-- 0/-- 1/145 0/-- 11/3
28 10-2
Bina Nusantara University
3 604 0/-- 0/-- 0/-- 2/149 0/-- 3/288 0/-- 0/-- 1/107 0/-- 6/3
29 Numpang Ngoding
University of Indonesia
3 627 0/-- 0/-- 2/-- 2/92 4/-- 6/213 0/-- 0/-- 4/142 0/-- 18/3
30 AO
Nanyang Technological University
3 759 0/-- 2/-- 7/-- 3/197 0/-- 1/250 0/-- 0/-- 2/252 0/-- 15/3
31 Ditolak jadi asdos programming
University of Indonesia
2 94 0/-- 0/-- 4/-- 1/46 0/-- 2/-- 0/-- 0/-- 2/28 0/-- 9/2
32 TC Pacifista
Institut Teknologi Sepuluh Nopember
2 100 0/-- 0/-- 2/-- 1/30 0/-- 3/-- 0/-- 0/-- 2/50 1/-- 9/2
33 ITT SOS Brigade
Institut Teknologi Telkom
2 118 3/-- 0/-- 0/-- 1/48 3/-- 0/-- 0/-- 0/-- 1/70 0/-- 8/2
34 lolypop
STMIK Mikroskil
2 118 0/-- 0/-- 1/-- 1/41 4/-- 0/-- 0/-- 0/-- 1/77 0/-- 7/2
35 KueKiaTheng
Bina Nusantara University
2 129 0/-- 0/-- 0/-- 1/43 0/-- 1/-- 0/-- 0/-- 1/86 0/-- 3/2
36 Padawan
Institut Teknologi Sepuluh Nopember
2 170 0/-- 0/-- 1/-- 1/72 0/-- 2/-- 0/-- 0/-- 1/98 0/-- 5/2
37 wFa2.0
University of Indonesia
2 177 0/-- 0/-- 0/-- 1/35 0/-- 3/-- 0/-- 0/-- 2/122 2/-- 8/2
38 playfunfun
Bina Nusantara University
2 198 0/-- 0/-- 3/-- 1/66 0/-- 0/-- 1/-- 0/-- 3/92 0/-- 8/2
39 TheLastCodeBlender
University of Surabaya
2 201 0/-- 0/-- 0/-- 1/107 0/-- 5/-- 0/-- 0/-- 1/94 0/-- 7/2
40 DnD
Parahyangan University
2 212 0/-- 0/-- 1/-- 1/136 0/-- 12/-- 0/-- 0/-- 1/76 0/-- 15/2
41 numpang_Makan
University of Indonesia
2 224 0/-- 0/-- 5/-- 1/117 2/-- 2/-- 0/-- 0/-- 3/67 0/-- 13/2
42 almostGraduate
University of Indonesia
2 228 0/-- 0/-- 0/-- 1/56 2/-- 1/-- 0/-- 0/-- 2/152 0/-- 6/2
43 Autovajin
Institut Teknologi Sepuluh Nopember
2 236 0/-- 0/-- 4/-- 3/116 0/-- 1/-- 0/-- 0/-- 1/80 0/-- 9/2
44 Legendroid
Parahyangan University
2 245 0/-- 0/-- 2/-- 1/65 0/-- 3/-- 0/-- 0/-- 3/140 0/-- 9/2
45 kulikodingHy
Universitas Pelita Harapan
2 266 0/-- 0/-- 0/-- 2/161 0/-- 0/-- 0/-- 0/-- 1/85 0/-- 3/2
46 Law Let Me AC
Bina Nusantara University
2 275 0/-- 0/-- 2/-- 3/128 0/-- 0/-- 0/-- 0/-- 1/107 3/-- 9/2
47 Satijan
University of Indonesia
2 279 0/-- 0/-- 7/-- 2/99 1/-- 0/-- 0/-- 0/-- 3/120 0/-- 13/2
48 PlugNPlay
Sekolah Tinggi Teknik Surabaya
2 289 0/-- 0/-- 0/-- 2/135 0/-- 6/-- 0/-- 0/-- 2/114 0/-- 10/2
49 Nerd
Sekolah Tinggi Teknik Surabaya
2 328 0/-- 0/-- 0/-- 3/192 0/-- 0/-- 0/-- 2/-- 1/96 0/-- 6/2
50 Coding's Angels
University of Indonesia
2 411 0/-- 0/-- 1/-- 7/139 0/-- 5/-- 0/-- 0/-- 3/112 0/-- 16/2
51 yoonA
Petra Christian University
2 475 0/-- 0/-- 1/-- 2/252 0/-- 0/-- 0/-- 1/-- 1/203 0/-- 5/2
52 inspanning
Parahyangan University
1 102 0/-- 0/-- 0/-- 5/-- 4/-- 3/-- 0/-- 1/-- 1/102 0/-- 14/1
53 HantuPuskom
University of Sumatera Utara
1 203 0/-- 0/-- 0/-- 10/-- 0/-- 1/-- 1/-- 0/-- 2/183 0/-- 14/1
54 ITT VCIOUS
Institut Teknologi Telkom
1 220 0/-- 0/-- 2/-- 3/180 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 5/1
55 ITT DividedByZero
Institut Teknologi Telkom
1 263 0/-- 0/-- 0/-- 4/203 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 4/1
56 JoRoGe
Petra Christian University
1 327 0/-- 0/-- 3/-- 1/-- 0/-- 0/-- 0/-- 0/-- 3/287 0/-- 7/1
57 CrossEdge
Sekolah Tinggi Teknik Surabaya
0 0 0/-- 0/-- 3/-- 2/-- 0/-- 0/-- 0/-- 0/-- 1/-- 0/-- 6/0
57 HantuPuskom.Jr
University of Sumatera Utara
0 0 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/0
57 IIUM cat-us-trophy
International Islamic University Malaysia
0 0 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/0
57 ITT Guntur
Institut Teknologi Telkom
0 0 0/-- 0/-- 0/-- 3/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 3/0
57 ITT LUCKY
Institut Teknologi Telkom
0 0 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/0
57 kode racun
University of Sumatera Utara
0 0 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/0
57 pssst...
University of Sumatera Utara
0 0 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/0
57 ShadowEvil
Sekolah Tinggi Teknik Surabaya
0 0 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/0
57 Sphinx
Bina Nusantara University
0 0 0/-- 0/-- 1/-- 0/-- 0/-- 0/-- 0/-- 2/-- 0/-- 0/-- 3/0
57 TouchEvent
Sekolah Tinggi Teknik Surabaya
0 0 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/0
57 Tpl08
University of Sumatera Utara
0 0 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/0
Total (attempt/solved) 44/6 35/12 92/16 113/53 61/13 107/25 32/9 19/1 82/54 93/20 678/209

Competitive Programming Book

If you are new to programming contest, you may feel that the discussions I write in this writeup is too short and you hardly understand it. For example:

  • How to find the shortest path in a graph?
  • How to check whether a node is reachable from other node in a graph?
  • What are other popular graphs problems occuring in programming contest?
  • What is Dynamic Programming? What are the common examples of it?
  • And so on...
These things have become mandatory things that any contestants should know. Often, in discussions forums people discuss the key to solve a problem in one paragraph and you are expected to know the rest.

Recently, my brother and I wrote a book to help new computer science students to quickly learn the types of problems that are popular and frequently occurs in programming contests like ACM ICPC and IOI. The book discusses the important algorithms and points out a set of problems for the exercises.

For more information about this book, click a link on the right figure.













© Felix Halim 2009 (Loaded in 0.02803 secs)