উত্তরের ওপর binary search — সিদ্ধান্তের প্রশ্নে রূপান্তর

১ · উত্তর খোঁজা কঠিন, উত্তর যাচাই সহজ — মূল ধারণা

পর্ব ১৮-এ আপনি দেখেছেন, সাজানো অ্যারেতে একটি মান খুঁজতে binary search প্রতিবার বাকি অংশের অর্ধেক বাদ দেয়। এই পর্বে সেই একই কৌশল আমরা একটি অ্যারের ওপর নয়, চালাব সম্ভাব্য উত্তরগুলোর ওপর। কৌশলটির নাম binary search on the answer — উত্তরের ওপর binary search. কনটেস্ট আর ইন্টারভিউতে এটি সবচেয়ে বেশি ব্যবহৃত কৌশলগুলোর একটি, আর একবার চিনে ফেললে অনেক “কঠিন” দেখানো সমস্যা কয়েক লাইনে নেমে আসে।

একটি গল্প দিয়ে শুরু করি। বোর্ড পরীক্ষার পর করিম স্যারের কাছে চারটি স্কুলের খাতার বান্ডিল এসেছে: ৩, ৬, ৭ আর ১১টি খাতা। ফল প্রকাশের আগে তাঁর হাতে আছে মোট ৮ ঘণ্টা। তাঁর কাজের নিয়ম একটু অদ্ভুত: প্রতি ঘণ্টায় তিনি একটি বান্ডিল বেছে নেন আর সেটি থেকে সর্বোচ্চ k টি খাতা দেখেন। বান্ডিলে k-এর কম খাতা থাকলে সেগুলো শেষ করে ঘণ্টার বাকি সময় চা খান — অন্য বান্ডিলে হাত দেন না। প্রশ্ন: ৮ ঘণ্টায় সব শেষ করতে k-এর সর্বনিম্ন মান কত? (কম গতিতে দেখলে খাতা মনোযোগ দিয়ে দেখা হয়, তাই তিনি যত কম গতি সম্ভব, তত কম রাখতে চান।) কনটেস্টের জগতে এটি “Koko eating bananas” নামে পরিচিত — সেখানে একটি বানর কলার কাঁদি খায়।

সরাসরি “সবচেয়ে ছোট k কত” বের করার কোনো সূত্র চোখে পড়ে না। কিন্তু উল্টো প্রশ্নটি খুব সহজ: “k = 5 দিলে কি ৮ ঘণ্টায় হবে?” প্রতিটি বান্ডিলে ⌈খাতা / k⌉ ঘণ্টা লাগে (ceiling, অর্থাৎ ওপরের দিকে পূর্ণসংখ্যা), সব যোগ করে ৮-এর সাথে তুলনা করলেই উত্তর। k = 5-এ ⌈3/5⌉ + ⌈6/5⌉ + ⌈7/5⌉ + ⌈11/5⌉ = 1 + 2 + 2 + 3 = 8 ঘণ্টা — হবে। এই ধরনের হ্যাঁ/না প্রশ্নকে বলে decision problem (সিদ্ধান্তের প্রশ্ন), আর মূল “সবচেয়ে ছোট কত” প্রশ্নটি একটি optimization problem. সব k-এর জন্য হিসাবটি করে দেখুন:

নিচের সারিটি লক্ষ করুন: F F F T T T T T T T T. প্রথমে কিছু “না”, তারপর একবার “হ্যাঁ” শুরু হলে বাকি সব “হ্যাঁ” — মাঝে কোনো ওলট-পালট নেই। এর কারণ সহজ: গতি বাড়ালে কোনো বান্ডিলে বেশি সময় লাগতে পারে না, তাই k দিয়ে হলে k + 1 দিয়েও হবে। এমন হ্যাঁ/না ফাংশনকে বলে monotone predicate (একমুখী শর্ত)। আর আমাদের উত্তর ঠিক সেই জায়গা, যেখানে F থেকে T শুরু — প্রথম T, এখানে k = 4.

২ · সাধারণ template — প্রথম true খোঁজা আর তার invariant

পর্ব ১৮-এর binary search-এ আপনি একটি নির্দিষ্ট মান খুঁজেছেন। এখানে আমরা খুঁজি একটি সীমানা — যেখানে predicate F থেকে T হয়। এর জন্য একটিমাত্র template মুখস্থ রাখুন, আর প্রতিটি সমস্যায় শুধু তিনটি জিনিস বদলান: lo, hi আর check(x).

Pseudocode: smallest x in [lo, hi] with check(x) = true
Precondition: check is monotone (F...F T...T) and check(hi) = true

FIRST-TRUE(lo, hi, check):
    while lo < hi:                    // at least two candidates left
        mid = lo + (hi - lo) / 2      // lower middle, never equals hi
        if check(mid):
            hi = mid                  // mid works: answer is mid or to its left
        else:
            lo = mid + 1              // mid fails: answer is strictly right
    return lo                         // lo == hi == first true

