Road-Map for Competition

To excel in your upcoming ICPC-style C++ coding competition, it's essential to master a
range of algorithms, data structures, and problem-solving strategies. Below is a
comprehensive guide to the key concepts and techniques you should focus on:

1. Algorithms and Data Structures

Graph Algorithms
 Breadth-First Search (BFS) and Depth-First Search (DFS): Fundamental for
traversing graphs.
 Shortest Path Algorithms:
o Dijkstra's Algorithm: For graphs with non-negative weights.
o Bellman-Ford Algorithm: Handles graphs with negative weights.
o Floyd-Warshall Algorithm: Computes shortest paths between all pairs of
vertices.
 Minimum Spanning Tree (MST):
o Kruskal's Algorithm
o Prim's Algorithm
 Advanced Topics:
o Strongly Connected Components (SCC)
o Topological Sorting
o Network Flow Algorithms: Ford-Fulkerson, Edmonds-Karp, Dinic's
Algorithm.
Dynamic Programming (DP)
 Classic Problems:
o Knapsack Problem
o Longest Increasing Subsequence (LIS)
o Longest Common Subsequence (LCS)
o Matrix Chain Multiplication
 Techniques:
o Memoization and Tabulation
o State Optimization
o Bitmask DP

Data Structures
 Fundamental Structures:
o Arrays and Linked Lists
o Stacks and Queues
o Heaps/Priority Queues
o Hash Tables (Maps/Sets)
 Advanced Structures:
 o Segment Trees and Fenwick Trees (Binary Indexed Trees)
o Disjoint Set Union (Union-Find)
o Tries (Prefix Trees)
o Suffix Arrays and Suffix Trees
Number Theory and Mathematics
 Prime Number Algorithms:
o Sieve of Eratosthenes
o Prime Factorization

Greatest Common Divisor (GCD) and Least Common Multiple (LCM)

 Modular Arithmetic:
o Modular Exponentiation
o Modular Inverses
o Chinese Remainder Theorem
 Combinatorics:
o Permutations and Combinations
o Binomial Coefficients

String Algorithms
 Pattern Matching:
o Knuth-Morris-Pratt (KMP) Algorithm
o Rabin-Karp Algorithm
 Advanced Topics:
o Z-Algorithm
o Aho-Corasick Algorithm
o Suffix Arrays and Trees

Computational Geometry
 Convex Hull Algorithms: Graham Scan, Andrew's Algorithm.
 Line Intersection and Distance Calculations
 Polygon Area Computation
 Point in Polygon Tests

2. Problem-Solving Strategies
 a. Team Collaboration
 Role Assignment: Leverage individual strengths by assigning specific problem types
or algorithmic areas to each team member.
 Effective Communication: Regularly discuss problem-solving approaches and share
insights to enhance collaboration.
 Time Management: Allocate specific time slots for each problem to mimic contest
pressure.
 b. Practice and Simulation
  Regular Practice: Solve problems from previous ICPC contests to familiarize
yourself with the format and difficulty.
 Mock Contests: Simulate real contest conditions to improve time management and
teamwork.
 Upsolving: After contests, revisit unsolved problems to understand and learn from
mistakes.
 c. Efficient Coding Practices
 Template Usage: Develop and use code templates for common algorithms and data
structures to save time during contests.
 Code Optimization: Write clean and efficient code to avoid time limit exceed (TLE)
errors.
 Debugging Skills: Enhance your ability to quickly identify and fix errors in your
code.

3. Additional Resources
 Standard Libraries: Familiarize yourself with C++ Standard Template Library
(STL) for efficient implementations.
 Educational Platforms: Utilize platforms like GeeksforGeeks, Codeforces, and
TopCoder for tutorials and practice problems.
 Reference Materials: Books like "Competitive Programming 3" by Steven Halim
and Felix Halim provide in-depth coverage of algorithms and problem-solving
techniques.

By focusing on these areas and maintaining consistent practice, you'll be well-prepared to

excel in your upcoming competition. Remember, success in competitive programming comes
from a blend of theoretical knowledge, practical application, and effective teamwork.
Preparing for a coding competition requires a strong grasp of algorithms, data structures, and
problem-solving skills. Below are some C/C++ coding competition questions categorized by
difficulty and topic. These questions are designed to help you practice for competitive
programming contests like ACM ICPC, Codeforces, Google Code Jam, or LeetCode contests.

Beginner Level
Sum of Two Numbers
Write a program to take two integers as input and print their sum.

Factorial of a Number
Write a program to calculate the factorial of a given number using recursion.
Check Prime Number
Write a program to check if a given number is prime.

