015 — Hotel Queries

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

• Original source: CSES Problem Set — "Hotel Queries"
• Platform: CSES — https://cses.fi/problemset/task/1143
• 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

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

পরপর সাজানো n-টা hotel আছে, প্রত্যেকটার একটা করে খালি ঘরের সংখ্যা (capacity)। তারপর m-টা group একে একে আসে; প্রতিটা group-এর একটা চাহিদা থাকে — কতগুলো ঘর লাগবে।

প্রতিটা group তার আগমনের ক্রমে বাঁ থেকে ডান খুঁজে নেয় প্রথম hotel-টা, যার capacity তার চাহিদার সমান বা বেশি। সেখানেই উঠে পড়ে, আর ওই hotel-এর capacity ঠিক সেই পরিমাণ কমে যায়। কোনো hotel না পেলে group-টার উত্তর 0।

প্রতিটা group-এর জন্য সে কোন hotel-এ (1-indexed) উঠল, সেটা বলো।

উদাহরণ

hotels (capacity): [3, 2, 4, 1]   (index 1..4)
groups (চাহিদা)  : [2, 1, 4, 1, 2]

উত্তর: 1 1 3 2 4

Input ও output

উদাহরণ

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

চেনা উদাহরণে বোঝা

ভাবো একটা সারিবদ্ধ গলিতে অনেকগুলো গেস্টহাউস, প্রত্যেকটার দরজায় বড় করে লেখা "এই block-এ সবচেয়ে বড় খালি ঘর: X জনের"। তুমি 4 জনের দল নিয়ে গলির মুখে দাঁড়িয়ে।

প্রথম অর্ধেক block-এর সাইনবোর্ড যদি বলে "সর্বোচ্চ 4", তুমি ডান অর্ধেকে তাকাও-ই না — সোজা বাঁ অর্ধেকে ঢুকে আবার একই প্রশ্ন করো, যতক্ষণ না একটামাত্র গেস্টহাউসে পৌঁছাও। পুরো গলি হাঁটতে হলো না, কয়েকটা সাইনবোর্ড দেখেই কাজ।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

এটা দাঁড়িয়ে আছে 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-এর জন্য।

ভেতরের যুক্তি

লুকানো logic হলো একটা descent invariant: root-এ থাকা max বলে দেয় "কোথাও একটা যোগ্য hotel আছে কি না"। যদি বাঁ subtree-র max চাহিদার সমান বা বেশি হয়, তবে প্রথম যোগ্য hotel নিশ্চিত বাঁ দিকে — তাই বাঁয়ে নামো। নাহলে ডানে নামো।

এই greedy choice সবসময় সঠিক, কারণ "প্রথম" মানে সবচেয়ে বাঁয়ের — আর বাঁ subtree-তে যদি একটাও যোগ্য থাকে, ডান subtree দেখার দরকারই নেই।

কী দিয়ে তথ্য রাখব

একটা max segment tree — flat array-এ heap layout-এ। প্রতিটা node তার segment-এর সর্বোচ্চ capacity রাখে। দরকার দুটো operation:

• find_first(need) — বাঁ থেকে প্রথম index যার stored capacity >= need, tree বেয়ে নেমে।
• ওই index-এ point update (capacity কমানো)।

এটি কেন উপযুক্ত

Prefix sums বা Fenwick এখানে চলবে না — এটা min/max-ধাঁচের query (আর Fenwick arbitrary range-এ max পারে না, যেমন ../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-এ পৌঁছানো যায়।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: প্রতিটা group-এর জন্য বাঁ থেকে ডান array scan করো, প্রথম capacity[j] >= need পেলেই থামো, capacity কমাও।

উদাহরণ

for each group need:
    for j in 1..n:
        if capacity[j] >= need:
            answer = j; capacity[j] -= need; break
    else:
        answer = 0

কোথায় বেশি কাজ হচ্ছে

প্রতিটা 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)-এ নামাতে হবে।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: প্রতিটা node-এ জমানো max-টাই বলে দেয় ওই subtree-তে আদৌ কোনো যোগ্য hotel আছে কি না। তাই "যোগ্য hotel খুঁজে পাওয়া যাবে কি" — এই প্রশ্নের উত্তর subtree-তে না ঢুকেই root-এর max দেখে দেওয়া যায়। বাঁ subtree-র max যথেষ্ট হলে উত্তর বাঁয়েই, কারণ আমরা সবচেয়ে বাঁয়ের যোগ্যটা চাই।

আরও কম কাজে সমাধান

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-এ মিশে যায়।

ভাবনার পরিবর্তন

মোচড়: "পুরো array-তে প্রথম যোগ্য খুঁজব" ভাবার বদলে ভাবো "max-গুলো guidepost — প্রতিটা node-এ শুধু একটা সিদ্ধান্ত: বাঁ subtree কি একটাও যোগ্য hotel ধরে আছে?" পুরো scan একটা single root-to-leaf descent-এ গুটিয়ে যায়।

ছবিতে বোঝা

[3, 2, 4, 1]-এর max tree (প্রতিটা node-এ [range] = stored max):

উদাহরণ

                 [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-এ ধাপে ধাপে

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। ✓

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

• 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 মিলিয়ে দেখা

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!।

খরচ ও সাধারণ ভুল

সময়

Build O(n) (প্রতিটা node একবার)। প্রতিটা group-এর booking একটা single root-to-leaf descent — O(log n)। m-টা group মিলিয়ে O(n + m log n)।

অতিরিক্ত জায়গা

O(n) — size 4n-এর flat tree array; group-প্রতি extra memory লাগে না।

যে ভুলগুলো এড়াতে হবে

• বাঁ child-এর max না দেখে root-এর max দেখে descend করা — তাহলে "প্রথম/leftmost" guarantee ভাঙে।
• Booking-এর পরে ফেরার পথে max repair ভুলে যাওয়া — পরের group stale max দেখে ভুল hotel-এ যাবে।
• book শুরুতে root max < need check বাদ দেওয়া — তাহলে যোগ্য hotel না থাকলেও tree ভুলভাবে নেমে যাবে।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: max segment tree (../segment-tree.md section 8-এর associative-combine generalization, combine = max) + binary descent (root থেকে এক-একটা সিদ্ধান্তে নামা, binary search-এর tree-version)। ../implementation.py-তে base tree-র runnable code।

পরের অনুশীলন

• Range Module / interval-based first-fit allocation — segment tree descent-এর variant।
• Online Stock Span (monotonic structure, ভিন্ন কিন্তু "first qualifying" চিন্তা) — https://leetcode.com/problems/online-stock-span/
• Sequentially Ordinal Rank Tracker / first-index queries — descent pattern-এর extension।

কৌশলটি মনে রাখুন

Walk down a max segment tree: node-এ জমানো max-কে guidepost বানিয়ে root থেকে নেমে "প্রথম index যেখানে capacity >= need" খুঁজে নেওয়া, এবং সেই same descent-এ point update মিশিয়ে দেওয়া — সব মিলিয়ে O(log n)। range query করে scan করার চেয়ে এটাই আসল tree-descent superpower।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "first/leftmost index satisfying a threshold, with updates" দেখলেই max segment tree descent মনে করবে। Root-এর max বলে যোগ্য কিছু আছে কি না; বাঁ child-এর max বলে কোন দিকে নামবে; leaf-এ পৌঁছে কাজ সেরে ফেরার পথে max repair করো। পুরো scan একটা root-to-leaf path-এ গুটিয়ে যায় — এটাই tree বেয়ে নামার আসল মানে।

---

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