নিচে খাতার সমস্যায় এই template চলতে দেখুন। ওপরের সারিতে “known” মানে এই মুহূর্তে অ্যালগরিদম কী জানে: বড় হাতের T/F মানে সরাসরি যাচাই করা হয়েছে, ছোট হাতের t/f মানে যাচাই না করেও একমুখিতার জোরে জানা গেছে, আর ? মানে এখনো অজানা।

1lo = 1, hi = 11            // 11 = largest bundle2while (lo < hi) {3    mid = lo + (hi - lo) / 2;4    if (hours(mid) <= 8) hi = mid;5    else lo = mid + 1;6}7return lo;

শুদ্ধতার প্রমাণ। ধরুন ans হলো প্রকৃত প্রথম T. লুপের loop invariant: “lo ≤ ans ≤ hi” — অর্থাৎ lo-এর বাঁয়ের সব x-এ check F, আর hi-তে check T. শুরুতে এটি সত্য, কারণ শর্ত অনুযায়ী check(hi) = T আর lo হলো সবচেয়ে ছোট সম্ভাব্য মান। একটি ঘূর্ণনে: check(mid) = T হলে একমুখিতার কারণে ans ≤ mid, তাই hi = mid দিলেও ans ∈ [lo, hi]. check(mid) = F হলে mid আর তার বাঁয়ের সব F, তাই ans ≥ mid + 1 — lo = mid + 1 দিলেও invariant টেকে। থামা: lo < hi হলে mid = lo + ⌊(hi − lo)/2⌋ সবসময় lo ≤ mid < hi, তাই দুই শাখাতেই পরিসর (hi − lo) অন্তত ১ কমে, আর আসলে প্রায় অর্ধেক হয়। লুপ শেষে lo = hi, আর invariant বলে ans সেখানেই। মোট ঘূর্ণন ⌈log₂(hi − lo + 1)⌉-এর মতো।

শেষ true — উল্টো একমুখিতা আর অসীম লুপের ফাঁদ

কিছু সমস্যায় predicate উল্টো দিকে একমুখী: T T T T F F F, আর আমরা চাই শেষ T — যেমন “সবচেয়ে বড় কত দূরত্ব রাখা যায়” (অংশ ৪)। তখন template-এর আয়না ছবি লাগে, আর একটি ছোট কিন্তু মারাত্মক পরিবর্তন:

Pseudocode: largest x in [lo, hi] with check(x) = true
Precondition: check is T...T F...F and check(lo) = true

LAST-TRUE(lo, hi, check):
    while lo < hi:
        mid = lo + (hi - lo + 1) / 2  // UPPER middle, never equals lo
        if check(mid):
            lo = mid                  // mid works: answer is mid or to its right
        else:
            hi = mid - 1              // mid fails: answer is strictly left
    return lo

এবার নিজে খেলে দেখুন। নিচের প্রোগ্রামটি প্রতিটি k-এর ঘণ্টা আর T/F সারি ছাপে, তারপর binary search-এর প্রতিটি ধাপ। প্রথম লাইনের বান্ডিল আর ঘণ্টা বদলে Run চাপুন — যেমন H = 5 বা piles = [30, 11, 23, 4, 20], H = 6:

// Change these and press Run: bundles of exam scripts, and the hour limit
const piles = [3, 6, 7, 11], H = 8;

const hoursAt = (k) => piles.reduce((s, p) => s + Math.ceil(p / k), 0);
const maxPile = Math.max(...piles);
let rowK = "k     ", rowH = "hours ", rowP = "ok?   ";
for (let k = 1; k <= maxPile; k++) {
  rowK += String(k).padStart(4);
  rowH += String(hoursAt(k)).padStart(4);
  rowP += (hoursAt(k) <= H ? "T" : "F").padStart(4);
}
console.log(rowK + "\n" + rowH + "\n" + rowP);

let lo = 1, hi = maxPile;            // speed maxPile always works if H >= piles.length
while (lo < hi) {
  const mid = lo + Math.floor((hi - lo) / 2);
  const ok = hoursAt(mid) <= H;
  console.log(`lo=${lo} hi=${hi} mid=${mid} hours=${hoursAt(mid)} -> ${ok ? "T" : "F"}`);
  if (ok) hi = mid; else lo = mid + 1;
}
console.log(`minimum speed = ${lo} scripts per hour`);

k        1   2   3   4   5   6   7   8   9  10  11
hours   27  15  10   8   8   6   5   5   5   5   4
ok?      F   F   F   T   T   T   T   T   T   T   T
lo=1 hi=11 mid=6 hours=6 -> T
lo=1 hi=6 mid=3 hours=10 -> F
lo=4 hi=6 mid=5 hours=8 -> T
lo=4 hi=5 mid=4 hours=8 -> T
minimum speed = 4 scripts per hour

