Frédéric de Mesmay's ACM-ICPC Ressources Page

The ACM - ICPC is a worldwide programming challenge for undergraduates. The contest is composed of a Problem Set containing 6 to 10 algorithmic problems. It is to be solved within 5 hours by teams of three guys and only one computer per team. I participated two times with two different teams to the South West European Regional Contest and we ranked French runner up in 2005. The level was so high that, though we beat last year winners, we only scored 12th in the european final rankings (out of 55).

There is only one method to become better : train yourself on the Universidad de Valladolid Online Judge (here is my ID).

But, if you are blocked, here are some useful ressources I wrote to help:

Basis:

Graphs:

Groups:

Number Theory:

Computational Geometry:

Big Integers:

Useful Links:

Basis : How to read input

Formatted input is the beginning of almost all problems : You must read the standard input to get the data. There are two cases : on one hand the data representation is dependant of the end of lines, on the other it is not. To know if this is dependant or not, try mentally squeezing all the newlines. If the input has lost some sense then it is dependant. eg: A list of numbers is clearly independant, a list of cities name is dependant because there can be cities with a blank in it and then you can't decide what's a city and what's not ("Paris New York London"), a list of of lists with the number of elements precised for each list is independant, ...

If it's independant, it's easier and the good solution is the scanf() function. For multiple entry problems, it can often be used like this: 

while((scanf("%d",&n)==1)&&(n!=0)) {;}

If it is dependant, remember 4 things:

My solution for multiple entry problem is doing something like this: 

for(gets(string);!feof(stdin);gets(string)) {
 if (string[strlen(string)-1]=='\r')
  string[strlen(string)-1]=0;
 ;
}

By the way, beware of multiple input problems, signaled by a blue or green comma!

Basis : How to sort

An efficient sort is required in a large number of problems, so be sure to know at least one! The standard C library "stdlib.h" proposes the Quicksort O(n * ln(n)) in average. This is how to use it (of course, you can change the int type by any type you like...): 


int compare(const void*a,const void*b){
 const int * i=(const int *)a;
 const int * j=(const int *)b;
 if (*i<*j)
  return -1;
 else if (*i>*j)
  return 1;
 else
  return 0;
}

qsort(array pointer,number of elements,size of elements, compare);

Basis : How to allocate dynamic memory

Sometimes, static array aren't useful since they waste too much memory or they are too small. You can use dynamic memory to bypass your problems, but remember that allocating memory is always a pain, so do it scarcely. Especially, don't forget to free the memory after usage or you will run quickly over the memory limit. void *calloc(size_t nitems, size_t size) will nullify the space and void *malloc(size_t size) won't. 

pointer=(int*)malloc(n*sizeof(int));
free(pointer);

Graphs : Depth First Search

Nearly all graphs problems require an adapted Depth First Search algorithm. It is useful since it will walk through all vertices of any graph but never two times one the same vertex. It works recursively this way: 

int dfs(int vertex){
 mark this vertex.
 dfs all sons of this vertex.
}

int main(){
 wipe all the marks on all vertices.
 for all non marked vertices, call dfs.
}
It has some interesting properties, like each time you call dfs on a vertex, it will call dfs on all vertices of the same connected component. Doing something on a vertex after having called all sons of this vertex is called doing something in the DFS post order. It is useful to ensure we begin to process all leaves, then the small nodes and then the bigger ones.

Graphs : Breadth First Search

While DFS is doing a depth-walktrough, BFS will do a breadth-walktrough. Do achieve this, don't program a LIFO stack but a FIFO queue. (Actually, my implentation of the DFS use the machine stack so BFS looks quite different but remember that it is essentially the same) 

      head=0;
      queue=0;
      wipe all marks;
      for(FIFO[queue++]=root;head!=queue;head++){
        if FIFO[head] is not marked
           mark FIFO[head];
        for all not marked i sons of FIFO[head]{
           mark sons[FIFO[head]][i];
           FIFO[queue++]=sons[FIFO[head]][i];
        }
	printf("%d",FIFO[head]);
      }
