Skip to content

Problems — Level 7: Binary Search on Answer

এই folder-এ Level 7-এর 12টা problem-এর note থাকবে। প্রতিটার জন্য আলাদা .md file — নিজের ভাষায় problem বোঝা, F/T সিঁড়ির ছবি, lo/hi-এর dry run, code আর ভুল থেকে শেখা।

কীভাবে problem গুলো use করবে?

প্রতিটা problem-এর note লেখা হয় ../../../templates/math-problem-note-template.md follow করে — ২০টা section-এর template: problem বোঝা → brute force → optimization → dry run → complexity → "ভবিষ্যতের আমাকে এক লাইনে কী বলব"। শুরুতে template-টা একবার পড়ে নাও।

নিয়মটা এই level-এ একটু বিশেষ:

  1. Table থেকে problem নাও (recommended order ../README.md-তে)
  2. BSoA problem-এ code-এর আগে তিনটা প্রশ্নের উত্তর লেখো: answer space কী? check(guess) কী? monotonic কেন? — তিনটার একটাও না পারলে আগে ../concept-notes.md-এ ফেরো
  3. Dry run-এ lo | hi | mid | check-এর টেবিল হাতে বানাও — binary search-এর bug শুধু এখানেই ধরা পড়ে
  4. Solve হলে Status planned → done

Tracker table

# Problem Difficulty Pattern Inherits from Source Note file Status
091 Basic Binary Search Easy halving — LeetCode Binary Search — https://leetcode.com/problems/binary-search/ 091-basic-binary-search.md planned
092 Lower Bound Easy first ≥ x 091 Classic (Python bisect_left) 092-lower-bound.md planned
093 Upper Bound Easy first > x 092 Classic (Python bisect_right) 093-upper-bound.md planned
094 Search Insert Position Easy lower bound apply 092 LeetCode — https://leetcode.com/problems/search-insert-position/ 094-search-insert-position.md planned
095 Square Root using Binary Search Easy first BSoA 091 LeetCode Sqrt(x) — https://leetcode.com/problems/sqrtx/ 095-square-root-binary-search.md planned
096 Minimum Eating Speed Medium BSoA minimize 095 LeetCode Koko Eating Bananas — https://leetcode.com/problems/koko-eating-bananas/ 096-minimum-eating-speed.md planned
097 Ship Packages Within D Days Medium BSoA minimize 096 LeetCode — https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/ 097-ship-packages-d-days.md planned
098 Aggressive Cows Medium BSoA maximize 096 SPOJ AGGRCOW — https://www.spoj.com/problems/AGGRCOW/ 098-aggressive-cows.md planned
099 Allocate Minimum Pages Medium minimize max load 097 Classic interview problem (book allocation) 099-allocate-minimum-pages.md planned
100 Split Array Largest Sum Hard minimize max load 099 LeetCode — https://leetcode.com/problems/split-array-largest-sum/ 100-split-array-largest-sum.md planned
101 Median of Two Sorted Arrays Hard partition search 092 LeetCode — https://leetcode.com/problems/median-of-two-sorted-arrays/ 101-median-two-sorted-arrays.md planned
102 Kth Smallest in Multiplication Table Hard BSoA + counting 096 LeetCode — https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/ (related: CSES Factory Machines — https://cses.fi/problemset/task/1620) 102-kth-smallest-multiplication-table.md planned

"Inherits from" column-টা কী?

প্রতিটা problem আগের কারো কাঁধে দাঁড়িয়ে। 091 হলো ভিত; 092/093 সেটার বাঁক; 095-এ array উধাও হয়ে BSoA-র জন্ম; 096 থেকে minimize/maximize-এর পুরো পরিবার। আটকে গেলে "Inherits from" problem-টা আবার দেখো — template-টা সেখানেই পরিষ্কার হয়েছিল।

091 (basic) ──> 092 (lower bound) ──> 093 (upper bound)
   │               ├──> 094 (insert position)
   │               └──> 101 (median partition)
   └──> 095 (sqrt, প্রথম BSoA)
            └──> 096 (Koko, minimize) ──> 097 (ships) ──> 099 (pages) ──> 100 (split)
                    ├──> 098 (cows, maximize)
                    └──> 102 (counting check)

একটা ছোট পরামর্শ

এই level-এর প্রতিটা problem-এ নিজের কাছে তিনটা জবাবদিহি: answer space, check, monotonicity। আর code লেখার সময় প্রতিটা lo = ... / hi = ...-এর পাশে এক শব্দের মন্তব্য রাখো — "কেন এটা নিরাপদ"। Binary search-এ মুখস্থ template বিপজ্জনক — কারণ minimize আর maximize-এ move গুলো উল্টে যায়, আর ঝোঁকানো mid ভুল হলে infinite loop নিঃশব্দে অপেক্ষা করে। সিঁড়ির ছবি (../visualization-ideas.md) আগে, code পরে — এই অভ্যাসটাই এই level-এর আসল উপহার।

Concept ঝালাই করতে → ../concept-notes.md। ছবি এঁকে বুঝতে → ../visualization-ideas.md।