Problem link ও উৎস
- **Original source:** CSES Problem Set — "Hotel Queries"
- **Platform:** CSES —
- **Topic:** segment tree and fenwick tree
- **Difficulty:** Hard
- **Pattern:** walk down a max segment tree (একটা tree বেয়ে নেমে প্রথম যোগ্য index খোঁজা)
- **Basic idea inherited from:** max segment tree, binary descent
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
পরপর সাজানো `n`-টা hotel আছে, প্রত্যেকটার একটা করে খালি ঘরের সংখ্যা (capacity)। তারপর `m`-টা group একে একে আসে; প্রতিটা group-এর একটা চাহিদা থাকে — কতগুলো ঘর লাগবে।
প্রতিটা group তার আগমনের ক্রমে **বাঁ থেকে ডান** খুঁজে নেয় **প্রথম** hotel-টা, যার capacity তার চাহিদার সমান বা বেশি। সেখানেই উঠে পড়ে, আর ওই hotel-এর capacity ঠিক সেই পরিমাণ কমে যায়। কোনো hotel না পেলে group-টার উত্তর `0`।
প্রতিটা group-এর জন্য সে কোন hotel-এ (1-indexed) উঠল, সেটা বলো।
```text
hotels (capacity): [3, 2, 4, 1] (index 1..4)
groups (চাহিদা) : [2, 1, 4, 1, 2]
উত্তর: 1 1 3 2 4
```
### Input ও output {#8-example-input-and-output}
```text
hotels = [3, 2, 4, 1]
groups = [2, 1, 4, 1, 2]
group 2 -> hotel 1 (cap 3->1)
group 1 -> hotel 1 (cap 1->0)
group 4 -> hotel 3 (cap 4->0)
group 1 -> hotel 2 (cap 2->1)
group 2 -> capacities [0,1,0,1]; maximum 1 < 2, তাই allocation নেই
আসলে: bookings-এর পর capacities = [0, 1, 0, 1]
group need=2 -> কোনো hotel-এ cap >= 2 নেই -> 0
উত্তর: 1 1 3 2 0
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা সারিবদ্ধ গলিতে অনেকগুলো গেস্টহাউস, প্রত্যেকটার দরজায় বড় করে লেখা "এই block-এ সবচেয়ে বড় খালি ঘর: X জনের"। তুমি 4 জনের দল নিয়ে গলির মুখে দাঁড়িয়ে।
প্রথম অর্ধেক block-এর সাইনবোর্ড যদি বলে "সর্বোচ্চ 4", তুমি ডান অর্ধেকে তাকাও-ই না — সোজা বাঁ অর্ধেকে ঢুকে আবার একই প্রশ্ন করো, যতক্ষণ না একটামাত্র গেস্টহাউসে পৌঁছাও। পুরো গলি হাঁটতে হলো না, কয়েকটা সাইনবোর্ড দেখেই কাজ।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা দাঁড়িয়ে আছে **max segment tree** আর **binary descent**-এর উপর।
- **Max segment tree** থেকে: প্রতিটা node একটা segment-এর *সর্বোচ্চ* capacity জমিয়ে রাখে (sum নয়)। `combine = max`, identity `-infinity` (বা এখানে `0`, যেহেতু capacity কখনো negative নয়)।
- **Binary descent** থেকে: পুরো tree query না করে, root থেকে নেমে প্রতি step-এ সিদ্ধান্ত নাও কোন child-এ যাবে — ঠিক binary search-এর মতো, কিন্তু array-র বদলে tree-র উপর।
দুটো মিললে: "প্রথম যোগ্য index" খুঁজে নেওয়া যায় O(log n)-এ, প্রতিটা group-এর জন্য।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো একটা **descent invariant**: root-এ থাকা max বলে দেয় "কোথাও একটা যোগ্য hotel আছে কি না"। যদি বাঁ subtree-র max চাহিদার সমান বা বেশি হয়, তবে প্রথম যোগ্য hotel নিশ্চিত বাঁ দিকে — তাই বাঁয়ে নামো। নাহলে ডানে নামো।
এই greedy choice সবসময় সঠিক, কারণ "প্রথম" মানে সবচেয়ে বাঁয়ের — আর বাঁ subtree-তে যদি একটাও যোগ্য থাকে, ডান subtree দেখার দরকারই নেই।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **max segment tree** — flat array-এ heap layout-এ। প্রতিটা node তার segment-এর সর্বোচ্চ capacity রাখে। দরকার দুটো operation:
- `find_first(need)` — বাঁ থেকে প্রথম index যার stored capacity `>= need`, tree বেয়ে নেমে।
- ওই index-এ `point update` (capacity কমানো)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Prefix sums বা Fenwick এখানে চলবে না — এটা **min/max-ধাঁচের** query (আর Fenwick arbitrary range-এ max পারে না, যেমন [../fenwick-tree.md](../fenwick-tree.md) section 8-এ বলা)। আবার পুরো range query করে scan করলে প্রতি group-এ O(n) লাগবে।
Max segment tree-র descent trick ঠিক এই "first index satisfying X" pattern-এর জন্য বানানো — node-এ জমানো max-টাই বলে দেয় কোন দিকে নামতে হবে, তাই পুরো subtree না ঘেঁটেই সঠিক hotel-এ পৌঁছানো যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা group-এর জন্য বাঁ থেকে ডান array scan করো, প্রথম `capacity[j] >= need` পেলেই থামো, capacity কমাও।
```text
for each group need:
for j in 1..n:
if capacity[j] >= need:
answer = j; capacity[j] -= need; break
else:
answer = 0
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা group সবচেয়ে খারাপ ক্ষেত্রে পুরো array (`n`-টা hotel) scan করে। `m`-টা group থাকলে মোট **O(n·m)** — `n, m` দুটোই 2·10^5 হলে প্রায় 4·10^10 operation, time limit exceeded। প্রতিটা "first index" খোঁজাকে O(log n)-এ নামাতে হবে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **প্রতিটা node-এ জমানো max-টাই বলে দেয় ওই subtree-তে আদৌ কোনো যোগ্য hotel আছে কি না**। তাই "যোগ্য hotel খুঁজে পাওয়া যাবে কি" — এই প্রশ্নের উত্তর subtree-তে না ঢুকেই root-এর max দেখে দেওয়া যায়। বাঁ subtree-র max যথেষ্ট হলে উত্তর বাঁয়েই, কারণ আমরা সবচেয়ে বাঁয়ের যোগ্যটা চাই।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
Max segment tree বানাও। প্রতিটা group-এর জন্য root থেকে নামো:
- leaf-এ পৌঁছালে — এটাই প্রথম যোগ্য hotel; capacity কমাও আর ফেরার পথে max repair করো।
- internal node-এ — বাঁ child-এর max `>= need` হলে বাঁয়ে নামো, নাহলে ডানে।
- root-এর max-ই যদি `< need` হয় — কোথাও যোগ্য hotel নেই, উত্তর 0।
Descent O(log n), capacity কমানোটাও সেই একই path-এ মিশে যায়।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "পুরো array-তে প্রথম যোগ্য খুঁজব" ভাবার বদলে ভাবো "max-গুলো guidepost — প্রতিটা node-এ শুধু একটা সিদ্ধান্ত: বাঁ subtree কি একটাও যোগ্য hotel ধরে আছে?" পুরো scan একটা single root-to-leaf descent-এ গুটিয়ে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
`[3, 2, 4, 1]`-এর max tree (প্রতিটা node-এ `[range] = stored max`):
```text
[1..4] = 4
/ \
[1..2] = 3 [3..4] = 4
/ \ / \
[1..1]=3 [2..2]=2 [3..3]=4 [4..4]=1
পড়ার নিয়ম: প্রতিটা internal node = max(বাঁ child, ডান child)
group need=4-এর descent:
[1..4] max=4 >= 4 -> নামো
বাঁ [1..2] max=3 < 4 -> বাঁয়ে নয়, ডানে যাও
ডান [3..4] max=4 >= 4 -> নামো
বাঁ [3..3] max=4 >= 4 -> বাঁয়ে নামো
[3..3] leaf -> hotel 3! capacity 4 - 4 = 0
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`hotels = [3, 2, 4, 1]`, group `need = 2` (প্রথম group):
1. `[1..4]` max = 4 `>= 2` → ভেতরে ঢোকা যায়, নামো।
2. বাঁ `[1..2]` max = 3 `>= 2` → বাঁয়ে নামো।
3. বাঁ `[1..1]` max = 3 `>= 2` → বাঁয়ে নামো।
4. `[1..1]` leaf → hotel 1। capacity `3 - 2 = 1`।
5. ফেরার পথে repair: `[1..2]` = max(1, 2) = 2, `[1..4]` = max(2, 4) = 4। উত্তর = 1। ✓
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class MaxSegmentTree:
"""RANGE MAX + 'find leftmost index with value >= need' descent।
combine = max, identity = 0 (capacity কখনো negative নয়)।
Flat list, heap layout: node i -> children 2i+1, 2i+2। Size 4n safe।
1-indexed hotels-কে ভেতরে 0-indexed হিসেবে রাখা হয়।"""
def __init__(self, data):
self.n = len(data)
self.tree = [0] * (4 * self.n)
if self.n:
self._build(data, 0, 0, self.n - 1)
def _build(self, data, node, lo, hi):
if lo == hi:
self.tree[node] = data[lo]
return
mid = (lo + hi) // 2
self._build(data, 2 * node + 1, lo, mid)
self._build(data, 2 * node + 2, mid + 1, hi)
self.tree[node] = max(self.tree[2 * node + 1], self.tree[2 * node + 2])
def book(self, need):
"""বাঁ থেকে প্রথম যে hotel-এর capacity >= need, সেখানে need কমিয়ে
তার 0-indexed position ফেরাও; কেউ যোগ্য না হলে -1।"""
if self.tree[0] < need: # root max-ই কম -> কেউ নেই
return -1
return self._descend(0, 0, self.n - 1, need)
def _descend(self, node, lo, hi, need):
if lo == hi: # leaf: এটাই প্রথম যোগ্য
self.tree[node] -= need # ঘর দখল
return lo
mid = (lo + hi) // 2
if self.tree[2 * node + 1] >= need: # বাঁ subtree-তে যোগ্য আছে
idx = self._descend(2 * node + 1, lo, mid, need)
else: # নাহলে ডানে
idx = self._descend(2 * node + 2, mid + 1, hi, need)
self.tree[node] = max(self.tree[2 * node + 1],
self.tree[2 * node + 2]) # ফেরার পথে repair
return idx
def brute(hotels, groups):
# obviously-correct reference: বাঁ-থেকে-ডান linear scan
cap = hotels[:]
out = []
for need in groups:
placed = 0 # 1-indexed; 0 = কোথাও না
for j in range(len(cap)):
if cap[j] >= need:
cap[j] -= need
placed = j + 1
break
out.append(placed)
return out
def solve(hotels, groups):
st = MaxSegmentTree(hotels)
out = []
for need in groups:
idx = st.book(need)
out.append(0 if idx == -1 else idx + 1) # 1-indexed answer, 0 = কোথাও না
return out
# ---- tests ----
hotels = [3, 2, 4, 1]
groups = [2, 1, 4, 1, 2]
assert solve(hotels, groups) == [1, 1, 3, 2, 0]
assert solve(hotels, groups) == brute(hotels, groups)
# single hotel
assert solve([5], [3, 2, 1]) == [1, 1, 0] # cap 5->2->0, শেষ group 1>0 fails
assert solve([5], [3, 3]) == [1, 0] # 5->2, পরে 2 < 3 -> 0
# কেউ-ই বসতে পারে না
assert solve([1, 1, 1], [2, 2]) == [0, 0]
# random fuzz: segment-tree descent vs brute
import random
random.seed(11)
for _ in range(300):
n = random.randint(1, 12)
m = random.randint(1, 15)
h = [random.randint(0, 9) for _ in range(n)]
g = [random.randint(1, 9) for _ in range(m)]
assert solve(h, g) == brute(h, g)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `MaxSegmentTree._build` — leaf-এ capacity বসায়, ফেরার পথে parent = max(দুই child)।
- `book(need)` — আগে root-এর max দেখে যোগ্য hotel আছে কি না নিশ্চিত করে; না থাকলে `-1`।
- `_descend` — leaf-এ পৌঁছে `need` কমায় (booking); internal node-এ বাঁ child-এর max `>= need` হলে বাঁয়ে, নাহলে ডানে; ফেরার পথে max repair।
- `brute` — হাতে-হাতে linear scan reference; descent-এর উত্তরের সাথে মেলাতে।
- `solve` — 0-indexed position-কে 1-indexed answer-এ বদলায় (`-1` → `0`)।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`hotels = [3,2,4,1]`-এ group 2 প্রথম hotel-এ বসে (cap 3→1), পরের group 1-ও hotel 1-এ (cap 1→0), group 4 descend করে hotel 3-এ (cap 4→0), group 1 hotel 2-তে, শেষ group 2-এর জন্য সব hotel-এর cap `< 2` — তাই 0। ফল `[1,1,3,2,0]`, brute-এর সাথে মেলে। single-hotel, কেউ-না-বসা, আর 300 random fuzz case-ও pass। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**Build O(n)** (প্রতিটা node একবার)। প্রতিটা group-এর booking একটা single root-to-leaf descent — **O(log n)**। `m`-টা group মিলিয়ে **O(n + m log n)**।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — size 4n-এর flat tree array; group-প্রতি extra memory লাগে না।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- বাঁ child-এর max না দেখে root-এর max দেখে descend করা — তাহলে "প্রথম/leftmost" guarantee ভাঙে।
- Booking-এর পরে ফেরার পথে max repair ভুলে যাওয়া — পরের group stale max দেখে ভুল hotel-এ যাবে।
- `book` শুরুতে root max `< need` check বাদ দেওয়া — তাহলে যোগ্য hotel না থাকলেও tree ভুলভাবে নেমে যাবে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: max segment tree ([../segment-tree.md](../segment-tree.md) section 8-এর associative-combine generalization, `combine = max`) + binary descent (root থেকে এক-একটা সিদ্ধান্তে নামা, binary search-এর tree-version)। [../implementation.py](../implementation.py)-তে base tree-র runnable code।
### পরের অনুশীলন {#22-similar-harder-problems}
- Range Module / interval-based first-fit allocation — segment tree descent-এর variant।
- Online Stock Span (monotonic structure, ভিন্ন কিন্তু "first qualifying" চিন্তা) —