বাইসেকশনঃ উত্তরটা না জেনেও উত্তর খুঁজে বের করার কৌশল

ছোটবেলার সেই খেলাটা মনে আছে? বন্ধু বলত, "১ থেকে ১০০০ এর মধ্যে একটা সংখ্যা ভেবেছি, বল তো কত?" তুমি বলতে ৫০০। ও বলত "ছোট"। তুমি বলতে ৭৫০। "বড়"। দশ-বারো বারের মধ্যেই তুমি বের করে ফেলতে, আর বন্ধু বিরক্ত হয়ে বলত, "তুই নিশ্চয়ই চিট করছিস!" তুমি চিট করোনি। তুমি শুধু প্রতিবার অর্ধেক ফেলে দিচ্ছিলে।

আগের লেখায় আমরা দেখেছি সাজানো অ্যারেতে বাইনারি সার্চ কীভাবে কাজ করে। আজ আমরা এমন জায়গায় এটা ব্যবহার করব যেখানে কোনো অ্যারেই নেই। এই কৌশলটার নাম বাইসেকশন মেথড অথবা Competitive Parogram-এর ভাষায়, "binary search on the answer"।

মূল চিন্তার মোড়টা এখানে

সাধারণ বাইনারি সার্চে তুমি খোঁজো একটা অ্যারের ভেতর। বাইসেকশনে তুমি খোঁজো উত্তরটা যে রেঞ্জে থাকতে পারে তার ভেতর। অ্যারে লাগে না, Memory-তে কিছু রাখতে হয় না। শুধু একটা রেঞ্জ, আর একটা প্রশ্নঃ "আমার আন্দাজটা কি বেশি বড়, নাকি বেশি ছোট?"

নিজের হাতে বর্গমূল বানাই

ধরো তুমি এমন একটা ভাষায় কোড করছ যেখানে sqrt() বলে কিছু নেই। গণিতের কঠিন সূত্রে যাওয়ার দরকার নেই। আমরা জানি X-এর বর্গমূল অবশ্যই ০ থেকে X-এর মধ্যে আছে। ব্যস, এটুকুই যথেষ্ট।

X = 15 নিয়ে হাতে-কলমেঃ

ছয় ধাপেই ৩.৭৫ থেকে ৩.৯৮-এর মধ্যে আটকে ফেলেছি। আসল উত্তর ৩.৮৭২৯৮।

def my_sqrt(x, eps=1e-9):
    low, high = 0.0, max(x, 1.0)      # x < 1 হলে বর্গমূল x-এর চেয়ে বড়!
    while high - low > eps:
        mid = (low + high) / 2
        if mid * mid > x:
            high = mid
        else:
            low = mid
    return (low + high) / 2

print(my_sqrt(15))   # 3.8729833463730756  (আসল মান 3.872983346207417)

একটা ছোট Trap খেয়াল করেছ? high = x লিখলে x = 0.25-এর জন্য কোড ভুল উত্তর দেবে, কারণ √0.25 = 0.5, যা x-এর চেয়ে বড়, রেঞ্জের বাইরে! তাই max(x, 1.0)। এই ধরনের Corner কেসগুলোই সাধারণত জাজে WA খাওয়ায়।

কতক্ষণ খুঁজব? একটা মাপা উত্তর

অনেকে বলে "নিরাপদ থাকতে ২০০ বার Loop ঘোরাও"। সত্যিই কি দরকার? মেপে দেখা যাক (X = 15):

প্রতি ১০ ধাপে ভুল প্রায় ১০০০ গুণ কমছে। কারণ ১০ বার অর্ধেক করা মানে ২¹⁰ ≈ ১০২৪ ভাগ করা। আর ৬০ ধাপে ভুল একদম শূন্যঃ double যতটুকু নির্ভুলতা ধরতে পারে, তার সীমায় পৌঁছে গেছি। এরপর Loop ঘোরানো মানে শুধু CPU-র সময় নষ্ট। ব্যবহারিক নিয়মঃ ১০০ ধাপ লিখে দাও, নিশ্চিন্ত থাকো। while (high - low > eps)-এর চেয়ে for i in range(100) নিরাপদ, কারণ eps খুব ছোট দিলে while-লুপ কখনো অসীম হয়ে যেতে পারে।

Golden Rules: কখন বাইসেকশন খাটবে?

এটাই পুরো লেখার সবচেয়ে গুরুত্বপূর্ণ অংশ। বর্গমূলে বাইসেকশন খেটেছে কারণ x বাড়লে x² সবসময় বাড়ে। তাই mid² বড় দেখলেই নিশ্চিতভাবে বলা যায় "উত্তর বামে"। এখন ভাবো, sin(x) + 5·log₁₀(x) = 5 সমীকরণটা একইভাবে সমাধান করতে চাইলে? তুমি একটা mid নিলে, মান বেশি এলো। কিন্তু উত্তর বামে না ডানে? বলার কোনো উপায় নেই, কারণ x কমলে মানটা বাড়তেও পারে, কমতেও পারে।

নিয়মটা এক লাইনেঃ মাঝের মানটা দেখে যদি এক পাশ নিশ্চিতভাবে বাদ দিতে পারো, তবেই বাইসেকশন Valid। এটাকে বলে monotonicity। তাই log(x) + x² = y হবে, কিন্তু tan(x) + x² = y হবে না।

