How to prepare for ACM – ICPC?

ACM ICPC(Association for Computing Machinery – International Collegiate Programming Contest) is a worldwide annual multi-tiered programming contest being organized for over thirteen years. The contest is sponsored by IBM. 

This article focuses on what all topics that are important for competitive programming and should especially be studied in order to train yourself for the upcoming ACM-ICPC contest. 

Rules of the Contest – World Final Rules for 2021 Click here 

Indian Participants – Codechef conducts all the Indian Regionals. Click here to know about team formation, reimbursements, etc 

ICPC for Schools by CodeChef – This competition serves as a gateway for school students to participate in the ACM ICPC contest along with ICPC college participants held across India. It is an idea conceived by CodeChef and supported by Amrita University. 
 

To reach the world’s final, there are two phases. First, you have to qualify for the Preliminary online Round conducted on Codedrills (since last two years). Every college’s top team is selected if they have at least one question solved during the contest, with the number of teams selected based on the number of available seats in that particular region. These teams will then go on to compete in the prestigious International Collegiate Programming Contest (ICPC) regionals, where they will represent their college and compete against other teams from around the world. The regional contest is onsite in which the teams who qualified for the preliminary round, reach the site to compete in an onsite regional contest. The teams which further qualified for the onsite regionals round will reach the world’s final ACM ICPC. 

How to apply for ACM-ICPC: 

