C++ Day 36

 

Day 36: Binary Search on Answer (BSOA)

A high-level competitive programming technique.

---

🚀 1. What is Binary Search on Answer?

You use binary search on the value of the answer when:

1️⃣ The answer lies in a range (like 1 to 1e18)
2️⃣ For any candidate mid, you can check whether it's possible, valid, or feasible
3️⃣ If mid is valid → all values < mid or > mid are also valid (monotonic property)

This works for problems like:

• minimum time

• minimum capacity

• maximum possible score

• partitioning array into k parts

• scheduling

• optimization

---

🚦 2. Template

long long lo = L, hi = R, ans = R;
while (lo <= hi) {
    long long mid = (lo + hi) / 2;

    if (check(mid)) {
        ans = mid;
        hi = mid - 1;  // try to minimize
    } else {
        lo = mid + 1;
    }
}
cout << ans << "\n";

---

🧠 3. Example 1: Allocate Minimum Pages

Given n books, allocate to k students to minimize maximum pages.

check(mid) returns true if we can divide such that no one gets more than mid pages.

---

🧠 4. Example 2: Aggressive Cows

Place cows in stalls to maximize minimum distance.

Monotonic:
If distance d is possible → any smaller distance is possible.

---

🔥 5. Example 3: Minimum Maximum Subarray Sum

Split array into k parts so that maximum part sum is minimized.

Classic check(mid) → greedily cut segments.

---

⭐ 6. Example Template Check Function

bool check(long long limit) {
    long long sum = 0;
    int parts = 1;

    for (long long x : arr) {
        if (x > limit) return false;
        if (sum + x > limit) {
            parts++;
            sum = x;
        } else {
            sum += x;
        }
    }
    return parts <= k;
}

---

⚡ 7. Tips

• The range [L, R] is usually:

  • L = max element

  • R = sum of elements

• Always check monotonicity

• Prefer long long

• Use mid = lo + (hi - lo)/2 if overflow is a concern

---

📚 8. Practice Problems

Try solving these to master BSOA:

1. Aggressive Cows (SPOJ, classic)

2. Book Allocation (GFG)

3. Split Array Largest Sum (LeetCode Hard)

4. Koko Eating Bananas

5. Factory Machines (CSES)

6. Apartments variant with maximize/minimize differences

7. Minimize Max Distance to Gas Station

---

🎯 Summary

Binary Search on Answer =
➡️ Search answer range
➡️ Check mid validity
➡️ Use monotonic property
➡️ Powerful for optimization problems

---

If you want, I can give:

✔ Notes PDF
✔ 10 practice questions
✔ A hard BSOA problem with full explanation

Just tell me!