৩ · সর্বোচ্চকে সর্বনিম্ন করা — split array, বই ভাগ আর জাহাজের মাল

এবার একটি ক্লাসিক সমস্যা, যা তিনটি ভিন্ন নামে আসে। বই ভাগ (book allocation): লাইব্রেরির তাকে পরপর সাজানো n টি বই, প্রতিটির পৃষ্ঠাসংখ্যা জানা; k জন ছাত্রের মধ্যে ভাগ করতে হবে, প্রত্যেকে পাশাপাশি থাকা এক টুকরো বই পাবে। সবচেয়ে বেশি যে পড়বে, তার পৃষ্ঠা যত কম সম্ভব রাখুন। রং করা (painter’s partition): পাশাপাশি দেয়াল, k জন রংমিস্ত্রি, প্রত্যেকে টানা কয়েকটি দেয়াল — সবচেয়ে ধীরে শেষ করা মিস্ত্রির সময় কমান। Split array largest sum: অ্যারে a-কে k টি অবিচ্ছিন্ন টুকরোয় ভাঙুন, যাতে টুকরোগুলোর সবচেয়ে বড় যোগফলটি সর্বনিম্ন হয়। তিনটিই একই অঙ্ক।

এই ধরনকে বলে “minimise the maximum” — সবচেয়ে খারাপ টুকরোটিকে যত ভালো সম্ভব করা। সরাসরি সব ভাগ পরীক্ষা করলে C(n − 1, k − 1) টি উপায়, যা দ্রুত অসম্ভব হয়ে যায়। কিন্তু সিদ্ধান্তের প্রশ্নটি দেখুন: “প্রতিটি টুকরোর যোগফল ≤ X রেখে কি k বা তার কম টুকরোয় ভাঙা যায়?” এর উত্তর দেয় একটি সরল greedy: বাঁ থেকে যোগ করতে থাকুন; পরের সংখ্যাটি যোগ করলে X ছাড়িয়ে গেলে সেখানে টুকরো কাটুন, নতুন টুকরো শুরু করুন। শেষে টুকরোর সংখ্যা ≤ k কি না দেখুন।

X বাড়ালে টুকরো কম লাগে (বা সমান), তাই predicate “টুকরো ≤ k” একমুখী: F…F T…T. আর সীমা: কোনো টুকরো একটি সংখ্যার চেয়ে ছোট হতে পারে না, তাই lo = max(a); পুরো অ্যারে এক টুকরো হলে যোগফল sum(a), যা সবসময় সম্ভব — hi = sum(a). a = [7, 2, 5, 10, 8], k = 2-এ পুরো খোঁজা দেখুন:

greedy যাচাই কেন সঠিক? দাবি: সীমা X-এর জন্য greedy সবচেয়ে কম সংখ্যক টুকরো দেয়। প্রমাণটি একটি “এগিয়ে থাকা” (greedy stays ahead) যুক্তি, যা exchange argument-এর আত্মীয়। যেকোনো বৈধ ভাগ OPT নিন। দাবি: greedy-র প্রথম j টি টুকরো OPT-এর প্রথম j টি টুকরোর সমান বা বেশি দূর পর্যন্ত যায়। j = 1-এ সত্য, কারণ greedy প্রথম টুকরোকে যতটা সম্ভব লম্বা করে। j থেকে j + 1-এ: greedy-র j-তম টুকরো OPT-এর চেয়ে আগে শেষ নয়, তাই greedy-র (j + 1)-তম টুকরো শুরু হয় OPT-এর চেয়ে আগে নয়; OPT-এর (j + 1)-তম টুকরোর শেষবিন্দু পর্যন্ত বাকি অংশ OPT-এর টুকরোর একটি অংশ, তাই যোগফল ≤ X — greedy অন্তত ততদূর যাবে। অতএব OPT m টুকরোয় শেষ করলে greedy-ও m বা কম টুকরোয় শেষ করে। আর “k বা কম টুকরো” পেলে “ঠিক k টুকরো” বানানো যায়, যদি n ≥ k — যেকোনো টুকরো আরও ভাঙলে বড় যোগফল বাড়ে না।

কোডে — প্রতিটি ঘূর্ণনে যাচাইয়ের ফল ছাপা হয়, তারপর k = 1 থেকে 5 পর্যন্ত উত্তর:

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int piecesNeeded(const vector<long long>& a, long long cap) {   // greedy
    int pieces = 1; long long cur = 0;
    for (long long x : a) {
        if (cur + x > cap) { ++pieces; cur = 0; }    // x does not fit: new piece
        cur += x;
    }
    return pieces;
}
long long splitArray(const vector<long long>& a, int k, bool trace) {
    long long lo = *max_element(a.begin(), a.end());       // answer in [lo, hi]
    long long hi = accumulate(a.begin(), a.end(), 0LL);
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        int p = piecesNeeded(a, mid);
        if (trace) cout << "lo=" << lo << " hi=" << hi << " mid=" << mid << " pieces=" << p
                        << " -> " << (p <= k ? "feasible" : "too small") << '\n';
        if (p <= k) hi = mid;          // mid works, so answer <= mid
        else lo = mid + 1;             // mid fails, so answer > mid
    }
    return lo;
}