1. Go to the ICPC website (https://icpc.global/).
2. Create your personal contestant id, log in with the same, and fill in all the necessary information.
3. As you have to create a team with a mentor/coach from your college your coach should do steps 1&2 but as a coach.
4. Now the coach has to go to the dashboard -> create a team.
5. Now you have to choose which region you want to opt for.
6. Then register all the contestants with the proper mail id which the team members registered on ICPC BAYLOR. Remember only a Team Coach can create the team.

A sample ICPC Problem: A usual ICPC problem has the following features: 
 

1. Problem statement: describing the problem and what output is to be generated.
2. Input: Make sure that you read this section with complete attention as missing out on any minor detail may land you in the wrong answer zone.
3. Output: Just like above, this one also should be read carefully.
4. Constraints: These can include constraints on input, time, memory, code size, etc.
5. Time limit: See if your algorithm can work in this range. If not, time to change it!
6. Memory limit: If you are fond of allocating memory for every small thing, it’s a good time you change it.

Preparing for ACM-ICPC

First and foremost Step: PRACTICE – Following are the resources that can be referred to for practicing the ACM-ICPC alike contests and problems. For all these Online Judges, begin with the problems with maximum submissions and check other solutions to check how you may improve. Do Participate in their monthly contests to remain up to the mark. 
 

• ACM-ICPC Past Problems – ICPC Archive, Practice at Codechef
• TopCoder – Proceed by increasing problem levels gradually
• Codeforces -List of Problem Sets
• Codechef – Beginners can start with Codechef Beginners and proceed further
• SPOJ – Move from easy to tough problems
• USACO – Excellent training resource
• uvaOnline Judge – Huge repository of problems
• Hackerrank – Practice problems topic wise and participate in preparatory series
• Hackerearth – Participate in preparatory series
• Practice – Good for beginners. Has problems ranging from difficulty level School to Hard.
• List of various Competitive Programming Contests available online all throughout the year
• Usaco Guide – Provides detailed explanations of each topic, as well as numerous practice problems.
• Atcoder – Contest A,B,C are beginner friendly and can help you in strengtheing your algorithms. 

What to study?

Knowing just the basics of programming won’t be fruitful for aspirants of ACM ICPC. One needs to have a thorough knowledge of advanced algorithms used as well. The following Topics list out the necessary Topics and Algorithms that one must surely know to improve and stand a chance in the actual competition. 

Elementary data structures: To begin with competitive programming, one must master Data Structures. Following is the list of most commonly used data structures: 
 

• Array
• Stack
• Queue
• String
• Heap
• Hash
• Extensive list of Data structures

Advanced Data Structures 
Priority queues, union-find sets, (augmented) interval trees, (augmented) balanced BSTs, and binary indexed trees 
 

• Binary Indexed Tree or Fenwick tree
• Segment Tree (RMQ, Range Sum, and Lazy Propagation)
• K-D tree (See insert, minimum and delete)
• Union Find Disjoint Set (Cycle Detection and By Rank and Path Compression)
• Tries
• Interval Tree

More Advanced Data Structures. 

Sorting and Searching: Concentrate on learning the basic concepts and also get familiar with all the library functions available. 
 

• Binary Search
• Quick Sort
• Merge Sort
• Order Statistics

String manipulation: Strings make programming problems interesting and difficult too and probably thats the reason they are used extensively in such contests. Learning library functions for String actually proves very helpful (C++: See this and this, String in Java). 
 

• KMP algorithm
• Rabin Karp
• Z’s algorithm
• Aho Corasick String Matching

Choosing the right Language: C++ is to date most preferred language followed by Java when it comes to programming contests but you should always choose a language you are comfortable with. Being CONFIDENT in any language is most important. 

Standard Template Library: A quintessential especially for those using C++ as a language for coding 
 

• Power up C++ STL by Topcoder – Part 1, Part 2
• C++ Magicians – STL Algorithms

Dynamic Programming 
 

• Longest Common Subsequence
• Longest Increasing Subsequence
• Edit Distance
• Minimum Partition
• Ways to Cover a Distance
• Longest Path In Matrix
• Subset Sum Problem
• Optimal Strategy for a Game
• 0-1 Knapsack Problem
• Assembly Line Scheduling
• Optimal Binary Search Tree

All DP Algorithms 
 

BackTracking 
 

• Rat in a Maze
• N Queen Problem
• Subset Sum
• m Coloring Problem
• Hamiltonian Cycle

More articles on Backtracking 

Greedy Algorithms 
 

• Activity Selection Problem
• Kruskal’s Minimum Spanning Tree Algorithm
• Huffman Coding
• Efficient Huffman Coding for Sorted Input
• Prim’s Minimum Spanning Tree Algorithm

More articles on Greedy Algorithms 

Graph Algorithms: One of the most important topics which you can not ignore if preparing for ACM – ICPC. 
 

• Breadth First Search (BFS)
• Depth First Search (DFS)
• Shortest Path from source to all vertices **Dijkstra**
• Shortest Path from every vertex to every other vertex **Floyd Warshall**
• Minimum Spanning tree **Prim**
• Minimum Spanning tree **Kruskal**
• Topological Sort
• Johnson’s algorithm
• Articulation Points (or Cut Vertices) in a Graph
• Bridges in a graph

All Graph Algorithms 
 

Basic Mathematics

Arithmetic: Programmers must know how integers and real numbers are represented internally and should be able to code high-precision numbers. Bit manipulation tricks and knowing library functions for number basic arithmetic would be very helpful. 

Number theory: Knowing some of these concepts would save a lot of time and effort while programming in the contests. 
 

• Modular Exponentiation
• Modular multiplicative inverse
• Primality Test | Set 2 (Fermat Method)
• Euler’s Totient Function
• Sieve of Eratosthenes
• Convex Hull
• Basic and Extended Euclidean algorithms
• Segmented Sieve
• Chinese remainder theorem
• Lucas Theorem

Combinatorics : Although directly might not seem to be important, Combinatorics is important to estimate asymptotic complexity of algorithms. 
 

• Analysis of Algorithms
• Combinatorial Game Theory | Set 1 (Introduction)

Geometrical Algorithms 
 

• Convex Hull
• Graham Scan
• Line Intersection
• Matrix Exponentiation and this
• Online construction of 3-D convex hull
• Bentley Ottmann algorithm to list all intersection points of n line segments
• Rotating Calipers Technique
• Area/Perimeter of Union of Rectangles
• Closest pair of points
• Area of Union of Circles
• Delaunay Triangulation of n points
• Voronoi Diagrams of n points using Fortune’s algorithm
• Point in a polygon problem

Network Flow Algorithms 
 

• Maxflow Ford Furkerson Algo and Edmond Karp Implementation
• Min cut
• Stable Marriage Problem
• Dinic’s Algorithm for Maximum Flow and Wiki
• Minimum Cost Flow Problem
• Successive Shortest Path Algorithm
• Cycle Cancelling algorithm
• Maximum weighted Bipartite Matching (Kuhn Munkres algorithm/Hungarian Method) 
  • Hungarian Algorithm Wiki 
     
  • Hungarian Algorithm for Assignment Problem 
     
  • Maximum Bipartite Matching 
     
• Stoer Wagner min-cut algorithm
• Maximum matching in the general graph (Blossom Shrinking)
• Gomory-Hu Trees
• Chinese Postman problem(Please see this too)
• Hopcroft–Karp Algorithm for Maximum Matching

All Articles on Geometric Algorithms 
 

More Advanced Stuff

Bit Algorithms, Randomized Algorithms, Branch and Bound, Mathematical Algorithms, Heavy Light Decomposition, A* Search 
 

Informative Articles that you may like to read

• An Awesome List for Competitive Programming – Codeforces
• What are the algorithms required to solve all C++ problems in Contests? – Quora
• Best books and sites to prepare for ACM-ICPC – Quora
• Introduction to Programming Contest – Stanford.edu
• World Final Problems of ACM-ICPC – icpc.kattis

References: 
Programming Camp Syllabus 

V

Vishwesh Shrimali

Improve