098 — Aggressive Cows

এখন পর্যন্ত সব ছিল minimize — "সবচেয়ে ছোট valid উত্তর"। এই problem-এ প্রথমবার মাথাটা উল্টাতে হবে: maximize — "সবচেয়ে বড় valid উত্তর"। গরুগুলো ঝগড়াটে, তাই দুই গরুর মাঝের সবচেয়ে কাছের দূরত্ব যত বড় করা যায়। সিঁড়িটা উল্টে যায় (T T T F F F), আর binary search-এর move-ও উল্টো। এই উল্টোটা ভালো করে বুঝলে minimize আর maximize আর কখনো গুলোবে না।

Source

• Original source: SPOJ AGGRCOW
• Platform: SPOJ — https://www.spoj.com/problems/AGGRCOW/
• Topic: Math-based programming fundamentals → Level 7: Binary Search on Answer
• Difficulty: Medium
• Pattern: BSoA maximize (সবচেয়ে বড় feasible উত্তর; সিঁড়ি TTTFFF)
• Basic idea inherited from: 096 — Minimum Eating Speed

1. Problem in simple words

একটা সরলরেখায় কতগুলো গোয়ালঘর (stall) আছে, stalls[i] হলো i-তম stall-এর অবস্থান (একটা সংখ্যা)। তোমার কাছে c টা গরু, প্রত্যেককে আলাদা stall-এ রাখতে হবে।

গরুগুলো আগ্রাসী — কাছাকাছি থাকলে ঝগড়া করে। তাই তুমি চাও যেকোনো দুই গরুর মধ্যে সবচেয়ে কম দূরত্বটা যত বড় সম্ভব হোক। প্রশ্ন: c টা গরু এমনভাবে বসালে, এই minimum দূরত্বের সর্বোচ্চ মান কত?

মানে আমরা minimum gap-টাকে maximize করছি — তাই একে "maximize the minimum" বলে।

2. What is the math idea?

maximize ঘরানার BSoA। উত্তর (সবচেয়ে বড় minimum gap) সরাসরি বের না করে, একটা gap g guess করি আর check: "প্রতি দুই গরুর মাঝে অন্তত g দূরত্ব রেখে c টা গরু বসানো যায়?"

observation — g ছোট হলে বসানো সহজ, বড় হলে কঠিন। তাই সিঁড়ি এবার উল্টো: T T T F F F — ছোট g-তে পারা যায় (T), একটা জায়গার পর আর যায় না (F)। শেষ T-টাই সবচেয়ে বড় feasible gap — আমাদের উত্তর।

3. Which basic idea does this inherit from?

096 (Minimum Eating Speed) থেকে — answer space + feasibility check + monotonicity, সেই তিন উপাদান এখানেও। কিন্তু দুটো বড় বদল:

