Problem link ও উৎস
- **Original source:** SPOJ AGGRCOW
- **Platform:** SPOJ —
- **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
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা সরলরেখায় কতগুলো গোয়ালঘর (stall) আছে, `stalls[i]` হলো i-তম stall-এর অবস্থান (একটা সংখ্যা)। তোমার কাছে `c` টা গরু, প্রত্যেককে আলাদা stall-এ রাখতে হবে।
গরুগুলো আগ্রাসী — কাছাকাছি থাকলে ঝগড়া করে। তাই তুমি চাও **যেকোনো দুই গরুর মধ্যে সবচেয়ে কম দূরত্বটা যত বড় সম্ভব** হোক। প্রশ্ন: c টা গরু এমনভাবে বসালে, এই minimum দূরত্বের সর্বোচ্চ মান কত?
মানে আমরা minimum gap-টাকে **maximize** করছি — তাই একে "maximize the minimum" বলে।
### Input ও output {#6-example-input-and-output}
```text
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`।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা লম্বা বেঞ্চে কয়েকটা নির্দিষ্ট জায়গায় বসা যায় (stall), আর তোমরা ক'জন বন্ধু যারা একে অপরের গা ঘেঁষে বসতে চাও না — যত দূরে দূরে, তত ভালো।
তুমি চেষ্টা করো — "সবাই অন্তত 3 হাত দূরে বসতে পারব?" যদি জায়গা কুলোয়, তাহলে ভাবো "5 হাত দূরে?" আরও ছড়িয়ে দেখো। একসময় এমন দূরত্ব আসে যে আর সবাইকে বসানো যায় না — তার ঠিক আগেরটাই সর্বোচ্চ সম্ভব দূরত্ব। দূরত্ব = gap g, বন্ধু = c টা গরু।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 দূরত্ব পেলেই পরেরটা"।
### ভেতরের অঙ্ক {#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 — আমাদের উত্তর।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
stall sort করো। তারপর gap g = 1 থেকে শুরু করে এক এক করে বাড়াও; প্রতি g-তে greedy-তে চেক করো c টা বসে কিনা — প্রথম যে g-তে **আর বসে না**, তার ঠিক আগেরটাই উত্তর:
```python
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))** — অচল।
```text
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-এ:
```python
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 কোন পাশে জমে — সেই দিকেই চাপতে হবে।
### ছবিতে বোঝা {#5-visual-explanation}
`stalls = [1, 2, 4, 8, 9], c = 3`। প্রতিটা gap g-এর জন্য "অন্তত g রেখে 3টা বসে?":
```text
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।
### ছোট input-এ ধাপে ধাপে {#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 থামল, আটকে গেল না।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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}
```text
stalls = sorted(stalls)
```
greedy বসানো কাজ করে শুধু sorted রেখায় — তাই আগে সাজাই। ইনপুট unsorted এলেও এই লাইন সামলে নেয়।
```text
cnt, last = 1, stalls[0]
```
প্রথম গরু সবসময় প্রথম (সবচেয়ে বাঁয়ের) stall-এ — এটাই সবচেয়ে বেশি জায়গা ছাড়ে। `cnt` = বসানো গরুর সংখ্যা, `last` = শেষ বসানো গরুর position।
```text
if s - last >= g: cnt += 1; last = s
```
চলতি stall শেষ গরু থেকে অন্তত g দূরে — তাই এখানে পরের গরু বসাও, `last` আপডেট। যথেষ্ট দূরে না হলে এই stall এড়িয়ে যাই।
```text
lo, hi = 0, stalls[-1] - stalls[0]
```
answer space। gap 0 সবসময় সম্ভব (T), তাই `lo = 0`। সর্বোচ্চ সম্ভব gap দুই প্রান্তের ফারাক (এর বেশি দূরত্ব রাখা অসম্ভব), তাই `hi = stalls[-1] - stalls[0]`।
```text
mid = (lo + hi + 1) // 2
```
**উপরে** ঝোঁকানো mid — কারণ নিচে `lo = mid`। `+1` না দিলে `hi - lo == 1`-এ infinite loop। (maximize-এর স্বাক্ষর।)
```text
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!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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; অন্য কোথাও শুরু করলে কম গরু বসে।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Magnetic Force Between Two Balls** (