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?

#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':' ');
        }
    }
}

#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':' ');
        }
    }
}

#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':' ');
        }
    }
}

#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':' ');
        }
    }
}

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.

Info | Buy | FB-page

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...

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.

Foreign Team Blogs

Local Team Blogs