int main() {
    vector<long long> a = {7, 2, 5, 10, 8};
    long long ans = splitArray(a, 2, true);          // trace lines print first
    cout << "answer = " << ans << '\n';
    cout << "k = 1..5:";
    for (int k = 1; k <= 5; ++k) cout << ' ' << splitArray(a, k, false);
    cout << '\n';
}

lo=10 hi=32 mid=21 pieces=2 -> feasible
lo=10 hi=21 mid=15 pieces=3 -> too small
lo=16 hi=21 mid=18 pieces=2 -> feasible
lo=16 hi=18 mid=17 pieces=3 -> too small
answer = 18
k = 1..5: 32 18 14 10 10

def pieces_needed(a, cap):            # greedy: fewest pieces, each sum <= cap
    pieces, cur = 1, 0
    for x in a:
        if cur + x > cap:                 # x does not fit: start a new piece
            pieces, cur = pieces + 1, 0
        cur += x
    return pieces

def split_array(a, k, trace=False):
    lo, hi = max(a), sum(a)               # the answer is somewhere in [lo, hi]
    while lo < hi:
        mid = lo + (hi - lo) // 2
        p = pieces_needed(a, mid)
        if trace:
            print(f"lo={lo} hi={hi} mid={mid} pieces={p} ->",
                  "feasible" if p <= k else "too small")
        if p <= k:
            hi = mid                      # mid works, so answer <= mid
        else:
            lo = mid + 1                  # mid fails, so answer > mid
    return lo

a = [7, 2, 5, 10, 8]
print("answer =", split_array(a, 2, trace=True))
print("k = 1..5:", *(split_array(a, k) for k in range(1, 6)))

lo=10 hi=32 mid=21 pieces=2 -> feasible
lo=10 hi=21 mid=15 pieces=3 -> too small
lo=16 hi=21 mid=18 pieces=2 -> feasible
lo=16 hi=18 mid=17 pieces=3 -> too small
answer = 18
k = 1..5: 32 18 14 10 10

একই ছাঁচ: D দিনে জাহাজের মাল

চট্টগ্রাম বন্দর থেকে একটি জাহাজ প্রতিদিন একবার যায়। কন্টেইনারগুলো লাইনে দাঁড়ানো, ক্রম বদলানো যায় না: ওজন [3, 2, 2, 4, 1, 4]. D = 3 দিনে সব পাঠাতে জাহাজের সর্বনিম্ন ধারণক্ষমতা কত? এটি হুবহু split array: ধারণক্ষমতা = টুকরোর সীমা, দিন = টুকরো। lo = 4 (সবচেয়ে ভারী কন্টেইনার), hi = 16 (সব একদিনে)। যাচাই হয় 10 (T), 7 (T), 5 (F, লাগে ৪ দিন), 6 (T: [3, 2], [2, 4], [1, 4]) — উত্তর 6. সমস্যার গল্প যতই বদলাক, গঠনটি চিনুন: পাশাপাশি টুকরো, প্রতিটির যোগফলে সীমা, টুকরোর সংখ্যা সীমিত।

৪ · সর্বনিম্নকে সর্বোচ্চ করা — aggressive cows আর হাইওয়ের টাওয়ার

এবার উল্টো ধরনের প্রশ্ন: “maximise the minimum”. একটি মোবাইল অপারেটর (ধরুন Grameenphone) ঢাকা–চট্টগ্রাম হাইওয়ের পাশে কয়েকটি নির্দিষ্ট জায়গায় টাওয়ার বসাতে পারে — জমি পাওয়া গেছে কিলোমিটার চিহ্ন 1, 2, 4, 8 আর 9-এ। বসাতে হবে c = 3টি টাওয়ার। পাশাপাশি দুটি টাওয়ার খুব কাছে হলে সংকেত একে অপরকে বিরক্ত করে, তাই দুটি টাওয়ারের সবচেয়ে ছোট দূরত্বটি যত বড় সম্ভব রাখতে হবে। কনটেস্টে এই সমস্যা “aggressive cows” নামে বিখ্যাত — সেখানে রাগী গরুদের গোয়ালের খোপে যতদূর সম্ভব আলাদা রাখতে হয়।

সিদ্ধান্তের প্রশ্ন: “প্রতিটি জোড়ার দূরত্ব অন্তত d রেখে কি c টি টাওয়ার বসানো যায়?” greedy যাচাই: জায়গাগুলো সাজিয়ে নিন; প্রথম টাওয়ার প্রথম জায়গায়; তারপর বাঁ থেকে ডানে যে প্রথম জায়গাটি শেষ টাওয়ার থেকে অন্তত d দূরে, সেখানে পরেরটি। এখানে predicate উল্টো একমুখী: d দিয়ে হলে d − 1 দিয়েও হবে (একই বিন্যাস চলবে), তাই T…T F…F, আর আমরা চাই শেষ T — অংশ ২-এর LAST-TRUE, ওপরের মধ্যকসহ।

