Skip to content

004 — Ferris Wheel

Source

  • Original source: Classic greedy pairing of extremes
  • Platform: CSES Problem Set — https://cses.fi/problemset/ ("Ferris Wheel")
  • Topic: heap / priority queue (greedy warm-up)
  • Difficulty: Easy
  • Pattern: Greedy pairing of extremes
  • Basic idea inherited from: 02-arrays-and-strings two pointers — sort করে দুই প্রান্ত থেকে এগোনো

1. Problem in simple words

কতগুলো শিশুর ওজন দেওয়া আছে আর একটা সর্বোচ্চ সীমা x। প্রতিটা গন্ডোলায় বড়জোর দুজন বসতে পারে, আর তাদের মোট ওজন x-এর বেশি হতে পারবে না। প্রতিটা শিশুকে অবশ্যই নিতে হবে। সবচেয়ে কম সংখ্যক গন্ডোলা দিয়ে সবাইকে কীভাবে বসানো যায়, সেই সংখ্যাটা বের করো।

weights = [7, 2, 3, 9],  x = 10  ->  সবচেয়ে কম গন্ডোলা = 3

2. Which basic idea does this inherit from?

ভিত হলো sort + two pointers। ওজনগুলো সাজিয়ে নিলে এক প্রান্তে সবচেয়ে হালকা, অন্য প্রান্তে সবচেয়ে ভারী। দুই pointer একে অপরের দিকে এগিয়ে এসে জোড়া বানানোর চেষ্টা করে — এটাই 02-arrays-and-strings-এর classic two-pointer move, greedy-র পোশাক পরে।

3. What is the hidden math or logic?

লুকানো logic একটা greedy exchange argument: সবচেয়ে ভারী শিশুকে যদি কারো সাথে বসাতেই হয়, তবে সবচেয়ে হালকা যে শিশু তার সাথে fits, তাকেই সঙ্গী করা সবচেয়ে নিরাপদ। কারণ হালকাতম শিশু যদি ভারীতমের সাথে না আঁটে, তবে অন্য কারো সাথেও আঁটবে না — তাই ভারীতমকে একাই পাঠাও। এই locally-best জোড়া কখনো ভবিষ্যতের সম্ভাবনা নষ্ট করে না।

4. Which data structure is needed?

কোনো heap লাগেই না — একটা sorted array + দুটো pointerই যথেষ্ট। (এটা heap tracker-এ আছে কারণ pattern-টা — "বারবার দুই extreme নিয়ে decide করা" — heap + greedy চিন্তার সরলতম রূপ; এখানে sort একবার করলেই extreme-গুলো সস্তায় পাওয়া যায়, heap-এর দরকার পড়ে না।)

5. Why this data structure fits

একবার sort করলে দুই extreme — হালকাতম (বাঁ pointer) আর ভারীতম (ডান pointer) — O(1)-এ পাওয়া যায়। প্রতি step-এ একটা সিদ্ধান্ত (জোড়া হবে কি না) আর pointer সরানো — সব O(1)। তাই sort-এর O(n log n)-এর পরে পুরো জোড়া বানানো মাত্র O(n)। Evolving heap-এর overhead এখানে অপ্রয়োজনীয়।

6. Real-life analogy

মেলায় nagordola-র সামনে লম্বা লাইন। অপারেটর চান যত কম গন্ডোলা ঘোরাতে। তিনি সবচেয়ে মোটা বাচ্চাকে ডেকে দেখেন তার পাশে সবচেয়ে রোগা বাচ্চাটা বসানো যায় কিনা — গেলে দুজন একসাথে, না গেলে মোটা বাচ্চা একাই। বারবার এই "দুই প্রান্ত মিলিয়ে দেখা" — এটাই sort + two-pointer greedy।

7. Visual explanation

weights = [7, 2, 3, 9], x = 10। আগে sort: [2, 3, 7, 9]। বাঁ pointer lo, ডান pointer hi:

sorted: [2, 3, 7, 9]   x = 10
         ^lo      ^hi