Reverse a String
Write a program to reverse a string without using built-in functions.

Find Maximum in an Array

Write a program to find the maximum element in an array.

Intermediate Level
Binary Search
Implement the binary search algorithm to find an element in a sorted array.

Merge Two Sorted Arrays

Write a program to merge two sorted arrays into a single sorted array.

Longest Common Prefix

Given an array of strings, find the longest common prefix among them.

Kth Largest Element in an Array

Write a program to find the kth largest element in an unsorted array.

Detect Cycle in a Linked List

Implement Floyd’s Cycle Detection Algorithm to detect a cycle in a linked list.

Advanced Level
Dijkstra’s Shortest Path Algorithm
Implement Dijkstra’s algorithm to find the shortest path in a weighted graph.
Knapsack Problem
Solve the 0/1 Knapsack problem using dynamic programming.

N-Queens Problem
Solve the N-Queens problem using backtracking.

Segment Tree
Implement a segment tree to handle range queries and updates efficiently.

Suffix Array
Construct a suffix array for a given string and use it to solve a problem like finding the
longest repeated substring.

Algorithmic Challenges
Sliding Window Maximum
Given an array and a window size, find the maximum in each sliding window.

Longest Increasing Subsequence (LIS)

Find the length of the longest increasing subsequence in an array.

Minimum Spanning Tree (MST)

Implement Kruskal’s or Prim’s algorithm to find the MST of a graph.

Topological Sorting
Perform topological sorting on a directed acyclic graph (DAG).

Floyd-Warshall Algorithm
Implement the Floyd-Warshall algorithm to find the shortest paths between all pairs of
vertices in a weighted graph.

Data Structure Problems

Implement a Trie
Write a program to implement a Trie (prefix tree) and use it to solve a problem like word
search.

LRU Cache
Design and implement an LRU (Least Recently Used) cache.

AVL Tree
Implement an AVL tree with insertion, deletion, and search operations.

Fenwick Tree (Binary Indexed Tree)

Implement a Fenwick tree to handle prefix sum queries and updates efficiently.

Disjoint Set Union (DSU)

Implement DSU with path compression and union by rank.

Mathematical Problems
GCD and LCM
Write a program to find the greatest common divisor (GCD) and least common multiple
(LCM) of two numbers.

Modular Exponentiation
Implement fast modular exponentiation to compute (a^b) % mod efficiently.

Sieve of Eratosthenes
Use the Sieve of Eratosthenes to find all prime numbers up to a given limit.

Catalan Numbers
Write a program to compute the nth Catalan number using dynamic programming.

Matrix Exponentiation
Implement matrix exponentiation to solve problems like finding the nth Fibonacci number in
O(log n) time.

String Manipulation
Rabin-Karp Algorithm
Implement the Rabin-Karp algorithm for pattern searching in a string.

Manacher’s Algorithm
Use Manacher’s algorithm to find the longest palindromic substring in a string.

Z-Algorithm
Implement the Z-algorithm for pattern matching.

Count Palindromic Substrings

Write a program to count the number of palindromic substrings in a given string.

Minimum Window Substring

Given two strings, find the smallest substring in the first string that contains all characters of
the second string.

Graph Problems
BFS and DFS
Implement Breadth-First Search (BFS) and Depth-First Search (DFS) for a graph.

Strongly Connected Components (SCC)

Use Kosaraju’s algorithm or Tarjan’s algorithm to find SCCs in a directed graph.

Articulation Points and Bridges

Find articulation points and bridges in an undirected graph.

Eulerian Path and Circuit

Determine if a graph has an Eulerian path or circuit and find it if it exists.

Bipartite Graph Check

Write a program to check if a graph is bipartite.

Dynamic Programming
Coin Change Problem
Solve the coin change problem to find the minimum number of coins required to make a
given amount.

Edit Distance
Compute the minimum number of operations (insert, delete, replace) required to convert one
string into another.

Longest Common Subsequence (LCS)

Find the length of the longest common subsequence between two strings.

Maximum Subarray Sum

Solve the maximum subarray sum problem using Kadane’s algorithm.

Rod Cutting Problem

Solve the rod cutting problem to maximize profit using dynamic programming.

Tips for Coding Competitions

Practice Regularly
Solve problems on platforms like Codeforces, LeetCode, HackerRank, and CodeChef.

Learn Standard Algorithms

Master algorithms like sorting, searching, graph traversal, and dynamic programming.
Optimize Code
Focus on time and space complexity to ensure your solution runs within constraints.

Participate in Contests
Join online coding competitions to gain experience and improve your speed.

Debugging Skills
Learn to debug code quickly and efficiently during competitions.