সীমা: d = 0 সবসময় সম্ভব (lo = 0). আর c টি টাওয়ার পুরো দৈর্ঘ্য L = সর্বোচ্চ − সর্বনিম্ন-এর ওপর বসলে c − 1 টি ফাঁক তৈরি হয়, যাদের যোগফল ≤ L; তাই সবচেয়ে ছোট ফাঁক ≤ L / (c − 1) — গড়ের চেয়ে সবচেয়ে ছোটটি বড় হতে পারে না। অতএব hi = ⌊L / (c − 1)⌋ = ⌊8 / 2⌋ = 4. (c = 1 হলে প্রশ্নটি অর্থহীন — কোনো জোড়াই নেই — তাই কোডে c ≥ 2 ধরে নেওয়া।)

greedy যাচাই কেন সঠিক? ধরুন দূরত্ব d রেখে কোনো বৈধ বিন্যাস OPT আছে, c টি টাওয়ারসহ। greedy-র টাওয়ারগুলো g₁ < g₂ < … আর OPT-এর o₁ < o₂ < …. আরোহ (induction) দিয়ে দেখাই gᵢ ≤ oᵢ. i = 1: g₁ সবচেয়ে বাঁয়ের জায়গা, তাই g₁ ≤ o₁. i − 1 থেকে i: oᵢ ≥ oᵢ₋₁ + d ≥ gᵢ₋₁ + d, তাই oᵢ নিজেই greedy-র জন্য একটি যোগ্য জায়গা; greedy সবচেয়ে বাঁয়ের যোগ্য জায়গা নেয়, তাই gᵢ ≤ oᵢ, আর greedy-র কাছে জায়গা ফুরায় না। অর্থাৎ OPT c টি বসাতে পারলে greedy-ও পারে — একটি exchange-ধাঁচের “এগিয়ে থাকা” যুক্তি। আর একমুখিতা: d-তে বৈধ বিন্যাস d − 1-এও বৈধ।

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool canPlace(const vector<long long>& pos, int c, long long d) {
    int placed = 1;
    long long last = pos[0];                         // first tower at the first site
    for (size_t i = 1; i < pos.size(); ++i)
        if (pos[i] - last >= d) { ++placed; last = pos[i]; }   // earliest site that fits
    return placed >= c;
}

long long bestGap(vector<long long> pos, int c, bool trace) {   // needs c >= 2
    sort(pos.begin(), pos.end());
    long long lo = 0, hi = (pos.back() - pos.front()) / (c - 1);
    while (lo < hi) {
        long long mid = lo + (hi - lo + 1) / 2;      // upper middle: lo = mid must move
        bool ok = canPlace(pos, c, mid);
        if (trace) cout << "lo=" << lo << " hi=" << hi << " mid=" << mid
                        << (ok ? " -> fits" : " -> does not fit") << '\n';
        if (ok) lo = mid; else hi = mid - 1;
    }
    return lo;
}

int main() {
    vector<long long> km = {1, 2, 8, 4, 9};          // possible tower sites, unsorted
    long long g = bestGap(km, 3, true);              // trace lines print first
    cout << "best gap for 3 towers = " << g << '\n';
    for (int c = 2; c <= 5; ++c)
        cout << "towers=" << c << " best gap=" << bestGap(km, c, false) << '\n';
}

lo=0 hi=4 mid=2 -> fits
lo=2 hi=4 mid=3 -> fits
lo=3 hi=4 mid=4 -> does not fit
best gap for 3 towers = 3
towers=2 best gap=8
towers=3 best gap=3
towers=4 best gap=1
towers=5 best gap=1

৫ · lo আর hi বাছাই, complexity আর overflow

template-টি নিজে প্রায় কখনো ভুল হয় না; ভুল হয় সীমায়। দুটি নিয়ম মানুন। lo: উত্তর এর নিচে হতেই পারে না, এমন একটি মান — প্রয়োজনে একটু ঢিলেঢালা নিন, শুধু বেশি নয়। hi: এমন একটি মান যেখানে check নিশ্চিতভাবে T (FIRST-TRUE-এ), আর সেটি প্রমাণ করতে পারতে হবে। ঢিলেঢালা সীমায় খরচ সামান্য — পরিসর দ্বিগুণ হলে মাত্র একটি বাড়তি ঘূর্ণন। কিন্তু ভুল দিকে টাইট সীমা দিলে উত্তর পরিসরের বাইরে পড়ে, আর template নিঃশব্দে একটি ভুল প্রান্ত ফেরত দেয়।

