Chapter 1: Introduction to Competitive Programming
Concepts
What is Competitive Programming?
Competitive programming (CP) is a mental sport that involves solving well-defined algorithmic problems under time and resource constraints. Participants write computer programs to find solutions to given problems. The focus is on efficiency, correctness, and speed of implementation. It is not about building software applications but about devising optimal algorithms to solve mathematical or logical puzzles.
Key aspects:
- Problems are usually computational (e.g., finding the shortest path, counting subsets, or sorting under constraints).
- Solutions must pass predefined test cases within strict time limits (often 1-2 seconds) and memory limits (e.g., 256 MB).
- It combines mathematics, logic, and coding skills.
Contests and Formats
Competitive programming contests are the primary arena for practice and competition. They vary in duration, difficulty, and structure. Common formats include:
- Individual Contests: One participant solves problems alone (e.g., most online judges).
- Team Contests: Teams of 2-3 members collaborate (e.g., ICPC regionals).
- Duration: Typically 2-5 hours for individual contests; up to 5 hours for team events.
- Problem Types:
- Ad-hoc: Problems that require direct implementation of logic without complex algorithms or data structures. Examples include parsing a specific string format or simulating a straightforward process like a board game with fixed rules.
- Greedy: Problems where the optimal solution can be constructed step-by-step by making the locally optimal choice at each step, such as scheduling activities to maximize count or classic coin change variants where greedy works.
- Dynamic Programming (DP): Problems that can be broken down into overlapping subproblems, solved once, and stored for reuse, like the knapsack problem or finding the longest common subsequence.
- Graph Algorithms: Problems modeled as graphs requiring traversals or pathfinding, such as using BFS for shortest unweighted paths or Dijkstra for weighted paths.
- Math/Number Theory: Problems involving prime factorization, modular arithmetic, or combinatorics.
- Scoring: Problems are assigned points (e.g., 500-3000 based on difficulty). Solve time affects ranking; faster solves or fewer wrong submissions improve position.
Popular contests:
- ICPC (International Collegiate Programming Contest): Team-based, university-level, global finals.
- Codeforces Rounds: Rated individual contests with Div. 1 (advanced) and Div. 2 (beginner) levels.
- Google Code Jam / Meta Hacker Cup: Online qualifiers leading to rounds; individual focus.
- AtCoder Contests: Japanese platform with Regular (ABC/ARC) and Heuristic (AGC/AHC) contests.
Judging Systems
Judging systems automate solution evaluation. Submit your code, and the system runs it against hidden test cases. This process follows a clear workflow: you read the problem, write code to handle the input and produce the correct output, submit, and the judge verifies your solution against all tests. If it passes, you get Accepted (AC); otherwise, you receive feedback like Wrong Answer (WA) or Time Limit Exceeded (TLE) to guide improvements.
How it works:
- Input/Output (I/O): Problems specify input format (e.g., number of test cases followed by values) and expected output. Your program reads from stdin and writes to stdout.
- Execution: The judge compiles/interprets your code (supports C++, Python, Java, etc.) and runs it on test inputs.
- Evaluation:
- Correctness: Output must match expected exactly (whitespace matters).
- Time Limit: E.g., 1 second per test case; if exceeded, "Time Limit Exceeded" (TLE).
- Memory Limit: E.g., 256 MB total; exceed → "Memory Limit Exceeded" (MLE).
- Runtime Errors: Crashes or invalid operations → "Runtime Error" (RE).
- Wrong Answer: Mismatched output → "Wrong Answer" (WA).
- Accepted (AC): Passes all tests.
- Pretests vs. System Tests: Pretests are sample cases; system tests are hidden and comprehensive.
- Tools: Integrated Development Environments (IDEs) are discouraged; use simple text editors. Online judges provide problem statements, sample I/O, and constraints.
Common platforms:
- Codeforces: Real-time rating system, editorial discussions.
- AtCoder: Beginner-friendly, English problems.
- LeetCode: Interview-focused, but CP-style problems.
- HackerRank / SPOJ: Mixed difficulty, educational.
Beginner Tips for the Landscape
- Start with easy problems on platforms like AtCoder ABC or Codeforces Div. 2 A/B.
- Learn one language deeply (C++ recommended for speed; Python for simplicity).
- Understand constraints: If N <= 10^5, avoid O(N^2) algorithms; aim for O(N log N) or better. For example, with N=100,000, an O(N^2) loop would be 10 billion operations, likely TLE, while O(N log N) is about 1.6 million, feasible.
- Read problem statements carefully—misinterpretation causes WA. Pay attention to input format, constraints, and edge cases.
- Participate in virtual contests to simulate real pressure.
Examples
Example 1: Simple Contest Format (AtCoder Beginner Contest)
Imagine an AtCoder ABC (duration: 100 minutes, 6 problems A-F).
- Problem A: "Hello World" variant—print "Hello, World!" (ad-hoc, 100 points).
- Input: No input (just output).
- Output:
Hello, World! - Submission (Python):
print("Hello, World!") - Judging: Immediate AC if correct.
- Progression: Solve A in 1 minute → B (simple sum) → C (loop-based calculation).
- Outcome: Ranking based on solve time and submissions. Wrong submissions add penalties.
Example 2: Judging System in Action (Codeforces Submission)
Problem: Given two integers A and B, print their sum (A + B).
- Constraints: 1 ≤ A, B ≤ 10^9.
- Input:
3 5(single line). - Expected Output:
8. - Sample Code (Python):
a, b = map(int, input().split()) print(a + b) - Submission Process:
- Paste code into Codeforces submission form.
- Select language (Python 3).
- Submit → System compiles.
- Tests: Sample passes → System tests (hidden: large numbers, edge cases like A=1, B=10^9).
- Result: AC if all pass; WA if output is
8(extra space).
- Real Contest Scenario: In Codeforces Round #123, this might be Problem A. You submit 3 times due to WA (forgot newline), get +50 penalty, finally AC at 5 minutes.
Example 3: Multiple Test Cases Judging
Problem: For T test cases, read N and print N! (factorial), but modulo 10^9+7 for large N.
- Input:
2 3 5 - Expected Output:
6 120 - Sample Code (Python):
MOD = 10**9 + 7 t = int(input()) for _ in range(t): n = int(input()) fact = 1 for i in range(1, n + 1): fact = (fact * i) % MOD print(fact) - Judging: T=2; first test N=3 → 6 (pass), second N=5 → 120 (pass). If time limit is 1s and N=10^5 in hidden test, TLE occurs due to O(N) per test (better: precompute factorials).
Key Notes
- Essential Skills: Basic programming knowledge (loops, conditionals), familiarity with I/O in your language, understanding of time complexity (Big O notation—review if needed; it describes how runtime scales with input size, e.g., O(1) constant, O(N) linear).
- Common Pitfalls for Beginners: Ignoring constraints → TLE; not handling large numbers → overflow (use long long in C++ or Python's arbitrary precision); ignoring multiple test cases → incomplete AC. Example: Using int for 10^9 * 10^9 leads to overflow; use 64-bit types. Another: Forgetting to clear global arrays between test cases causes WA.
- Resources to Start:
- Platforms: AtCoder (ABC for beginners), Codeforces (Div. 2 A/B), CSES Problem Set (curated problemset for practice).
- Books: "Competitive Programming" by Halim (free online), "Guide to CP" by Errichto (online).
- Editorials: Always read after solving/ failing.
- Next Steps: Set up an account on Codeforces and AtCoder. Solve 1-2 easy problems daily. Track progress with a spreadsheet (date, problem, attempts, result).
- Mental Model: Treat every problem like a puzzle—understand I/O first, then constraints, then devise plan, implement, test with samples, submit. This model integrates into the judging workflow: reading I/O defines the problem, constraints guide complexity, planning avoids pitfalls.