Guide to ICPC Preparation

Competitive Programming
1

ICPC

ICPC stands for International Collegiate Programming Contest. It is open for only college students. Its a team contest. Each team should have 3 members from the same college.

The competition is divided in multiple rounds –

Preliminary Round
This is a qualifier round to make it to a Regional. Each Regional generally has a qualifier to shortlist the teams which will compete at Regional Onsite Round.
Regional Round
Shortlisted teams from the qualifier compete with each other at regional rounds. Each regional has few World Finals slots based on their capacity.
World Finals
Top few teams from each regional qualify for World Finals! This is the ultimate battle between best of the bests!

ICPC 2021

There is no confirmation on World Finals. But some of the regionals are organizing their regional rounds. In this blog we will include all the information for Amritapuri Regional.

Registration

ICPC registration happen on ICPC global site. To find upcoming regionals, visit upcoming regionals page on the site. Select your region. For example participants belonging to Asia West continent, select The 2020 ICPC Asia West Contests. The dropdown will expand with all regional contests listed. Select one belonging to your region. For example, Indian participants can see Asia Amritapuri First Round Online Programming Contest. There is details button in front of it, click on it and you will land to its page. On the contest page, there should be register button, from there you can register your team for that particular regional contest.

All team members first need to create an account on ICPC Global site. After that team should be registered by the coach not the students. If you do not have a coach, ask one of the professors from your college to sign up on ICPC Global site and then register your team. Once the coach registers your team, you should enter all required details in your profile to be eligible. If there is something missing, it will be shown on your team or profile page.

World’s largest regional Amritapuri will organize its qualifier round on May 16 and regional round on May 30. Both contests will be held on our platform CodeDrills.
Registration for qualifier round has started on March 1 on Baylor System and ends on April 30 . There is no Registration fee to participating in the Preliminary Online Round for Amritapuri Regional.

Preparation

When you are planning to compete in such a prestigious contest, its very essential to prepare for it to increase your chances to reach World Finals or even Regionals.
You can follow these steps –

Learn a language well
First step is to find the best choice for the programming language. Most of the community use - C++, Java or Python. C++ is the fastest in most of the situations. Some of the problems are not solvable in other languages with given constraints. Also there is no language specific multiplier in ICPC contests. Hence its advised to use C++.
Once you have made your choice for the language, learn the syntax and its inbuilt libraries and their use. For example C++ has STL(standard template library) with a lot of useful algorithms and data structures. You should learn them to code quick because that also matters. When two teams have same score, total time taken is considered to determine ranks.

Learn well known topics
Next step is to learn all useful topics which are widely used. Most of the topics are available on CP Algorithms. This is one of the best site to refer the DS/Algo implementations and understand them, specifically for competitive programming.

Data Structures

  • Basic data structures
    • Array
    • Vector
    • String
  • Linked Lists
  • Stacks
  • Queues
  • Priority Queues
  • Trees
    • Binary Trees
    • Binary Search Trees
    • AVL Trees
  • Heaps
  • Hashmaps, Hashtables
  • Sets
  • Trie
  • Segment Tree
  • Fenwick Tree or Binary Indexed Tree(BIT)
  • RMQ
  • Sqrt Decomposition
  • Disjoint Data Structures

Algorithms

  • Sorting
    • Merge Sort
    • Quick Sort
    • Counting Sort
  • Searching
    • Linear Search
    • Binary Search
    • Ternary Search
  • Bit Manipulation
  • Number Theory
    • Prime Numbers (Sieve of Eratosthenes)
    • GCD and LCM Euclid’s Algorithm
    • Modular Exponentiation
    • Long arithmetic (Multi, Add)
    • Efficient Prime Factorization
    • Fermat’s Theorem
    • Euler’s Totient Function
    • Chinese Remainder Theorem
    • Lucas Theorem
  • Combinatorics
    • Permutations & Combinations
    • Probability
    • Expected Value
  • Dynamic programming
    • Knapsack
    • Matrix chain multiplication
    • Coin Change
    • Kadane
    • Longest increasing Subsequence (with RMQ)
    • DP with bitmasking
  • Strings
    • Z algorithm
    • Suffix Trees/Arrays
    • Knuth-Morris-Pratt Algorithm (KMP)
    • Rabin-Karp Algorithm
    • Hash
    • Aho Corasick Algorithm
    • Finite Automata
  • Graph Theory
    • Depth First Search (DFS)
    • Breadth First Search (BFS)
    • Topological Sorting
    • Dijkstra’s Shortest Path
    • Minimum Spanning Tree
    • Ford Bellman
    • Floyd Warshall
    • Articulation Points
    • Bridges
    • Union Find
    • LCA (Lowest Common Ancestor)
    • HLD (Heavy Light Decomposition)
    • Graph Coloring
    • Max Flow / Min Cut
  • Game theory
    • Nim game
    • Grundy numbers
    • Sprague-Grundy theorem
  • Computational geometry
    • Primitive Operations
      • Intuition
      • Polygon Inside, Outside
      • Implementing CCW
      • Immutable Point ADT
    • Convex Hull
    • Closest pair problem
    • Line intersection
  • Others
    • Mo’s Algorithm
    • Graph Matching

Practice problems from each topic to build the confidence. I found one useful CF blog having topicwise listed problems. Blog Link.

Practice regularly
Keep participating in contests regularly. Keep solving problems regularly to keep yourself in touch with problem solving.
ICPC problem archive is available here.

Give mock team contests
Try CodeDrills Contests with your team. You can also try previous years qualifier/regional rounds. We will also have more practice rounds in coming weeks! Don’t miss them! You can also win the prizes along with the preparation by participating in practice rounds!
Some of CodeDrills team contests are listed here -

Final Preparation
When you are done with all the preparations, prepare your code template having all well known topics implementations. You can refer it during online round. Also a hand book of maximize of 20-25 pages is allowed for onsite contests also. So this would be useful for you!

5 Likes