লক্ষ করুন, log-এর ভেতরে n নয়, আছে উত্তরের পরিসর। hi = 10¹⁸ হলেও log₂ 10¹⁸ ≈ 60 — মাত্র ৬০টি যাচাই। তাই এই কৌশল অনেক সময় বিশাল সংখ্যার পরিসরেও নির্ভয়ে চলে; আসল খরচ check-এর ভেতরে।

k জন কর্মী আর overflow-এর ফাঁদ

একটি চায়ের দোকানে তিনজন কারিগর: একজন ২ মিনিটে এক কাপ চা বানান, আরেকজন ৩ মিনিটে, তৃতীয়জন ৭ মিনিটে। সবাই একসাথে কাজ করেন। ১০ কাপ চা হতে সর্বনিম্ন কত মিনিট? T মিনিটে কারিগর i বানান ⌊T / tᵢ⌋ কাপ, তাই check(T): Σ⌊T / tᵢ⌋ ≥ 10. T বাড়লে কাপ কমে না — একমুখী। hi = সবচেয়ে দ্রুত কারিগর একা সব বানালে = 2 × 10 = 20. T = 11-এ 5 + 3 + 1 = 9 কাপ (F), T = 12-এ 6 + 4 + 1 = 11 কাপ (T) — উত্তর 12 মিনিট। এই একই গঠন আসে কারখানার মেশিন, ATM বুথ, বা অনলাইন জাজের একাধিক সার্ভারে কাজ ভাগে।

৬ · গণনা দিয়ে k-তম ছোট — গুণের নামতা আর সাজানো ম্যাট্রিক্স

উত্তরের ওপর binary search শুধু অপটিমাইজেশনে নয়, “k-তম ছোট মান কত?” প্রশ্নেও কাজ করে — যখন সব মান লিখে সাজানো খুব ব্যয়বহুল। উদাহরণ: m × n গুণের নামতা, ঘর (i, j)-এ i × j. m = n = 3 × 10⁴ হলে ৯০ কোটি ঘর — সাজানো অসম্ভব। কিন্তু প্রশ্ন “x-এর সমান বা ছোট কয়টি ঘর?” খুব সহজ: সারি i-তে i, 2i, 3i, … — এদের মধ্যে x-এর সমান বা ছোট ⌊x / i⌋ টি, তবে n-এর বেশি নয়। তাই

count(x) x বাড়লে কমে না, তাই predicate “count(x) ≥ k” একমুখী, আর প্রথম T-ই k-তম ছোট মান। 3 × 3 নামতায় k = 5 দেখুন ([ ] মানে ঘরটি x-এর সমান বা ছোট):

উত্তরটি নামতায় আছেই তো? binary search পূর্ণসংখ্যার ওপর চলছে, নামতার মানের ওপর নয় — তাহলে 5-এর মতো একটি মান, যা নামতায় নেই, উত্তর হতে পারে কি? না। ধরুন প্রথম T হলো x*. তাহলে count(x*) ≥ k কিন্তু count(x* − 1) < k, অর্থাৎ count(x*) − count(x* − 1) ≥ 1 — ঠিক x* মানের অন্তত একটি ঘর আছে। প্রথম T সবসময় এমন একটি জায়গা, যেখানে গণনা লাফ দেয়, আর গণনা লাফ দেয় শুধু নামতার মানে। এই যুক্তিটি “k-তম ছোট” ধাঁচের সব সমস্যায় খাটে।

সাজানো ম্যাট্রিক্সে k-তম ছোট। একটি n × n ম্যাট্রিক্সের প্রতিটি সারি আর কলাম বাড়তি ক্রমে সাজানো। count(x) এখানে একটি “সিঁড়ি” হাঁটায় O(n)-এ: নিচের-বাঁ কোণা থেকে শুরু করুন; ঘরটি ≤ x হলে সেই কলামের ওপরের সব ঘরও ≤ x — গণনায় (সারি + 1) যোগ করে ডানে যান; না হলে ওপরে যান। মোট O(n) ধাপ, তাই পুরো সমাধান O(n log(max − min)). কোনো heap বা পুরো সাজানো লাগে না। একই ভাবনা “দুটি সাজানো অ্যারের জোড়া-যোগফলের k-তম ছোট” বা “k-তম ছোট জোড়া-দূরত্ব” জাতীয় সমস্যায়ও চলে — গণনাটি two pointer দিয়ে (পর্ব ১৬).

৭ · দশমিক উত্তর — নির্দিষ্টসংখ্যক ঘূর্ণন আর সর্বোচ্চ গড়

কিছু সমস্যার উত্তর পূর্ণসংখ্যা নয়: একটি বর্গমূল, একটি গতি, একটি গড়। তখন lo আর hi double, আর “প্রথম T” মানে একটি বাস্তব সংখ্যা, যেটি আমরা যতটা দরকার ততটা কাছ থেকে ঘিরে ফেলি। template-এ দুটি বদল: mid = (lo + hi) / 2 (দশমিকে +1 নেই), আর lo = mid / hi = mid — কারণ দশমিকে “পরের মান” বলে কিছু নেই।