• দিক উল্টো: 096-এ সিঁড়ি F F F T T T, প্রথম T খুঁজতাম; এখানে T T T F F F, শেষ T খুঁজি।
• move উল্টো: 096-এ check পাশ করলে hi = mid (ছোট খুঁজি); এখানে পাশ করলে lo = mid (আরও বড় খুঁজি)। আর তাই mid উপরে ঝোঁকাতে হয় ((lo+hi+1)//2), নইলে infinite loop।

check-এর ভেতরের greedy (097-এর মতো এক পাস) এখানেও — কিন্তু এবার "একটা বসাও, g দূরত্ব পেলেই পরেরটা"।

4. Real-life analogy

ভাবো একটা লম্বা বেঞ্চে কয়েকটা নির্দিষ্ট জায়গায় বসা যায় (stall), আর তোমরা ক'জন বন্ধু যারা একে অপরের গা ঘেঁষে বসতে চাও না — যত দূরে দূরে, তত ভালো।

তুমি চেষ্টা করো — "সবাই অন্তত 3 হাত দূরে বসতে পারব?" যদি জায়গা কুলোয়, তাহলে ভাবো "5 হাত দূরে?" আরও ছড়িয়ে দেখো। একসময় এমন দূরত্ব আসে যে আর সবাইকে বসানো যায় না — তার ঠিক আগেরটাই সর্বোচ্চ সম্ভব দূরত্ব। দূরত্ব = gap g, বন্ধু = c টা গরু।

5. Visual explanation

stalls = [1, 2, 4, 8, 9], c = 3। প্রতিটা gap g-এর জন্য "অন্তত g রেখে 3টা বসে?":

g       :  1   2   3   4 | 5   6   7 ...
বসানো যায়?:  T   T   T   T | F   F   F ...    check(g) = "gap ≥ g রেখে 3টা গরু বসে?"
                       ↑
              শেষ T → উত্তর = 3

g=3: stall 1-এ বসাও → 4 (4-1=3≥3) → 8 (8-4=4≥3) → 3টা বসল ✓ T
g=4: stall 1-এ বসাও → 8 (8-1=7≥4, কিন্তু 4 বাদ গেল কারণ 4-1=3<4) → 9 শেষ, মোট 2টা < 3 ✗ F

সিঁড়ি T T T F F F (096-এর উল্টো) — g বাড়লে বসানো কঠিন, শেষ T = সবচেয়ে বড় feasible gap।

6. Example input and output

stalls (sorted)      c   ->  max min-gap   (ব্যাখ্যা)
---------------------------------------------------
[1, 2, 4, 8, 9]      3   ->  3     (1, 4, 8 → gap 3, 4)
[1, 2, 8, 4, 9]      3   ->  3     (sort করে নিতে হয় → একই)
[0, 3, 4, 7, 10, 9]  4   ->  3     (0, 3, 7, 10 → min gap 3)
[1, 5]               2   ->  4     (দুই গরু দুই প্রান্তে → 5-1)
[1, 2, 3, 4, 5]      5   ->  1     (সব stall-এ গরু → পাশাপাশি gap 1)

edge: c == len(stalls) হলে প্রতিটা stall-এ একটা গরু বসাতেই হবে → min gap = পরপর দুই stall-এর সবচেয়ে ছোট ফারাক। আর c == 2 হলে দুই প্রান্তে বসানোই সেরা → gap = max - min।

7. Brute force thinking

stall sort করো। তারপর gap g = 1 থেকে শুরু করে এক এক করে বাড়াও; প্রতি g-তে greedy-তে চেক করো c টা বসে কিনা — প্রথম যে g-তে আর বসে না, তার ঠিক আগেরটাই উত্তর:

def aggressive_cows_brute(stalls, c):
    stalls = sorted(stalls)
    def can(g):
        cnt, last = 1, stalls[0]          # প্রথম গরু প্রথম stall-এ
        for s in stalls[1:]:
            if s - last >= g:
                cnt += 1; last = s
        return cnt >= c
    g = 1
    while can(g):                          # যতক্ষণ বসে, gap বাড়াও
        g += 1
    return g - 1                           # প্রথম "বসে না"-র আগেরটা

can(g) greedy: প্রথম stall-এ একটা বসাও, তারপর যেখানেই last গরু থেকে অন্তত g দূরত্ব পাও, সেখানেই পরের গরু। মোট c টা বসলে feasible। তারপর g বাড়িয়ে শেষ feasible-টা ধরি।

8. Why brute force may be slow

g-এর পরিসর 1 থেকে max - min পর্যন্ত — যা 10^9 স্কেল হতে পারে। প্রতি g-তে greedy O(n)। তাই O(n · (max - min)) — অচল।

max - min ≈ 10^9, n = 10^5 হলে:
  brute force   : ~10^14 operation  (অসম্ভব ধীর, TLE)
  binary search : ~30 × 10^5 ≈ 3×10^6  (O(n log(range)), দ্রুত)

মূল শিক্ষা: can(g) monotonic (T...F) — তাই g এক এক করে না বাড়িয়ে binary search-এ অর্ধেক বাদ।

9. Better thinking

মূল insight: can(g)-এর সিঁড়ি T T T F F F — monotonic। শেষ T খুঁজি, maximize template-এ:

def aggressive_cows(stalls, c):
    stalls = sorted(stalls)
    def can(g):                                  # gap ≥ g রেখে c টা বসে?
        cnt, last = 1, stalls[0]
        for s in stalls[1:]:
            if s - last >= g:
                cnt += 1; last = s
        return cnt >= c

    lo, hi = 0, stalls[-1] - stalls[0]           # gap 0 সবসময় হয়; সর্বোচ্চ = পরিসর
    while lo < hi:
        mid = (lo + hi + 1) // 2                 # উপরে ঝোঁকানো mid (lo = mid থাকায়)!
        if can(mid):
            lo = mid                             # পারা যায় → আরও বড় চেষ্টা (mid রেখে দাও)
        else:
            hi = mid - 1                         # পারা যায় না → ছোট লাগবে
    return lo

প্রতি ধাপে অর্ধেক, প্রতি check O(n) → O(n log(range))।

10. Thinking tweak

আসল মোচড় — minimize থেকে maximize-এ গেলে দুটো জিনিস একসাথে উল্টাও:

1. move: check পাশ করলে lo = mid (আরও বড় চাই, mid রেখে দাও), fail করলে hi = mid - 1। (096-এ ছিল উল্টো।)
2. mid-এর ঝোঁক: যেহেতু lo = mid, তাই mid = (lo + hi + 1) // 2 — উপরে ঝোঁকানো। নইলে hi - lo == 1 অবস্থায় mid = lo হয়ে lo = mid কোনো অগ্রগতি করে না → চিরঘূর্ণন (infinite loop)।

নিয়মটা গেঁথে নাও: lo = mid থাকলে mid উপরে ঝোঁকাও (+1); hi = mid থাকলে নিচে। সিঁড়ির ছবি এঁকে দেখো T কোন পাশে জমে — সেই দিকেই চাপতে হবে।

11. Step-by-step dry run

stalls = [1, 2, 4, 8, 9], c = 3 (sorted; lo=0, hi=9-1=8):

step	lo	hi	mid=(lo+hi+1)//2	can(mid)? (কতটা বসে)	সিদ্ধান্ত
1	0	8	4	2টা < 3 → না	hi = mid - 1 = 3
2	0	3	2	3টা (1,4,8) → হ্যাঁ	lo = mid = 2
3	2	3	3	3টা (1,4,8) → হ্যাঁ	lo = mid = 3
—	3	3	—	—	lo == hi = 3 → return 3

উত্তর 3 ✓। লক্ষ করো step 1-এ mid উপরে ঝোঁকানো (4, নিচে হলে 4-ই হতো এখানে) — আর step 3-এ lo = mid করেও mid উপরে ঝোঁকা বলে hi - lo == 0 হয়ে loop থামল, আটকে গেল না।

12. Python solution

def aggressive_cows(stalls, c):
    """c টা গরু এমনভাবে বসাও যাতে minimum gap সবচেয়ে বড় হয়।"""
    stalls = sorted(stalls)                       # রেখার উপর সাজিয়ে নিই
    def can(g):                                   # gap ≥ g রেখে c টা গরু বসে?
        cnt, last = 1, stalls[0]                  # প্রথম গরু প্রথম stall-এ
        for s in stalls[1:]:
            if s - last >= g:                     # যথেষ্ট দূর → পরের গরু এখানে
                cnt += 1
                last = s
        return cnt >= c

    lo, hi = 0, stalls[-1] - stalls[0]            # gap 0 always; max = দুই প্রান্তের ফারাক
    while lo < hi:
        mid = (lo + hi + 1) // 2                  # lo=mid থাকায় mid উপরে ঝোঁকানো
        if can(mid):
            lo = mid                              # পারা যায় → আরও বড় চেষ্টা
        else:
            hi = mid - 1                          # পারা যায় না → ছোট লাগবে
    return lo


def cows_brute(stalls, c):                        # ছোট input-এ cross-check
    stalls = sorted(stalls)
    def can(g):
        cnt, last = 1, stalls[0]
        for s in stalls[1:]:
            if s - last >= g:
                cnt += 1; last = s
        return cnt >= c
    g = 0
    while can(g + 1):                             # পরের gap-ও কি চলে?
        g += 1
    return g


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert aggressive_cows([1, 2, 4, 8, 9], 3) == 3
assert aggressive_cows([1, 2, 8, 4, 9], 3) == 3        # unsorted ইনপুট
assert aggressive_cows([0, 3, 4, 7, 10, 9], 4) == 3
assert aggressive_cows([1, 5], 2) == 4                 # দুই প্রান্তে
assert aggressive_cows([1, 2, 3, 4, 5], 5) == 1        # সব stall-এ
assert aggressive_cows([10, 1, 2, 7, 5], 3) == 4       # SPOJ sample

# brute force-এর সাথে random cross-check
import random
random.seed(13)
for _ in range(300):
    n = random.randint(2, 8)
    stalls = random.sample(range(0, 40), n)            # আলাদা position
    c = random.randint(2, n)
    assert aggressive_cows(stalls, c) == cows_brute(stalls, c)

# boundary: উত্তর g-তে বসে, g+1-এ বসে না
stalls, c = [1, 2, 4, 8, 9], 3
g = aggressive_cows(stalls, c)
def fits(arr, gap, k):
    cnt, last = 1, arr[0]
    for s in arr[1:]:
        if s - last >= gap:
            cnt += 1; last = s
    return cnt >= k
ss = sorted(stalls)
assert fits(ss, g, c)
assert not fits(ss, g + 1, c)

print(aggressive_cows([1, 2, 4, 8, 9], 3))   # 3
print(aggressive_cows([10, 1, 2, 7, 5], 3))  # 4
print("সব test pass!")

13. Line-by-line explanation

stalls = sorted(stalls)

greedy বসানো কাজ করে শুধু sorted রেখায় — তাই আগে সাজাই। ইনপুট unsorted এলেও এই লাইন সামলে নেয়।

cnt, last = 1, stalls[0]

প্রথম গরু সবসময় প্রথম (সবচেয়ে বাঁয়ের) stall-এ — এটাই সবচেয়ে বেশি জায়গা ছাড়ে। cnt = বসানো গরুর সংখ্যা, last = শেষ বসানো গরুর position।

if s - last >= g: cnt += 1; last = s

চলতি stall শেষ গরু থেকে অন্তত g দূরে — তাই এখানে পরের গরু বসাও, last আপডেট। যথেষ্ট দূরে না হলে এই stall এড়িয়ে যাই।

lo, hi = 0, stalls[-1] - stalls[0]

answer space। gap 0 সবসময় সম্ভব (T), তাই lo = 0। সর্বোচ্চ সম্ভব gap দুই প্রান্তের ফারাক (এর বেশি দূরত্ব রাখা অসম্ভব), তাই hi = stalls[-1] - stalls[0]।

mid = (lo + hi + 1) // 2

উপরে ঝোঁকানো mid — কারণ নিচে lo = mid। +1 না দিলে hi - lo == 1-এ infinite loop। (maximize-এর স্বাক্ষর।)

if can(mid): lo = mid   /   else: hi = mid - 1

maximize move: পারলে আরও বড় খুঁজি (mid রেখে lo = mid), না পারলে ছোট লাগবে (hi = mid - 1)। 096-এর ঠিক উল্টো।

cross-check-এ random brute force আর boundary (g বসে, g+1 বসে না)। সব মিললে সব test pass!।

14. Output walkthrough

চালালে যা ছাপবে:

3
4
সব test pass!

প্রথম: aggressive_cows([1,2,4,8,9], 3) = 3 (dry run-এর ফল)। দ্বিতীয়: [10,1,2,7,5] c=3-এ = 4 (sort → [1,2,5,7,10]; 1,5,10 → min gap 4)। আগের সব assert — random cross-check (300 কেস) আর boundary যাচাই — চুপচাপ pass। সবশেষে সব test pass!।

15. Time complexity

O(n log(range)) — sort-এ O(n log n), তারপর answer space [0, max-min]-এ binary search (log(range) ধাপ), প্রতি ধাপে check O(n)। মোট O(n log n + n log(range))।

16. Space complexity

O(1) (sort-কে in-place ধরলে; Python-এর sorted আসলে O(n) extra বানায়) — check-এ শুধু cnt, last; বাড়তি কাঠামো নেই।

17. Common mistakes

1. sort করতে ভুলে যাওয়া — greedy বসানো sorted রেখা ছাড়া অর্থহীন; ভুল উত্তর। সবার আগে sort।
2. maximize-এর mid নিচে ঝোঁকানো — lo = mid থাকলে mid = (lo+hi)//2 দিলে hi-lo==1-এ infinite loop। +1 দাও।
3. minimize-এর move লিখে ফেলা — পাশ করলে এখানে lo = mid (বড় খোঁজো), hi = mid না। সিঁড়ি TTTFFF মনে রাখো।
4. return g vs return g - 1 (brute force-এ) — শেষ T কোনটা সেটা সাবধানে; binary search version এই ফাঁদ এড়ায় কারণ lo-ই শেষ T।
5. প্রথম গরু প্রথম stall-এ না বসানো — greedy-তে প্রথমটা সবচেয়ে বাঁয়ে বসানোই optimal; অন্য কোথাও শুরু করলে কম গরু বসে।

18. Harder problems that inherit this idea

• LeetCode — Magnetic Force Between Two Balls (https://leetcode.com/problems/magnetic-force-between-two-balls/) — হুবহু aggressive cows (ball = গরু, force = gap); একই maximize-the-minimum।
• LeetCode — Divide Chocolate (https://leetcode.com/problems/divide-chocolate/) — সবচেয়ে ছোট টুকরোটা যত বড় সম্ভব; একই উল্টো সিঁড়ি।
• 102 (Kth Smallest in Multiplication Table) — এই repo-রই পরের ধাপ; সেখানে দিক আলাদা কিন্তু "guess + count/greedy check" চিন্তা একই পরিবার।

19. Pattern learned

BSoA maximize (largest feasible answer; TTTFFF) — check পাশ → lo = mid, fail → hi = mid - 1, আর mid = (lo+hi+1)//2 (উপরে ঝোঁকা)। বড় শিক্ষা: "maximize the minimum" (বা "সবচেয়ে বড় valid X") শুনলেই — সিঁড়ি উল্টে যায়, শেষ T খোঁজো, move আর mid-এর ঝোঁক দুটোই উল্টাও। minimize আর maximize-এর এই জোড়া চিনে রাখাই এই level-এর আসল পরিপক্বতা।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "Aggressive Cows = maximize BSoA; answer = min-gap, check = greedy-তে gap≥g রেখে c টা বসে?, সিঁড়ি TTTFFF, শেষ T-ই উত্তর। sort আগে; পাশ→lo=mid, fail→hi=mid-1, mid=(lo+hi+1)//2 (উপরে ঝোঁকা — নইলে infinite loop)। 'maximize the minimum' = এই ছক।"

পরের ধাপ → 099 — Allocate Minimum Pages (আবার minimize, কিন্তু "minimize the maximum load")। সম্পর্কিত → 096 — Minimum Eating Speed (এর উল্টো ঘরানা)।

ফিরে দেখা: এই level-এর map → ../README.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখো; problem statement copy কোরো না; official link শুধু attribution-এর জন্য রাখো; "asked by Google/Amazon" এমন দাবি কোরো না — বরং "Google-style pattern" / "common interview pattern" লেখো।