The interesting property of DFS is that is gives the Shortest Path between the root and any node in an unweighted graph.

Graphs : Dijkstra Shortest Path

In a weighted graph, computing the shortest path cannot be done with the Breadth First Search algorithm. Dijkstra algorithm will compute the shortest path from a vertex to all vertices of a connected component by incrementally adding vertices. First, add the given vertex and mark all root neighbours as reachable. Then add the closest reachable vertex and mark all his neighbours as reachable and so on... Usually I use this code: 

int* graph_shortestpath(int results[GRAPH_MAXVERTEX],graph* graphe,int root){
  int i,j,realmin,locrealmin,min;
  for(i=0;i<graphe->nvertex;i++)
    results[i]=-1;
  results[root]=-2;
  while (1){
    locrealmin=-1;
    realmin=GRAPH_MAXINT;
    for(i=0;i<graphe->nvertex;i++)
      if (results[i]==-2){
	min=GRAPH_MAXINT;
	if (graphe->matrix[i][root]!=-1)
	  min=graphe->matrix[i][root];
	for (j=0;j<graphe->nvertex;j++)
	  if ((graphe->matrix[i][j]!=-1)&&(results[j]>=0)&&(results[j]+graphe->matrix[i][j]<min))
	    min=results[j]+graphe->matrix[i][j];
	if (min<realmin){
	  realmin=min;
	  locrealmin=i;
	}
      }
    if (locrealmin==-1)
    break; 
    results[locrealmin]=realmin;
    for(i=0;i<graphe->nvertex;i++)
      if ((results[i]==-1)&&(graphe->matrix[i][locrealmin]!=-1))
	results[i]=-2;
  }
  results[root]=0;
  return results;
}
Note that it does not work if there are negative weights since the shortest way will be a negative infinity and that it returns -1 for unconnected vertices.

Graphs : Strongly Connected Components

When dealing with an asymetrical graph, the question is sometimes : starting from this point, is there any points that can be reached that allow me to return to the start? To solve this question, compute the post order of the reversed graph (the graph with all his connection reversed). Then dfs the original graph in the reversed order of the post order calculated and simply output the standard components. 

void graph_connected_dfs(int results[GRAPH_MAXVERTEX],graph* graphe,int vertex,int ncomponents,int* graph_fog){
  int i;
  graph_fog[vertex]=1;
  results[vertex]=ncomponents;
  for(i=0;i<graphe->nvertex;i++)
    if ((graphe->matrix[vertex][i]>0)&&(graph_fog[i]==0))
      graph_connected_dfs(results,graphe,i,ncomponents,graph_fog);
}

int graph_connected(int results[GRAPH_MAXVERTEX],graph* graphe){
  graph temp;
  int i,post[GRAPH_MAXVERTEX],ncomponents, graph_fog[GRAPH_MAXVERTEX];
  graph_post(post,graph_transpose(&temp,graphe));
  memset(graph_fog,0,graphe->nvertex*sizeof(int));
  memset(results,0,graphe->nvertex*sizeof(int));
  ncomponents=0;
  for(i=graphe->nvertex-1;i>=0;i--)
    if (graph_fog[post[i]]==0)
      graph_connected_dfs(results,graphe,post[i],ncomponents++,graph_fog);
  return ncomponents;
}

Groups : Generate all sets

Sometimes, when order doesn't matter, you don't want to generate all permutations, but just all sets. This can be only done with small sets since the number of sets is 2 ** n. The good way to do it is to compute it bitwise like this: 

  n=3;
  for(i=0; i < (int)pow(2,n) ;i++){
    for(j=0; j < n ;j++)
      if (i&(1 << j))
	printf("%d ",j+1);
    printf("\n");
  }

Number Theory : How to get the prime factors

There is no subtility in this job : Just do as you do for safe primality check (Steave of Erathostenes) and remember the values of the factors! Beware of 0 and 1! 

int integer_factor(int *prime,int *mult,int n){
  int i,p;
  memset(prime,0,INTEGER_MAXFACTORS*sizeof(int));
  memset(mult,0,INTEGER_MAXFACTORS*sizeof(int));
  p=0;
  while ((n%2==0)&&(n!=0)) {
    mult[0]++;
    prime[0]=2;
    p=1;
    n>>=1;
  }
  for(i=3;i<=sqrt(n)+1;i+=2)
    while (n%i==0) {
      if (prime[p-1]!=i)
	prime[p++]=i;
      mult[p-1]++;
      n=n/i;
    }
  if (n>1){
    prime[p++]=n;
    mult[p-1]++;
  }
  return p;
}

Number Theory : How to create a GCD function

The best idea is to use the Euclide algorithm with integer divisions. It can be implemented this way: 

int integer_gcd(int a,int b) {
 int r;
 while (b!=0){
  r=a%b;a=b;b=r;
 }
 return a;
}

Geometry basics : equality, colinearity, triangle ...

The big problem with computational geometry is that is is computationnal, that is, it uses floating points operations... And as everybody know, FPU is not always precise (especially Intel FPU!), so, eg, never try to egalize two points, but rather look if their distance is less than a very small number. 

typedef struct {
  double X;
  double Y;
} point;

int point_equal(point a, point b){ 
  return ((fabs(a.X-b.X) < GEOM_EPSILON)&&(fabs(a.Y-b.Y) < GEOM_EPSILON));
}
Another really important function is knowing if three points are aligned and you can do this this way: 

int point_colinear(point p1,point p2,point p3){
  return (fabs((p1.X-p2.X)*(p1.Y-p3.Y)-(p1.Y-p2.Y)*(p1.X-p3.X)) < GEOM_EPSILON);
}
Last but not least, it is often useful to know if three points are clockwise or counterclockwise, but beware of colinear points! 

double triangle_signedarea(point a, point b, point c){
  return(a.X*b.Y - a.Y*b.X + b.X*c.Y - b.Y*c.X + c.X*a.Y - c.Y*a.X)/2.0;
}

int triangle_iscounterclockwise(point a, point b, point c){
  return (triangle_signedarea(a,b,c) > -GEOM_EPSILON);
}

Computational Geometry : How to compute the convex hull

Convex hull is a little bit like sorting : it is necessary to know how to compute a correct convex hull, but that knowledge is often not sufficient enough to complete a problem. The code I use is a slightly different version of the one given in the Programming Challenges book from S. Skienna (by the way, you should buy it cause it is a good book), so I won't give the implementation to you, but rather the way to achieve it.

1. Skim all the duplicates, they are dangerous and not useful.

2. Get the leftlowest point. It is clearly in the hull.

3. Sort the other points by growing angles around the leftlowest point.

4. Add points one by one to the hull. If the triangle formed by the last three hull point is turning in a wrong direction, remove the middle point that is clearly not in the hull. Be specially aware of colinear points. You can use a cyclic definition or a sentinel to take care of the last point.

Computational Geometry : How to test if a point lies within a convex hull

To know if the point is inside the hull, you'd better know if the hull is clockwise or counter-clockwise. Then, just test if it's on the left or on the right of all border lines. Be sure to know if you wanna an inside function that include or exclude border points. 

  for(i=0;i<=input->npoints-1;i++)
    if ((!point_colinear(A,input->points[i],input->points[(i+1)%input->npoints]))&&(!triangle_iscounterclockwise(A,input->points[i],input->points[(i+1)%input->npoints])))
      return FALSE;
  return TRUE;

Computational Geometry : How to calculate the area of a polygon

There is a tricky and useful formula you better remember to get the area of a polygon.: 


  float area=0;
  for (k=0;k < npoints;k++)
    area+=points[k].X*points[(k+1)%npoints].Y-points[k].Y*points[(k+1)%npoints].X;
  return fabs(area/2.0);

Big Integers : Basis

Sometimes, integers will not fit into 32 bits, so you will need to program it. How to handle additions, substractions, multiplications and divisions for really big integers? The answer is simple, do it like you always did on the paper. The code I use is a slightly different version of the one given in the Programming Challenges book from S. Skienna (by the way, you should buy it cause it is a good book), so I won't give the implementation to you.

return to my home