Pseudocode: real-valued answer, fixed number of iterations

REAL-FIRST-TRUE(lo, hi, check):        // check(hi) = true, monotone
    repeat 100 times:                  // NOT "while hi - lo > eps"
        mid = (lo + hi) / 2
        if check(mid): hi = mid
        else:          lo = mid
    return hi                          // hi - lo = (initial range) / 2^100

দৈর্ঘ্য অন্তত L, সর্বোচ্চ গড়ের subarray

একটি ক্লাসিক কঠিন সমস্যা: অ্যারে a আর একটি সংখ্যা L দেওয়া। দৈর্ঘ্য অন্তত L এমন কোন subarray-এর গড় সবচেয়ে বেশি? (ধরুন একটি দোকানের দৈনিক লাভ-ক্ষতির হিসাব থেকে “অন্তত ৪ দিনের টানা সময়ে সর্বোচ্চ গড় লাভ”।) সব subarray দেখলে Θ(n²). সিদ্ধান্তের প্রশ্নে বদলাই: “গড় অন্তত x এমন কোনো subarray (দৈর্ঘ্য ≥ L) আছে কি?”

এখানে একটি সুন্দর কৌশল: গড়(a[l..r]) ≥ x ⇔ Σ(a[i] − x) ≥ 0. অর্থাৎ প্রতিটি সংখ্যা থেকে x বাদ দিন, তারপর প্রশ্ন দাঁড়ায় “দৈর্ঘ্য ≥ L এমন কোনো subarray-এর যোগফল ≥ 0?” — পর্ব ১৭-এর prefix sum দিয়ে O(n)-এ: প্রতিটি শেষবিন্দু r-এর জন্য P[r + 1] − min(P[0..r + 1 − L]) ≥ 0 কি না দেখুন, আর চলতি সর্বনিম্নটি এক লুপেই রাখা যায়। x বাড়ালে সব বিয়োগফল কমে, তাই check(x) T…T F…F — চাই শেষ T. a = [1, 12, −5, −6, 50, 3], L = 4-এ উত্তর 12.75 (subarray [12, −5, −6, 50] = 51 / 4). মোট সময় O(n × ঘূর্ণন), যেমন ১০০ ঘূর্ণনে O(100 n).

Pseudocode (0-based): is there a subarray of length >= L with average >= x ?

CHECK-AVG(a, L, x):
    P[0] = 0
    for i = 0 to n - 1: P[i + 1] = P[i] + (a[i] - x)
    best_min = +infinity
    for r = L - 1 to n - 1:
        best_min = min(best_min, P[r + 1 - L])   // earliest allowed start prefix
        if P[r + 1] - best_min >= 0: return true
    return false
// lo = min(a), hi = max(a); LAST-TRUE on reals with 100 iterations

৮ · predicate একমুখী না হলে — বিপদ চেনা, আর ternary search

পুরো কৌশলটি একটি শর্তের ওপর দাঁড়িয়ে: predicate একমুখী। শর্তটি না থাকলে binary search কোনো error দেয় না, ক্র্যাশও করে না — শুধু আত্মবিশ্বাসের সাথে একটি ভুল উত্তর দেয়। একটি উদাহরণ দেখুন। a = [5, −10, 5, 5], S = 5. প্রশ্ন: “সবচেয়ে বড় কোন দৈর্ঘ্য L-এর এমন একটি window আছে, যার যোগফল ≥ 5?” check(L) = “দৈর্ঘ্য ঠিক L এমন কোনো window-এর যোগফল ≥ 5”. কেউ ভাবল “ছোট window পারলে বড়টিও পারবে না” — অর্থাৎ T…T F…F — আর LAST-TRUE চালাল:

একমুখিতা কীভাবে যাচাই করবেন

• প্রমাণের চেষ্টা: “x-এ একটি বৈধ সমাধান থাকলে x + 1-এও আছে” — এক বাক্যে দেখান কীভাবে x-এর সমাধানটিকে x + 1-এর সমাধানে বদলানো যায় (খাতা দেখায় একই সময়সূচি দ্রুত গতিতে আরও আগে শেষ হয়; টাওয়ারে d-এর বিন্যাস d − 1-এও বৈধ)। এই রূপান্তরটি লিখতে না পারলে সন্দেহ করুন।
• brute force দিয়ে সারি ছাপান: ছোট random ইনপুটে সব x-এর জন্য check(x) ছাপুন আর দেখুন F থেকে T-তে একবারের বেশি বদল হয় কি না — কয়েকশো ইনপুটে একটিও T F T বা F T F ধরা পড়লে সেটিই counterexample. এটি stress testing-এর সবচেয়ে সস্তা রূপ।
• সতর্ক সংকেত: ঋণাত্মক সংখ্যা, “ঠিক সমান” (= k, ≥ নয়) ধরনের শর্ত, আর দুই দিক থেকে টানা শর্ত (“যথেষ্ট বড় কিন্তু খুব বড় নয়”). শেষেরটি প্রায়ই একমুখী নয়, বরং “এক চূড়ার” — তখন ternary search ভাবুন।

