Lecture Notes: Reaching 1600 Rating on Codeforces

Introduction

• Speaker: Prian Agarwal
  • Candidate Master on Codeforces
  • Six-star coder on CodeChef
  • India rank one and Global rank six in Google Kickstart Round A 2022
• Purpose: Guide to reach 1600 rating on Codeforces
  • 91% of viewers are below 1600 rating
  • Focus on useful and unnecessary topics

Prerequisites for Reaching 1600

• Familiarity with a programming language (C++, Java, Python)
• Familiarity with C++ STL or equivalent Java/Python libraries
• Solve 100-120 problems on online judges
  • e.g., CodeChef, Codeforces, AtCoder
• Understand online judge basics: time/space complexity, leaderboards, point systems

Essential Topics to Master

1. Number Theory

• Key Subtopics:
  • Modular arithmetic
  • Primes, multiples, divisors
  • Bitwise operations (AND, OR, XOR)
  • Euclidean algorithm (calculate GCD/HCF)
  • Sieve of Eratosthenes (finding primes)
  • Binary modular exponentiation
  • Combinatorics
• Resources:
  • Code and Code (YouTube channel)
  • CT Algorithms (website)

2. Binary Search and Ternary Search

• Binary Search:
  • General binary search
  • Monotonic functions
  • Binary searching on answer
  • C++ STL functions: lower_bound, upper_bound
• Ternary Search:
  • Convex functions
  • Basics of ternary search
• Resources:
  • Codeforces EDU section
  • CP Algorithms (website)

3. Greedy Algorithms

• Key Points:
  • Solve standard greedy problems
  • Prove solutions
  • Exchange arguments (optional)
• Resources:
  • Geeks for Geeks
  • CSS Problem Set

4. Dynamic Programming (DP)

• Key Points:
  • Understand recursion and backtracking
  • Memorization techniques
  • Solve standard DP problems
  • DP with bit masking and on trees (basic)
• Resources:
  • Errichto's DP videos
  • AtCoder DP contest
  • Karthik Arora's DP playlist

5. Trees

• Key Points:
  • Basic properties, DFS
  • Binary lifting and LCA
  • Practice problems
• Resources:
  • Prian's YouTube videos
  • Codeforces tutorials

6. Graphs

• Key Points:
  • Basic properties: cycle, path, DFS, BFS
  • Connected components, directed graphs
  • Minimum Spanning Trees
• Resources:
  • William Fiset's graph playlist
  • CSS Problem Set

Topics to Avoid

• Advanced Number Theory: Euler’s theorem, Matrix exponentiation
• Range Query Data Structures: Segment trees, Fenwick trees
• Advanced String Algorithms: KMP, Z-algorithm
• Advanced Tree Algorithms: Heavy-light decomposition
• Others: Mo's algorithm, DP optimizations
• Focus on mastering basics first

Conclusion

• Avoid less critical topics until comfortable with essentials
• Subscribe and follow on social media for more content

This guide is meant to focus efforts on key topics necessary for advancing in competitive programming while avoiding deep dives into less relevant areas for sub-1600 ratings.