26 August 2010

ACM-ICPC How to get started?

by Chua Hock-Chuan (ehchua@ntu.edu.sg)

To know more about ICPC, read the ICPC mother site (@ http://icpc.baylor.edu/icpc/) or Wiki “ICPC”. To summarize, ICPC is the programming contest for the university students (just like the IOI – International Olympiad in Informatics – is the programming contest for high school students). The ICPC contest rules are:

  • Each team consists of THREE students
  • Each team is given only ONE computer
  • Each team is given 5 hours to solve 8-10 problems (in C, C++, Java and possibly Pascal)
  • The team who solves the most number of questions in the shortest time is the winner
  • There are two stages for the contest: Regional’s and the Grand Final. Winners of each regional contest proceed to the Grand Final

PREPARATION…

Step 0.1 – Read, Read, Read: on programming, data structures, algorithms, and object-oriented programming.

Step 0.2 – Pick your Language: Pick a programming language that you are comfortable, either C++ or Java or both (but not C nor Pascal as they lack advanced libraries).

Step 0.3 – Gather Programming Resources: Gather programming books and materials, especially online references and resources.

Step 0.4 – Setup your Programming Workbench: If you can afford a laptop, get one (so that you can program at the Starbucks and in the train).

Depending on the host, the contest could be run on Linux (most likely) or Windows or any other exotic machines.

For Java programmers
Use JDK 1.5 and above, which greatly simplifies the IO processing. The Java IDE of choice is certainly eclipse – an open-source IDE supported by IBM (the official sponsor of the contest), and it runs on both Linux and Windows. For newcomers, read “How to install Eclipse“, “writing your first Java program in Eclipse“, and “debugging Java program in Eclipse“.

For C/C++ programmers
It is harder to decide because you have a few options:

Important for All Programmers

  • You should be familiar with the use of graphical debugger to improve your programming efficiency and productivity.
  • You should be familiar with the libraries, such as Java’s API and C++ STL.
  • [TODO] more

Step 0.5 – Online Judges and Training Sites: There are many “online practice sites” called online judge, that archive hundreds (or even thousands) of past contest problems. You could try the problems at your own time and own target, and submit your solutions online. You program will be automatically compiled and run with a carefully-designed set of test inputs. The status of the run, such as “accepted”, “wrong answer”,”compile error”, “presentation error”, “time limit exceeded”, “memory limited exceed”, “output limit exceed” will then be shown to you. In the case of compilation error, some of the sites may also show you the compilation error messages.

These are the sites that I frequently used (google or wiki “icpc”, “online judge” to get the full list).

  • Peking University Online Judge (PKU): This site support many languages, including Java (JDK 1.5), GNU’s GCC/G++ (for C/C++) and Visual C/C++ version 6.
  • Universidad de Valladolid Online Judge (UVA): This is the most reputable site, with a good forum (equipped with search). The support for C++ is excellent, however, the support for Java is mediocre (no JDK 1.5).
  • USA Computing Olympiad (USACO) Training Program: This is the training site for IOI (International Olympiad in Informatics for high school students) instead of ICPC. However, it provides a very systematic training on the algorithms frequently encountered in contests, e.g., shortest path, greedy, dynamic programming, heuristic search, minimum spanning tree, and etc. It supports C, C++ and JDK 1.5.

LET’S GET REAL & STARTED…

Step 1 – Try PKU Online Judge

  1. Register with PKU online judge @ http://acm.pku.edu.cn/JudgeOnline/.
  2. Read the FAQ to understand to submission rules – IMPORTANT!
  3. Read the FAQ AGAIN.
  4. The programming rules for ICPC are:Java Language
    • Input comes form System.in and output goes to System.out (no File IO allowed).
    • The source file must contain a class called Main with the entry-method main:
      public static void main(String[] args) { ... }.

    C++ Language

    • Input comes form std:cin and output goes to std:cout (no File IO allowed).
    • The source file must contain the entry-function int main() { ... }.
  5. Try the first problem “1000 (A+B)” with the solution provided in FAQ. The purpose of this problem is to let you understand the above programming rules. In your submission, make sure you specify the language used (“Java”, “G++” for GNU C++ compiler, or “C++” for VC6 compiler).For Java programmers
    You should program at JDK 1.5 or above. Use Scanner, in.nextInt(), in.nextDouble(), in.next() for inputting int, double, and String, and C-like System.out.printf("formatString", args...) for output.
    JDK 1.5 Program Template for ICPC Online Judge

    import java.util.Scanner;
    
    public class Main {   // save as Main.java
       public static void main(String[] args) {
          Scanner in = new Scanner(System.in);
    
          int    i = in.nextInt();    // read int
          double d = in.nextDouble(); // read double
          String s = in.next();       // read String
          // There is no nextChar(), use next() and charAt()
          char c = s.charAt(2);
          // Read whole line (or rest of the line past '\n')
          String line = in.nextLine();
    
          System.out.printf("%4d, %6.2f, %s, %c\n", i, d, s, c);
          // Use %f for double (not %lf)
          // Don't forget to print the '\n'
       }
    }
  6. Try another few (extremely) simple problems (you can look at the percentages to estimate the difficulty of the problems)
    • Read the programming rules AGAIN before trying these problems.
    • You input and output must strictly follow the description given. You need not and CANNOT print input prompting message such as “Please enter a number” (because nobody is sitting at the online judging system to read these prompts).
    • Do “1004 (Financial Management)” – Simply averaging 12 numbers
      Hints: To test this program, you have two options: (a) key in the 12 numbers slowly, or (b) save the 12 numbers in a file, says “in.txt“, start a Command shell (“cmd“), and use the “pipe” operator “<” to re-direct the input from the file “in.txt” to the stdin as follows:
      For Java Programmers
      Assume that the source file is called Main.java

      > javac Main.java
      > java Main < in.txt

      For C++ programmers
      Assume that the source file is called test.cpp

      > g++ -o test.exe test.cpp
      > test < in.txt
    • “1003 (Hangover)” – Compute the sum of a harmonic series and compare…
    • “1005 (I think I need a house boat)” – Compute the area of a semi-circle and compare…

Step 2 – Try UVA Online Judge: This site is meant for C/C++ programmers. Java programmers can forget about this site (as there is no support for JDK 1.5). For C programs, you cannot use // comments.

  1. Register with UVA online judge @ http://online-judge.uva.es/problemset/.
  2. Read the HOWTOs, especially on how to submit solution.
  3. Try the first problem Volume 1 Problem 100 (3n+1) with the solution provided in HOWTOs.

The above steps are meant for you to familiarize with the contest process. Here come the “serious” training…

Step 3 – Try USACO Training Problem

  1. Register with USACO Training Program @ http://train.usaco.org/usacogate/.
  2. Read “Section 1.0 Text Introduction” and “Section 1.1 Submitting Solutions”.
    As mentioned, this site is meant for IOI instead of ICPC, the submission requirements are different from the online judges.
    You are required to read from an input file named “xxxx.in” and write to an output file named “xxxx.out” where “xxxx” is the name of the problem.
    Try the “First Challenge” (or “testproblem). If you encounter problem in File IO under VC++ or Eclipse, read “VC++ File Input/Output” or “Eclipse File Input/Output“, respectively.
    For Java programmers
    The sampled Java solution given is based on JDK 1.2, which is rather clumsy in IO processing. I provide the sample solution in JDK 1.5 is as follows:JDK 1.5 Program Template for USACO

    /*
    ID: yourID
    LANG: JAVA
    TASK: test
    */
    
    import java.util.Scanner;
    import java.util.Formatter;
    import java.io.File;
    import java.io.IOException;
    
    public class test {  // saved as test.java
       public static void main (String [] args) throws IOException {
          Scanner in = new Scanner(new File("test.in"));        // file input
          Formatter out = new Formatter(new File("test.out"));  // file output
    
          int a = in.nextInt();
          int b = in.nextInt();
          out.format("%d\n",a+b);  // format() has the same syntax as printf()
    
          out.close();    // flush the output and close the output file
          System.exit(0); // likely needed in USACO
       }
    }
  3. Continue and try to complete the training problem. As mentioned, this site provides systematic training for the frequently used algorithms encountered in contests (IOI as well as ICPC).

TRAINING GUIDE

My ex-student-training-manager Mr. Nguyen Trung Nghia suggests the following approach for ICPC training.

You need to pick up basic knowledge in data structures (e.g., vector, linked list, queue, stack).

You need to know many algorithms (USACO teaches some of the basics which you MUST know).

  • All kind of sorting algorithms
  • How to handle bit-operations (See “tips, tricks and tweak“)
  • Complexity of well-known algorithms
  • Graph (BFS, DFS,…)
  • Maths (Number Theory)
  • Geometry (Convex Hull, Interval tree,…)
  • Greedy algorithm
  • Dynamic algorithm
  • others

For the Beginners:

  • Do “ad-hoc” problems and simple problems which related to Maths (e.g., gcd, fibonaci, prime numbers,…). Focus on how to produce prime number with the fastest speed (See “tips, tricks and tweaks“), manipulate strings, operations on big numbers (not allow to use bignumber library).
  • Simulation problems (describe some rules and give the input, you have to follow these rules to produce output). This helps you to learn how to read the questions properly and code without bugs.
  • Try not to give them any sample code, let them code it by themselves :-)
  • Do not use C++ STL (or Java API library) at this stage.