Ternary search — এক চূড়ার ফাংশনে

কিছু ফাংশন প্রথমে বাড়ে, তারপর কমে — একটিমাত্র চূড়া। যেমন একটি দোকানের দাম p ধরলে লাভ: দাম খুব কম হলে লাভ নেই, খুব বেশি হলে ক্রেতা নেই, মাঝে কোথাও সর্বোচ্চ। এমন ফাংশনকে বলে unimodal function. এর সর্বোচ্চ বিন্দু খুঁজতে ternary search: পরিসরের এক-তৃতীয়াংশ আর দুই-তৃতীয়াংশে দুটি বিন্দু m₁ < m₂ নিন। f(m₁) < f(m₂) হলে চূড়া m₁-এর বাঁয়ে হতে পারে না — lo = m₁; না হলে চূড়া m₂-এর ডানে হতে পারে না — hi = m₂. প্রতি ধাপে পরিসরের এক-তৃতীয়াংশ বাদ, তাই O(log n) ধাপ (ভিত্তি 3/2).

Pseudocode: maximum of a strictly unimodal f on integers [lo, hi]

TERNARY-MAX(lo, hi, f):
    while hi - lo > 2:
        m1 = lo + (hi - lo) / 3
        m2 = hi - (hi - lo) / 3
        if f(m1) < f(m2): lo = m1 + 1     // peak is right of m1
        else:             hi = m2         // peak is at or left of m2
    return the best of f(lo), ..., f(hi)  // at most 3 values

// Often simpler on integers: FIRST-TRUE on check(x) = f(x) >= f(x + 1)

পূর্ণসংখ্যায় আরও পরিষ্কার একটি পথ: “f(x) ≥ f(x + 1)?” predicate-টি এক চূড়ার ফাংশনে F…F T…T — চূড়ার আগে ফাংশন বাড়ছে (F), চূড়া থেকে কমছে (T). তাই সাধারণ FIRST-TRUE-ই চূড়া দেয়, আর আমাদের পরিচিত invariant কাজে লাগে। সাবধান: ফাংশনে সমতল অংশ থাকলে (একাধিক x-এ একই মান, চূড়ার বাইরে) দুটি পদ্ধতিই ভুল দিকে যেতে পারে — ternary search চায় কঠোরভাবে বাড়া আর কঠোরভাবে কমা।

৯ · AI-এর যুগে উত্তরের ওপর binary search — template সহজ, প্রমাণ কঠিন

“Split array largest sum সমাধান করো” লিখলে যেকোনো AI কয়েক সেকেন্ডে সঠিক কোড দেয় — সমস্যাটি অত্যন্ত পরিচিত। কিন্তু যখন সমস্যাটি নতুন গল্পে আসে, AI-এর দুটি দুর্বলতা দেখা দেয়। প্রথমত, এটি প্রায়ই predicate একমুখী কি না প্রমাণ না করেই binary search বসিয়ে দেয় — দেখতে মসৃণ, চলেও, শুধু কিছু ইনপুটে ভুল। দ্বিতীয়ত, সীমা আর মধ্যকের খুঁটিনাটিতে off-by-one ভুল: lo = mid-এর সাথে নিচের মধ্যক, hi এমন মান যেখানে check F, বা check-এর ভেতরে overflow. আর complexity-তে প্রায়ই “O(n log n)” লিখে দেয়, যেখানে আসল উত্তর O(n log S).

এই কৌশলে AI সাধারণত যেসব ভুল করে

AI-এর (বা নিজের) কোড যাচাইয়ের চেকলিস্ট

• check(x) এক বাক্যে লিখেছি, আর “x-এ হলে x + 1-এও” (বা উল্টো) প্রমাণটি লিখতে পেরেছি
• lo-এর নিচে উত্তর অসম্ভব আর hi-তে check নিশ্চিত — দুটিরই যুক্তি আছে; “অসম্ভব” ইনপুট আলাদা করে সামলানো
• hi = mid হলে নিচের মধ্যক, lo = mid হলে ওপরের মধ্যক — দুই উপাদানের পরিসরে হাতে dry run করেছি
• mid = lo + (hi − lo) / 2, আর check-এর ভেতরের যোগফল long long-এ বা আগে-থামাসহ
• greedy check-এর শুদ্ধতা (এগিয়ে থাকা যুক্তি) বুঝেছি, আর দরকার হলে ইনপুট সাজিয়েছি
• ছোট random ইনপুটে brute force-এর সাথে কয়েকশো বার মিলিয়েছি, আর complexity O(log(range) × cost(check)) হিসেবে লিখেছি