চিন্তার কাঠামোঃ তিনটা প্রশ্ন

1. আমি কোন একটামাত্র সংখ্যা খুঁজছি?
2. কোনো আন্দাজ ধরে নিলে "চলবে কি চলবে না" যাচাই করা কি সহজ?
3. সেই যাচাইয়ের উত্তরটা কি monotonic?

তিনটার উত্তরই "হ্যাঁ" হলে বাইসেকশন লিখে ফেলো।

এবার একটা আসল প্রবলেম

LightOJ 1043 — Triangle Partitioning

ত্রিভুজ ABC-এর AB, AC আর BC দেওয়া আছে। DE রেখাটা BC-এর সমান্তরাল। ADE ত্রিভুজ আর BDEC ট্রাপিজিয়ামের ক্ষেত্রফলের অনুপাত R দেওয়া আছে। AD-এর দৈর্ঘ্য বের করতে হবে।

১. কী খুঁজছি? AD, একটা সংখ্যা

২. যাচাই সহজ? ধরো AD = x। DE ∥ BC হওয়ায় ADE আর ABC সদৃশ। সদৃশ ত্রিভুজে ক্ষেত্রফলের অনুপাত = বাহুর অনুপাতের বর্গ। k = x/AB ধরলে ADE = k², BDEC = (1 − k²), অনুপাত = k²/(1 − k²)। খেয়াল করো, ABC-এর আসল ক্ষেত্রফল কেটে যাচ্ছে, হেরনের সূত্রই লাগছে না

৩. Monotonic? x বাড়লে k² বাড়ে, (1 − k²) কমে, অনুপাত সবসময় বাড়ে

def solve(AB, R):
    low, high = 0.0, AB
    for _ in range(100):
        mid = (low + high) / 2
        k = mid / AB
        ade = k * k                 # ABC-কে ১ ধরে নিলাম
        if ade / (1.0 - ade) < R:   # অনুপাত ছোট → AD আরও বড় হবে
            low = mid
        else:
            high = mid
    return (low + high) / 2

চারটাই মিলে গেছে

এখন মজার অংশটা

আমরা AC আর BC একবারও ব্যবহার করিনি। আর একটু বীজগণিত করলেঃ

R = k²/(1 − k²)  →  R = k²(1 + R)  →  k = √( R/(1+R) )
AD = AB × √( R / (1 + R) )

পুরো প্রবলেমটার এক লাইনের সূত্র আছে! তাহলে বাইসেকশন শেখা বৃথা গেল?

বাইসেকশন হলো তোমার নিরাপত্তা জাল। কনটেস্টে ওই বীজগণিত মাথায় নাও আসতে পারে। কিন্তু "AD বাড়লে অনুপাত বাড়ে" এই পর্যবেক্ষণটা যে কেউ ২ মিনিটে করতে পারে। সূত্র না পেলেও তুমি AC পেয়ে যাবে।

এই কৌশল আজও কোথায় কাজে লাগে

• git bisect-এ হুবহু একই ধারণা। হাজারটা কমিটে কোনটায় বাগ ঢুকেছে, ১০-১১ বার চেকেই বের হয়। monotonicity: বাগের আগের সব ভালো, পরের সব খারাপ।
• ক্যাপাসিটি পরিকল্পনা "কত RPS পর্যন্ত latency ১০০ms-এর নিচে?"
• মেশিন লার্নিং কোয়ান্টাইজেশন থ্রেশহোল্ড বা লার্নিং রেট খোঁজা।
• অটোস্কেলিং সবচেয়ে ছোট পড-সংখ্যা যেটায় কাজ চলে।

আর এই AI-এর যুগে টুল যতই শক্তিশালী হোক, "এই সমস্যাটা কি monotonic?" প্রশ্নটা তোমাকেই করতে হবে। কোড লিখে দেওয়ার লোকের অভাব নেই; সঠিক প্রশ্ন করার লোকের অভাব আছে।

কীভাবে অনুশীলন করলে সত্যিই শেখা হবে

1. আগে ৩টা প্রশ্ন, তারপর কোড।
2. check(mid) আলাদা ফাংশনে লেখো।
3. ছোট ইনপুটে brute-force দিয়ে মিলাও।
4. Corner কেস খাতায় লেখো। x = 0, x < 1, R খুব বড়/ছোট।
5. AC পেয়েও থেমো না, "সূত্র দিয়ে হয় কি?" 

অনুশীলনের জন্য

• LightOJ 1043 — Triangle Partitioning
• LightOJ 1076 — Get the Containers — "সর্বোচ্চ মানকে সর্বনিম্ন করো" 
• SPOJ — Aggressive Cows 
• Codeforces EDU — Binary Search — সেরা আধুনিক রিসোর্স

নিজে ভেবে দেখোঃ গ্রাফে A থেকে E যেতে চাও এমনভাবে যেন পথের সবচেয়ে weighted রাস্তাটা যতটা সম্ভব হালকা হয়। সীমা L ধরো, L-এর চেয়ে heavy সব রাস্তা মুছে দেখো A→E যায় কি না। এই "যায় কি না"-টা কি monotonic?