For the Intermediates and Advanced:

  • C++ STL (or Java API libraries) should be taught
  • Graphs (bfs, dfs, flood fill algorithm, shortest path (diskja, floyd), tree, network flow)
  • Dynamic algorithm, dictionary algorithm
  • Geometry (need to know at least convex-hull, detect a point is inside a polygon, calculate the area of a polygon, etc.)
  • Graphs, dynamic, ad-hoc, simulation, maths, geometry + dynamics, graphs + geometry, maths + dynamic, and so on

If you are a C++ guy, you MUST know C++ STL:

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <list>
#include <stack>
#include <map>
#include <set>

If you are a Java guy, learn Java API, especially Collection classes and BigNumber.

C++ Program Template for UVA

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <list>
#include <stack>
#include <map>
#include <set>
using namespace std;

#define DEBUG
#define REP(i,a) for(i=0;i<a;i++)
#define FOR(i,a,b) for(i=a;i<b;i++)
#define VE vector<int>
#define SZ size()
#define PB push_back

int main()
#ifndef ONLINE_JUDEGE
   freopen("/input.txt","r",stdin);
#endif

#ifdef DEBUG
   // to write some values for debugging purposes, e.g.,
   int i =5;
   printf("%d",i);
#endif
   return 0;
}

Java References & Resources

  • JDK API Documentation

C++ References & Resources

You may have missed:

2 Responses to “ACM-ICPC How to get started?”

  1. alankelon 26 August 2010 at 4:27 am #

    Excelent tutorial!

    Three minor fixes:

    1. Current Universidad de Valladolid Online Judge (UVA) link is http://online-judge.uva.es/problemset/
    2. The correct registration link of UVA Online Judge is http://uva.onlinejudge.org/index.php?option=com_comprofiler&task=registers
    3. The List of supported compilers of UVA is:
    * ANSI C 4.1.2 – GNU C Compiler with options: -lm -lcrypt -O2 -pipe -ansi -DONLINE_JUDGE
    * JAVA 1.6.0 – Java Sun JDK
    * C++ 4.1.2 – GNU C++ Compiler with options: -lm -lcrypt -O2 -pipe -DONLINE_JUDGE
    * PASCAL 2.0.4 – Free Pascal Compiler

    Regarda

    • alankelon 26 August 2010 at 4:29 am #

      *Regards.

      Please edit this :-)