From Tools to Techniques

You are here: Ch 0 (Fundamentals) → Ch 1 (Essential Techniques) | Core Path

---

The Gap

You've spent weeks on C++, complexity, recursion, bit manipulation. You can read code, analyze its speed, and write clean implementations—and yet you still can't solve a single Codeforces problem.

That's not a knowledge gap. You have all the ingredients. What you're missing are the recipes: the patterns that translate raw language fluency into actual problem-solving power. The difference between an ingredient and a recipe is knowing when to use what, and in what order.

Here's what that gap looks like in practice.

---

Three Problems You Can't Solve Yet

Two Sum in a Sorted Array

Given a sorted array of $n$ integers, find two elements that sum to a target value.

With Chapter 0 tools, you'd write:

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        if (a[i] + a[j] == target) return {i, j};

$O(n^2)$. For $n={10}^5$, that's ${10}^{10}$ operations. Time limit exceeded.

You know the array is sorted. You know that if a[i] + a[j] is too large, you need a smaller a[j]. But Chapter 0 never taught you to put one pointer at the start and another at the end, walking them inward. That's the two-pointer technique, and it solves this in $O(n)$.

Two lines of insight. A factor of ${10}^5$ speedup.

100,000 Range Sum Queries

Given an array of $n$ integers, answer $Q$ queries: "What is the sum from index $l$ to index $r$?"

With Chapter 0, the honest approach:

for (each query l, r)
    sum = 0;
    for (int i = l; i <= r; i++) sum += a[i];

Each query is $O(n)$. With $Q={10}^5$ queries on an array of size ${10}^5$, that's ${10}^{10}$ again. TLE again.

The right instinct is "can I precompute something?"—but Chapter 0 didn't teach you what to precompute. The answer is a prefix sum array: p[i] = a[0] + a[1] + ... + a[i-1], so any range sum reduces to p[r+1] - p[l]. One pass to build, $O(1)$ per query.

The idea is embarrassingly simple once you see it. But you have to see it first.

Minimum Speed to Finish on Time

You have $n$ tasks with known workloads. Given a speed $s$, task $i$ takes $\lceil \text{workload}[i]/s\rceil$ hours. Find the minimum integer speed so all tasks finish within $T$ hours.

With Chapter 0, you might try every speed from 1 upward:

for (int s = 1; s <= max_workload; s++)
    if (totalTime(s) <= T) return s;

$O(\text{max\_workload}\cdot n)$. If workloads reach ${10}^7$, this is far too slow.

But notice: if speed $s$ works, speed $s+1$ also works. The answer space is monotonic. That means you can binary search on the answer—checking $O(\log (\text{max\_workload}))$ speeds instead of every one. From ${10}^7$ iterations down to 23.

Binary search isn't just "find an element in a sorted array." It's a paradigm: whenever the answer space has a monotonic property, you can binary search on it. Chapter 0 taught you the mechanics. Chapter 1 teaches you to see it everywhere.

---

What's Actually Happening

Each problem above is genuinely solvable—the code isn't complicated. But in every case, the brute-force approach you'd naturally reach for with Chapter 0 skills is too slow by orders of magnitude. The fast solution requires recognizing a pattern and applying a technique.

That's the entirety of Chapter 1. Not new data structures, not new theory—just eight clean techniques (two pointers, sliding window, prefix sums, binary search, greedy, complete search, divide and conquer, and a few more) that close the gap between "I understand the problem" and "I have the solution." Master them, and the problems rated 1000–1500 on Codeforces start to feel like vocabulary exercises.

---

Before You Move On

Can you confidently:

• [ ] Write C++ solutions with proper I/O, types, and STL usage?
• [ ] Analyze time and space complexity of a brute-force approach?
• [ ] Implement recursion and identify base cases without getting lost?
• [ ] Use bit manipulation for masking, toggling, and counting?
• [ ] Debug a wrong answer using stress testing against a brute force?

If any feel shaky, revisit Chapter 0 first.

---

Key Files

Chapter 0 (just completed):

• Arrays and Strings—the data you'll be processing
• STL Containers—the containers techniques build on
• Recursion and Backtracking—foundation for divide and conquer
• Debugging and Stress Testing—you'll need this more, not less

Chapter 1 (starting now):

• How to Solve Problems—start here
• Binary Search—from "find in sorted array" to paradigm
• Two Pointers—the technique from Problem 1 above
• Prefix Sums—the technique from Problem 2 above

Practice: Ladder: 1100-1400

---

Next: Chapter 1—Essential Techniques