step 1: lo=2, hi=9 -> 2+9=11 > 10 -> 9 একা যায়।  gondola++ (=1)  hi--
        [2, 3, 7, 9]
         ^lo   ^hi

step 2: lo=2, hi=7 -> 2+7=9 <= 10 -> জোড়া!  gondola++ (=2)  lo++  hi--
        [2, 3, 7, 9]
            ^lo^hi

step 3: lo=3, hi=3 -> একই শিশু (lo==hi) -> একা যায়।  gondola++ (=3)
        মোট গন্ডোলা = 3

8. Example input and output

Input : weights = [7, 2, 3, 9], x = 10  -> Output: 3
Input : weights = [1, 1, 1, 1], x = 2   -> Output: 2   (দুই-দুই জোড়া)
Input : weights = [5], x = 10            -> Output: 1   (একজনই)
Input : weights = [6, 6, 6], x = 10      -> Output: 3   (কেউ জোড়া হয় না)

9. Brute force thinking

প্রথম সরল চিন্তা: সব সম্ভাব্য জোড়া (pairing) চেষ্টা করে দেখো কোনটা সবচেয়ে কম গন্ডোলা দেয় — অর্থাৎ matching-এর সব combination ঘেঁটে দেখা।

[2,3,7,9] -> (2,3)(7,9)? (2,7)(3,9)? (2,9)(3,7)? ... সব try করো

10. Why brute force is slow

সব pairing combination চেষ্টা করা মানে exponential, এমনকি ভালো matching algorithm-এও অনেক বেশি কাজ। অথচ এখানে কাঠামোটা এত সরল যে greedy-ই optimal — সব combination ঘাঁটা নিখাদ অপচয়, যখন sort + one pass-ই যথেষ্ট।

11. Key observation

মূল observation: ভারীতম শিশুকে সবসময় হালকাতমের সাথে জোড়ার চেষ্টা করো। আঁটলে দুজন এক গন্ডোলায়, না আঁটলে ভারীতম একা — কারণ হালকাতমই যদি না আঁটে, কেউই আঁটবে না। এই একটা নিয়মই পুরো optimal উত্তর দেয়।

12. Optimized intuition

Sort করো। lo = 0, hi = n-1। যতক্ষণ lo <= hi: যদি w[lo] + w[hi] <= x হয়, দুজনকে জোড়া দাও (lo++); যেভাবেই হোক ভারীতম এই গন্ডোলায় যায় (hi--), গন্ডোলা গোনা একটা বাড়াও। lo > hi হলে থামো। Sort O(n log n), pass O(n)।

13. Thinking tweak

মোচড়: "দুজনকে কীভাবে জোড়া বানাব" না ভেবে ভাবো "সবচেয়ে ভারীটাকে নিয়ে কী করব — তার সাথে সবচেয়ে হালকাটা আঁটে কি?" যখনই কোনো problem বলে "দুই extreme জোড়া দিয়ে capacity/cost minimize করো", তখন sort + two-pointer greedy-র কথা মাথায় আসা উচিত — এটা heap + greedy ভাবনার বীজ।

14. Step-by-step dry run

Input weights = [7, 2, 3, 9], x = 10:

  1. sort → [2, 3, 7, 9]; lo=0 (2), hi=3 (9), gondola=0
  2. 2 + 9 = 11 > 10 → 9 একা → gondola=1, hi=2
  3. 2 + 7 = 9 ≤ 10 → জোড়া → gondola=2, lo=1, hi=1
  4. lo == hi (3) → একা → gondola=3, lo=2, hi=0
  5. lo > hi → থামো → return 3

15. Python solution

def min_gondolas(weights, x):
    weights = sorted(weights)          # হালকা থেকে ভারী সাজাও
    lo, hi = 0, len(weights) - 1       # দুই প্রান্তে দুই pointer
    gondolas = 0
    while lo <= hi:                    # এখনো বসানো বাকি শিশু আছে
        if weights[lo] + weights[hi] <= x:
            lo += 1                    # হালকাতম জোড়া হলো; ভেতরে এগোও
        hi -= 1                        # ভারীতম এই গন্ডোলায় গেল (একা বা জোড়ায়)
        gondolas += 1                  # একটা গন্ডোলা ব্যবহার হলো
    return gondolas

