Considered as the “Olympics of Programming Competitions,” the Association for Computing Machinery – International Collegiate Programming Contest or ACM-ICPC is one of the oldest and most esteemed programming competitions in the world. Every year, more than 2,000 universities spread across eighty countries participate in this contest to win the grand prize of $12,000 and a gold medal awarded by the ACM-ICPC. Apart from this, three runner-up teams receiving the Gold medal are also rewarded with $6,000 and teams that bag the Silver and Bronze medal receive $3,000 and $1,500 respectively.
The ACM-ICPC contest has two rounds, the regional round that is organized and conducted at the local universities of various regions across the world. In India, the Asia Regionals are held at Amritapuri, Chennai, and Kolkata. The regional contest location sites are allotted a ‘slot’ which is the formal invitation to enter the ACM-ICPC World Finals.
Here’s how you should approach the ACM-ICPC preparation!
The first step in preparing for the ACM-ICPC is to start practicing and competing in Online Judges and contests similar to ICPC. OJs such as CodeChef, TopCoder, Codeforces, Hackerrank, Hackerearth, USACO are excellent online resources to practice and hone your programming skills. Begin by tracking down problems with the most number of submissions, see how people have approached it, and see if you can get to the solution through a different and better perspective.
The next step would be to make a detailed list of the things you have to study. Having a computer science background is highly preferred as you’ll have to deal with a lot of complex data structures and algorithms in the contest.
There are many programming languages to choose from including C++, Java, Ruby, Python, Perl, and so on. Pick one programming language that you think will be the best match for you and master it through and through. Once you master a programming language, you’ll find it much easier to learn other programming languages.
Mastering data structures is one of the prerequisites for participating in any competitive programming contest. Thus, you are expected to be well-versed with the fundamental data structures such as arrays, stacks, queues, strings, heap, and hash, to name a few. Once you’ve got a solid grasp on these basic data structures, it’s time to move on to more advanced data structures like Fenwick Tree, K-D Tree, Segment Tree, Interval Tree, and so on.
Sorting & Searching
After data structures, you should focus on learning sorting and searching functions like quick sort, merge sort, binary search, and order statistics. While learning the basic concepts of sorting and searching functions are fine, you must also familiarize yourself with as many library functions as possible.
Once you learn how to work with strings, you’ll find it extremely interesting. Strings are a must-learn as they are highly used in competitive programming contests. Try to learn how to manipulate string functions such as Z’s algorithm, KMP algorithm, Rabin Karp, and Aho Corasick string matching, to name a few. If you can learn library functions for strings, even better!
Just like data structures, algorithms are also very important for competitive programming. Algorithms can be classified under the following categories:
Dynamic Programming algorithms – Longest Common Subsequence, Longest Increasing Subsequence, Minimum Partition, Longest Path In Matrix, Subset Sum Problem, 0-1 Knapsack Problem, and Assembly Line Scheduling.
- Graph algorithms – Breadth First Search (BFS), Depth First Search (DFS), Dijkstra, Floyd Warshall, Prim, Kruskal, Johnson’s algorithm, Topological Sort, and Bridges in a graph.
- Greedy algorithms – Activity Selection Problem, Huffman Coding, Huffman Decoding, Egyptian Fraction, Job Sequencing Problem, Water Connection Problem, and Fitting Shelves Problem.
- Geometric algorithms – Convex Hull, Graham Scan, Line Intersection, Matrix Exponentiation, Bentley Ottmann algorithm, Rotating Calipers Technique, Closest pair of points, and Voronoi Diagrams of n points using Fortune’s algorithm.
- Network Flow algorithms – Maxflow Ford Fulkerson algorithm, Edmond Karp Implementation, Min-cut, Stable Marriage Problem, Dinic’s Algorithm, Cycle Cancelling algorithm, Stoer Wagner min-cut algorithm, and Hopcroft–Karp Algorithm.
When it comes to programming, one must have a solid foundation in Mathematics and Statistics since a lot of programming problems are rooted in these two. Thus, you must learn basic math concepts such as number theory, linear algebra, discrete mathematics and combinatorics, probability theory, game theory, graph theory, numerical analysis, and calculus. Also, be well-versed with principles like Induction, Pigeon Hole, Inclusion-Exclusion, and the like. Moving on to Statistics, make sure that you learn concepts like mean, median, variance, and so on.
Mastering the above-mentioned concepts should be enough for you to make it through the regional round of the ACM-ICPC, and once that’s done, there’s nothing to stop you from emerging as a winner in this prestigious competition. The key to success is dedication, commitment, and practice. During the learning process, try to connect with mentors and peers on the various OJ platforms. Usually, such communities are very active and can help you with helpful feedback if you are ever stuck somewhere. Be confident, and begin!
Till then, happy coding!