কনটেন্টে যান

004 — Ferris Wheel

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

Problem link ও উৎস

  • Original source: Classic greedy pairing of extremes
  • Platform: CSES Problem Set — https://cses.fi/problemset/task/1090 ("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 করে দুই প্রান্ত থেকে এগোনো

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

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

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

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

Input ও 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   (কেউ জোড়া হয় না)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

উদাহরণ
limit=10, weights=[2,3,7,9]
দুই gondola-য় সব pair করার তিনটি সম্ভাবনা:
(2,3)+(7,9): দ্বিতীয়টির sum 16, অবৈধ
(2,7)+(3,9): দ্বিতীয়টির sum 12, অবৈধ
(2,9)+(3,7): প্রথমটির sum 11, অবৈধ
তিন gondola: (2,7), (3), (9) -> বৈধ; minimum 3

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

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

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

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

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

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

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

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

ছবিতে বোঝা

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

ছোট input-এ ধাপে ধাপে

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

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

Python

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

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

  • 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 — প্রতিবার একটা গন্ডোলা ব্যবহার হলো।

Output মিলিয়ে দেখা

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

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

সময়

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

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

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

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

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

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

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

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

পরের অনুশীলন

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

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

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

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

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