015 — Hotel Queries

Source

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

1. Problem in simple words

পরপর সাজানো 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

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 section 8-এ বলা)। আবার পুরো range query করে scan করলে প্রতি group-এ O(n) লাগবে।

Max segment tree-র descent trick ঠিক এই "first index satisfying X" pattern-এর জন্য বানানো — node-এ জমানো max-টাই বলে দেয় কোন দিকে নামতে হবে, তাই পুরো subtree না ঘেঁটেই সঠিক hotel-এ পৌঁছানো যায়।

6. Real-life analogy

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

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

7. Visual explanation

[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

8. Example input and 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 -> hotel 4? cap 1 < 2... hotel 2 cap 1 < 2... কোথাও নেই?

আসলে: bookings-এর পর capacities = [0, 1, 0, 1]
group need=2 -> কোনো hotel-এ cap >= 2 নেই -> 0

উত্তর: 1 1 3 2 0

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা 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

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-এ গুটিয়ে যায়।

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

15. Python solution

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

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

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 ভুলভাবে নেমে যাবে।

21. Which basic problem this inherits from

ভিত্তি: 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।

22. Similar harder problems

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

23. Pattern learned

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।

24. Final summary

ভবিষ্যতের আমাকে: "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।