# ---- tests ----
assert min_gondolas([7, 2, 3, 9], 10) == 3
assert min_gondolas([1, 1, 1, 1], 2) == 2     # দুই-দুই জোড়া
assert min_gondolas([5], 10) == 1             # একজনই
assert min_gondolas([6, 6, 6], 10) == 3       # কেউ জোড়া হয় না
assert min_gondolas([], 10) == 0              # কেউ নেই
print("সব test pass!")

16. Line-by-line code explanation

  • weights = sorted(weights) — হালকা থেকে ভারী সাজানো; এক প্রান্তে min, অন্য প্রান্তে max।
  • lo, hi = 0, len(weights) - 1 — বাঁ pointer হালকাতমে, ডান pointer ভারীতমে।
  • while lo <= hi: — যতক্ষণ অন্তত একজন শিশু বাকি (lo == hi মানে একজনই বাকি)।
  • if weights[lo] + weights[hi] <= x: — হালকাতম আর ভারীতম একসাথে আঁটলে জোড়া; lo ভেতরে সরাও।
  • hi -= 1 — জোড়া হোক বা না হোক, ভারীতম এই গন্ডোলায় যায়, তাই hi সবসময় কমে।
  • gondolas += 1 — প্রতিবার একটা গন্ডোলা ব্যবহার হলো।

17. Output walkthrough

min_gondolas([7,2,3,9],10) section 14-এর dry run মেনে 3 দেয় — assert pass। [1,1,1,1],2 → প্রতিবার দুজন আঁটে → 2 গন্ডোলা। [5],10 → একজনই → 1। [6,6,6],10 → 6+6=12>10, কেউ জোড়া হয় না → 3 (প্রত্যেকে একা)। [] → loop চলে না → 0। পাঁচটা assert pass করার পরে print হয়: সব test pass!।

18. Time complexity

O(n log n) — sort-ই dominant খরচ; তারপর দুই pointer-এর single pass O(n)।

19. Space complexity

O(n) — sorted() একটা নতুন list বানায়। input list-কে in-place sort করলে (weights.sort()) extra space O(1)-এ নামানো যায়, কিন্তু caller-এর data না বদলানোই পরিষ্কার।

20. Common mistakes

  • sort না করেই two-pointer চালানো — তখন "দুই extreme" আসলে extreme না, greedy ভেঙে পড়ে।
  • lo == hi case ভুলে যাওয়া — শেষ একা শিশুকে গোনা না হলে উত্তর কম আসে।
  • জোড়া না আঁটলে hi না কমানো — তখন ভারীতম শিশু কখনো গন্ডোলায় ওঠে না, infinite loop।

21. Which basic problem this inherits from

ভিত্তি 02-arrays-and-strings-এর two-pointer move (sort করে দুই প্রান্ত থেকে এগোনো), আর patterns.md-র Pattern 6-এর বীজ ("repeatedly take the extreme")। এখানে heap লাগে না কারণ একবার sort করলেই extreme-গুলো স্থির — তবু চিন্তার ছাঁচটা heap + greedy-রই।

22. Similar harder problems

23. Pattern learned

Sort + two-pointer greedy: যখন "দুই extreme জোড়া দিয়ে সংখ্যা minimize/maximize করো" আর set একবার fix থাকে, তখন sort করে দুই প্রান্ত থেকে এগোও — heap লাগে না। কিন্তু যদি জোড়ার ফল আবার set-এ ফিরে আসে (যেমন Last Stone Weight), তখন এটাই heap + greedy হয়ে যায়।

24. Final summary

ভবিষ্যতের আমাকে: "দুজন করে capacity-তে জোড়া, কম গন্ডোলা চাই" = sort + two pointers (ভারীতমকে হালকাতমের সাথে জোড়ার চেষ্টা)। heap লাগে না যখন list স্থির; কিন্তু এই greedy ছাঁচটাই heap problem-গুলোর শিকড় — মনে রেখো, extreme থেকে শুরু করো।

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