# The Ultimate Guide for the ICPC

## The Ultimate Guide for the ICPC

Resources to prepare yourself for the The International Collegiate Programming Contest (ICPC) or any competitive programming contest

### The Ultimate Guide for the ICPC

#### Resources to prepare yourself for the *The International Collegiate Programming Contest (ICPC) or any competitive programming contest*

Photo by Ariel Besagar on Unsplash

### What is the ICPC?

“The ICPC, the ‘International Collegiate Programming Contest,’ is an extra-curricular, competitive programming sport for students at universities around the world. ICPC competitions provide gifted students opportunities to interact, demonstrate, and improve their teamwork, programming, and problem-solving process. The ICPC is a global platform for academia, industry, and community to shine the spotlight on and raise the aspirations of the next generation of computing professionals as they pursue excellence.” — Wikipedia

#### Disclaimer

I’m by no mean a top coder or a world finalist. I just wanted to share the resources I found helpful, and if you follow them, hopefully, you will be an ICPC world finalist.

### Introduction

I really like competitive programming, and I really want to be someone like Gennady Korotkevich. He is truly a living legend in the field of competitive programming.

Anyways, let’s get into the details …

### The Steps to be a Good Competitive Programmer

It’s really simple: There are no tricks and there’s no short way … all you need is dedication and a goal, and you are all set.

First, you will need to be familiar with at least one of the following programming languages: Python, Java, C, or C++.

Secondly, you will need to study all of the different topics about data structures and algorithms.

Finally, do a lot of problems … *a lot!*

### Topics

These are the main topics that should be done thoroughly.

#### Number theory

- Euclidian and extended Euclidian algorithm
- Modular arithmetic and modular inverse
- Prime generation (sieve and segmented sieve)
- Fermat’s theorem
- Euler’s Totient function
- Miller Rabin primality test
- Chinese remainder theorem
- Lucas theorem

#### Greedy algorithms

#### Binary search

- Topcoder binary search
- Binary search
- Ubiquitous binary search — get a grasp of discrete and continuous binary searches

#### Data structures

- Linked lists
- Binary-search tree
- Binary-indexed tree or Fenwick tree
- Segment Tree (RMQ, range sum,andlazy propagation)
- Red-Black trees
- Hashing
- Extensive list of data structures

**Graph algorithms**

- 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

**String algorithms**

Learning library functions for string actually proves very helpful. (C++: See this, this, String in Java.)

- KMP algorithm
- Rabin karp
- Z’s algorithm
- Aho-Corasick string matching
- Suffix arrays
- Trie
- Finite automata

**Dynamic programming**

Dynamic programming is quite important and can be infused and asked with various other topics. Some different types of DP concepts are:

**Classic DP**

- 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
- All DP algorithms

**Computational geometry**

### Resources

“Competitive Programming 3” This book is beyond great. I’m currently in the middle of it and I’m enjoying the problems and the book structure. I highly recommended it.

“The ‘Science’ of Training in Competitive Programming” In this blog,the author explains how to train for CP and what he did in order to be a good problem solver.

How to be a red coder This Quora answer really goes deep into how to be a red coder and train efficiently.

Tags: algorithm, data-structure, c++, advice, competitive-programming, blogging | Edit on GitHub