DEV Community

Ibrahim
Ibrahim

Posted on

Plan and main algorithms

Thank, DeepSeek

Sure! Competitive programming is a separate field where it's not only important to know how to write code but also to understand key algorithms and data structures that are frequently used in competitions. Here's a list of essential algorithms and topics you need to learn to perform well in serious programming contests:


1. Basic Algorithms and Data Structures

  • Sorting:
    • Quick Sort
    • Merge Sort
    • Counting Sort
    • Radix Sort
  • Binary Search:
    • Searching in a sorted array
    • Binary search on the answer
  • Two Pointers:
    • Solving problems related to subarrays, pairs, etc.
  • Prefix Sums:
    • Fast computation of sums on subarrays.
  • Stack, Queue, Deque:
    • Implementation and applications in problems.
  • Hashing:
    • Hash tables, polynomial hashes for strings.

2. Graphs

  • Graph Representation:
    • Adjacency lists, adjacency matrix.
  • Graph Traversal:
    • Depth-First Search (DFS)
    • Breadth-First Search (BFS)
  • Connected Components:
    • Finding connected components in undirected graphs.
  • Topological Sorting:
    • For Directed Acyclic Graphs (DAG).
  • Shortest Paths:
    • Dijkstra's Algorithm
    • Bellman-Ford Algorithm
    • Floyd-Warshall Algorithm
  • Minimum Spanning Tree (MST):
    • Kruskal's Algorithm
    • Prim's Algorithm
  • Cycle Detection:
    • In directed and undirected graphs.
  • Bridges and Articulation Points:
    • Tarjan's Algorithm.

3. Dynamic Programming (DP)

  • Basics of DP:
    • Knapsack Problem
    • Longest Increasing Subsequence (LIS)
  • DP on Subarrays:
    • Problems related to substrings, subarrays.
  • DP on Trees:
    • Problems involving counting paths, subtrees.
  • DP with Bitmasks:
    • Problems involving subset enumeration.
  • DP Optimizations:
    • Divide and Conquer, Convex Hull Trick.

4. Trees

  • Binary Trees:
    • Search, insert, delete operations.
  • Segment Tree:
    • Range minimum/maximum queries, range sum queries.
  • Fenwick Tree (Binary Indexed Tree):
    • Fast updates and prefix queries.
  • Search Trees (BST, AVL, Splay):
    • Tree balancing.
  • Lowest Common Ancestor (LCA):
    • Binary Lifting Algorithm.

5. Strings

  • Prefix Function and Z-Function:
    • Substring search.
  • Knuth-Morris-Pratt Algorithm (KMP):
    • Substring search.
  • Aho-Corasick Algorithm:
    • Multiple substring search.
  • Suffix Array:
    • Construction and applications.
  • String Hashing:
    • Polynomial hashes for substring comparison.

6. Mathematics

  • Number Theory:
    • Greatest Common Divisor (GCD), Euclidean Algorithm.
    • Sieve of Eratosthenes for prime numbers.
    • Integer factorization.
  • Combinatorics:
    • Binomial coefficients, combinations.
  • Fast Exponentiation:
    • Fast modular exponentiation.
  • Chinese Remainder Theorem:
    • Solving systems of congruences.
  • Linear Algebra:
    • Matrix multiplication, fast matrix exponentiation.

7. Geometry

  • Points, Vectors, Lines:
    • Dot product, cross product.
  • Segment Intersection:
    • Algorithm for checking intersection.
  • Convex Hull:
    • Andrew's monotone chain algorithm.
  • Triangulation:
    • Decomposing polygons into triangles.

8. Advanced Topics

  • Network Flow:
    • Ford-Fulkerson Algorithm.
    • Edmonds-Karp Algorithm.
  • Matchings:
    • Hungarian Algorithm.
  • Segment Tree with Lazy Propagation:
    • Lazy updates in segment trees.
  • Persistent Data Structures:
    • Persistent Segment Tree.
  • Square Root Decomposition:
    • SQRT decomposition, Mo's Algorithm.

9. Useful Skills

  • Bit Manipulation:
    • Bitmasks, bitwise operations.
  • Greedy Algorithms:
    • Solving problems using greedy strategies.
  • Divide and Conquer:
    • Solving problems by breaking them into subproblems.
  • Two Pointers Technique:
    • Solving problems involving subarrays, pairs, etc.

10. Practice

  • Platforms for Practice:
    • Codeforces (regular contests, problems of varying difficulty).
    • AtCoder (Japanese contests, problems on DP and graphs).
    • LeetCode (algorithm and data structure problems).
    • Timus Online Judge (Russian-language problems).
    • CSES Problem Set (great collection for beginners and advanced programmers).

How to Learn:

  1. Start with basic algorithms (sorting, binary search, prefix sums).
  2. Solve problems on graphs and dynamic programming — these are the most common topics in competitions.
  3. Learn advanced data structures (segment trees, Fenwick trees, suffix arrays).
  4. Regularly participate in contests (Codeforces, AtCoder).

Example Learning Plan:

  1. Week 1-2: Basic algorithms (sorting, binary search, two pointers).
  2. Week 3-4: Graphs (DFS, BFS, shortest paths).
  3. Week 5-6: Dynamic programming (knapsack, LIS, problems on subarrays).
  4. Week 7-8: Trees (segment trees, Fenwick trees, LCA).
  5. Week 9-10: Strings (KMP, Z-function, hashing).

If you'd like, I can explain any specific algorithm or topic in more detail! 😊

Sentry image

Hands-on debugging session: instrument, monitor, and fix

Join Lazar for a hands-on session where you’ll build it, break it, debug it, and fix it. You’ll set up Sentry, track errors, use Session Replay and Tracing, and leverage some good ol’ AI to find and fix issues fast.

RSVP here →

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay