Enter your search terms
Submit search form
Story & | &
Research & | &
Programming & | &
Scripts & | &
Member & | &
Miscellaneous
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 :)
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)
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 =
for (Subtree Sa = (Subtree){ N, Xa-1, Ya, -1 }; ! Sa.go_up()){
for (Subtree Sb = (Subtree){ N, Xb-1, Yb, -1 }; ! Sb.go_up()){
if (Sa.valid(N) && Sb.valid(N) && dist(Sa,Sb) > Z) possible =
if (!Sb.up())
if (!Sa.up())
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 {
// node's value
// 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
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
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
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
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
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>
#define REP(i,n) for (int i=0,_n=n; i&_n; i++)
struct Dummy {
// initial strength
// current strength
// 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 =
// 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:
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).
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.
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>
#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> >
vector&vector&int> >
class SegmentTree {
SegmentTree(int ii){
ns.push_back(vector&Node>());
as.push_back(vector&int>());
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); }
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];
int z = (x+y)/2;
int tmp = rec_build(x,z); // if you don't use tmp -> crash!
tmp = rec_build(z+1,y); // this also
n[id].V = val(n[n[id].L],x,y) + val(n[n[id].R],x,y);
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 +=
if (qx&=x && y&=qy){ n[r].T += 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);
int rec_query(int r, int x, int y, int t, int qx, int qy){
vector&Node> &n = ns[idx]; n[r].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];
int d = rec(j, r);
if (d > md) md = d, t[r] =
return md + 1;
struct Location { int num, pos, };
vector&SegmentTree>
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);
sts.push_back(SegmentTree(sts.size()));
build(con[r][i], sts.size()-1, 0, r, r);
if (leaf) sts[snum].build();
int main(){
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>
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].
sts[s].update(0,p,c);
for (int x=b,f=1; x!=-1; x=loc[x].par){
int s = loc[x].num, p = loc[x].
if (spos.count(s)){
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);
sts[s].update(0,p,-c);
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>
#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]) 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();
scanf("%d %d",&A,&B);
con[A-1].push_back(B-1);
int cnt = 0;
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 = ;
// 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) 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;
// 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&= 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
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 =
REP(length, total){
sum = (sum + pw * f(length,d-1)) % M;
pw = (pw * 10 + d)% M;
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
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
. Seeing , 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>
#define REP(i,n) for (int i=0,_n=n; i&_n; i++)
string op[11];
char num[20];
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()))
if (++cnt==X)
int main(){
int T,N,X;
scanf("%d",&T);
while (T--){
scanf("%d",&K);
REP(i,K) scanf("%s",num), op[i] =
scanf("%d",&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>
#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>
string op[11];
char num[20];
// 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);
// 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[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>
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)
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.
bool below = mi->first.
long long cnt = mi->
for (int d=0; d&10 && (below || d&=num[i]-'0'); d++){ // d = digit to be appended
string ns = ns += '0'+d;
if (is_op(ns)==2)
bool nbelow = below || (d & num[i]-'0');
ndp[make_pair(ns,nbelow)] +=
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->
return memo[x] =
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;
int main(){
int T,N,B;
scanf("%d",&T);
while (T--){
scanf("%d",&K);
REP(i,K) scanf("%s",num), op[i] =
memo.clear();
scanf("%d",&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>
#define REP(i,n) for (int i=0,_n=n; i&_n; i++)
int memo[11][11][11]; // uses plain array
vector&string>
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)
s = s.substr(1,s.length()-1);
// 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) else ret = 0;
REP(d,10) ret += rec(rem-1, p + string(1,'0'+d)); // try append new digits
// 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& 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)
int bsearch(int B){
int lo=0, hi=;
while (lo+1 & hi){
int mid = lo + (hi-lo)/2;
if (f(mid) & B)
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);
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>
#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>
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) 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);
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 = opos =
return ret + (oidx!=-1);
// O(31 * 10)
int bsearch(int X){
int lo=0, hi=;
while (lo+1 & hi){
int mid = lo + (hi-lo)/2;
if (f(mid) & X)
// 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)
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 *
scanf("%d",&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;
case 'J' : V = 9;
case 'Q' : V = 10;
case 'K' : V = 11;
case 'A' : V = 12;
default : V = C[0]-'2';
switch (C[1]){
case 'D' : V += 0;
case 'C' : V += 1;
case 'H' : V += 2;
case 'S' : V += 3;
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++; }
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>
#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,
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 vis[floor][row][col] =
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] =
queue&Node>
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> > // 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 = q.pop();
switch (cur.state()){
case 'V' : timepoint.push_back(make_pair(dis*3, cur.points()));
case 'U' : next.floor++; if (next.canVisit()) q.push(next);
case 'D' : next.floor--; if (next.canVisit()) q.push(next);
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].
int p = timepoint[i].
if (s - t >= 0) dp[s] >?= dp[s-t] +
printf("%d\n",dp[S]);
fprintf(stderr,"%.3lf\n",1.0*(clock()-sc)/CLOCKS_PER_SEC);
If you run the above code using , 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].
int p = timepoint[i].
for (int s=S; s>0; s--){
if (s - t >= 0) dp[s] >?= dp[s-t] +
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].
int p = timepoint[i].
for (int s=S; s>0; s--){
if (s - t >= 0) dp[s] >?= dp[s-t] +
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.
Total att/solv
+1 ironwood branch
National Taiwan University
Shanghai Jiaotong University
Chinese University of Hong Kong
Shanghai Jiaotong University
NTU GladiaToRs
Nanyang Technological University
Chinese University of Hong Kong
Saklar Lhompat
University of Indonesia
NTU Diversity
Nanyang Technological University
Dongskar Pedongi II
Institut Teknologi Bandung
Tokyo Institute of Technology
Bina Nusantara University
Chinese University of Hong Kong
Chinese University of Hong Kong
Chinese University of Hong Kong
Bina Nusantara University
Gadjah Mada University
Institut Teknologi Bandung
University of Indonesia
Joglosemar
Institut Teknologi Bandung
Bina Nusantara University
Nanyang Technological University
Nanyang Technological University
Bina Nusantara University
Chulalongkorn University
Institut Teknologi Telkom
Shanghai University
kulikoding
Universitas Pelita Harapan
Bina Nusantara University
Numpang Ngoding
University of Indonesia
Nanyang Technological University
Ditolak jadi asdos programming
University of Indonesia
TC Pacifista
Institut Teknologi Sepuluh Nopember
ITT SOS Brigade
Institut Teknologi Telkom
STMIK Mikroskil
KueKiaTheng
Bina Nusantara University
Institut Teknologi Sepuluh Nopember
University of Indonesia
playfunfun
Bina Nusantara University
TheLastCodeBlender
University of Surabaya
Parahyangan University
numpang_Makan
University of Indonesia
almostGraduate
University of Indonesia
Institut Teknologi Sepuluh Nopember
Legendroid
Parahyangan University
kulikodingHy
Universitas Pelita Harapan
Law Let Me AC
Bina Nusantara University
University of Indonesia
Sekolah Tinggi Teknik Surabaya
Sekolah Tinggi Teknik Surabaya
Coding's Angels
University of Indonesia
Petra Christian University
inspanning
Parahyangan University
HantuPuskom
University of Sumatera Utara
ITT VCIOUS
Institut Teknologi Telkom
ITT DividedByZero
Institut Teknologi Telkom
Petra Christian University
Sekolah Tinggi Teknik Surabaya
HantuPuskom.Jr
University of Sumatera Utara
IIUM cat-us-trophy
International Islamic University Malaysia
ITT Guntur
Institut Teknologi Telkom
Institut Teknologi Telkom
kode racun
University of Sumatera Utara
University of Sumatera Utara
ShadowEvil
Sekolah Tinggi Teknik Surabaya
Bina Nusantara University
TouchEvent
Sekolah Tinggi Teknik Surabaya
University of Sumatera Utara
Total (attempt/solved)
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.
Foreign Team Blogs
Local Team Blogs
& Felix Halim 2009 (Loaded in 0.19598 secs)}