019 — IPO¶

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

Problem link ও উৎস

Original source: Classic capital-bounded greedy with two heaps
Platform: LeetCode — https://leetcode.com/problems/ipo/
Topic: heap / priority queue
Difficulty: Hard
Pattern: Two heaps + greedy (affordable min-heap by capital → max-heap by profit)
Basic idea inherited from: 08 two heaps + greedy — unlock-by-threshold, তারপর সবচেয়ে লাভজনকটা নাও

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

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

তোমার হাতে শুরুতে w পরিমাণ capital আছে, আর কতগুলো project আছে। প্রতিটা project-এর দুটো সংখ্যা: শুরু করতে যত capital লাগবে (capital[i]), আর শেষ হলে যত profit যোগ হবে (profits[i])। তুমি বড়জোর k-টা project করতে পারবে, একটার পর একটা। কোনো project শুরু করতে হলে এই মুহূর্তে তোমার capital তার capital[i]-এর সমান বা বেশি হতে হবে; শেষ হলে profit তোমার capital-এ যোগ হয়। k-টা project শেষে সর্বোচ্চ কত capital হতে পারে, সেটা return করো।

উদাহরণ

w = 0, k = 2, profits = [1, 2, 3], capital = [0, 1, 1]  ->  4

Input ও output¶

উদাহরণ

Input : w=0, k=2, profits=[1,2,3], capital=[0,1,1]   -> Output: 4
Input : w=0, k=3, profits=[1,2,3], capital=[0,1,2]   -> Output: 6   (তিনটেই করা যায়)
Input : w=2, k=1, profits=[5],     capital=[5]        -> Output: 2   (afford হয় না)
Input : w=0, k=0, profits=[1,2],   capital=[0,0]      -> Output: 0   (k=0, কিছুই না)

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

ভাবো তুমি একজন investor। সামনে অনেক startup, প্রত্যেকের একটা "ঢোকার টিকিট দাম" (capital) আর একটা প্রত্যাশিত "return" (profit)। যেগুলোর টিকিট তোমার এখনকার টাকায় কেনা যায়, সেগুলো একটা টেবিলে রাখো — আর সেই টেবিল থেকে সবসময় সবচেয়ে বেশি return-এর টা আগে বেছে নাও। একটা ভালো deal শেষ হলে পকেট ভারী হয়, তখন আরও দামি টিকিটও নাগালে আসে। "সস্তা গুলো খোলো, লাভজনকটা নাও" — সেই দুই টেবিলই দুই heap।

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

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

ভিত 08-এর two heaps + greedy। একটা min-heap সব project-কে capital অনুযায়ী সাজিয়ে রাখে — যাতে "এখনকার টাকায় কোনগুলো affordable" সেটা সস্তায় বের করা যায়। আরেকটা max-heap সেই affordable project-গুলোর profit ধরে রাখে — যাতে তাদের মধ্যে সবচেয়ে লাভজনকটা চট করে নেওয়া যায়। এটা ঠিক 001-এর negate-for-max trick আর greedy "locally-best choice"-এরই বড় ভাই।

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

লুকানো logic একটা greedy exchange argument: প্রতি round-এ এই মুহূর্তে যেটা afford করতে পারো তাদের মধ্যে সবচেয়ে বেশি profit-দেওয়া project নেওয়া কখনো ভুল না। কারণ profit শুধু capital বাড়ায়, কমায় না — তাই বেশি profit আগে নিলে পরের round-এ affordable project-এর set কেবল বড় হয় (বা সমান থাকে), কখনো ছোট হয় না। তাই প্রতি step-এ সবচেয়ে লাভজনকটা নিলে শেষে capital maximize হয়।

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

দুটো heap। (1) by_capital — সব (এখনো না-করা) project-এর min-heap, key = required capital। (2) affordable — যেগুলোর capital বর্তমান w-এর নিচে নেমে এসেছে তাদের profit-এর max-heap (heapq min-heap বলে profit negate করে রাখা)।

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

প্রতি round-এ তোমার দুটো প্রশ্ন: "এই capital-এ কোন project গুলো খুলে গেল?" আর "তাদের মধ্যে সবচেয়ে লাভজনক কে?"। min-heap (capital দিয়ে sorted) প্রথমটার উত্তর দেয় — top সস্তা হলেই pop করে affordable-এ সরাও। max-heap (profit) দ্বিতীয়টার উত্তর O(log n)-এ দেয়। পুরো list বারবার scan বা re-sort করার দরকারই পড়ে না।

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

প্রথম সরল উপায়¶

প্রথম সরল চিন্তা: প্রতি round-এ পুরো project list scan করো, এখন afford করা যায় এমন সবগুলোর মধ্যে সবচেয়ে বেশি profit-এর টা খুঁজে নাও, করো, capital update করো, project-টা mark করে বাদ দাও। k বার এটা চালাও।

উদাহরণ

round-প্রতি: পুরো list scan -> affordable-দের মধ্যে max profit -> নাও
k round x n project = O(k * n) scan

কোথায় বেশি কাজ হচ্ছে¶

প্রতি round-এ পুরো list scan মানে O(n), আর round হয় k-টা — মোট O(k·n), যেখানে n বড় হলে এটা ভারী। অথচ আমাদের প্রতিবার সবগুলো দেখার দরকার নেই: একবার capital-sorted করে রাখলে নতুন কোন project খুলেছে সেটা incremental-ভাবে জানা যায়, আর max profit heap O(log n)-এ দেয়।

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

মূল observation: capital শুধু বাড়ে। তাই কোনো project একবার affordable হলে চিরকাল affordable থাকে — কখনো আবার "দামি" হয়ে যায় না। মানে capital-sorted list-এর ওপর একটা pointer শুধু সামনে এগোয়, পিছায় না। আর affordable হয়ে যাওয়া project-গুলোর মধ্যে শুধু সবচেয়ে লাভজনকটাই দরকার — পুরো order না।

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

সব project-কে capital দিয়ে একটা min-heap-এ ঢালো (বা শুধু sort করো)। k বার loop: বর্তমান w-এর <= capital-ওয়ালা সব project min-heap থেকে pop করে profit max-heap-এ ঢালো। max-heap খালি হলে আর কিছু afford হয় না — থামো। নাহলে সবচেয়ে বড় profit pop করে w-তে যোগ করো। প্রতিটা push/pop O(log n), মোট O(n log n)।

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

মোচড়: "project বাছাই" না ভেবে ভাবো "একটা unlock gate + একটা reward chest।" Capital-min-heap হলো gate — capital বাড়ার সাথে সাথে নতুন project খুলে দেয়; profit-max-heap হলো chest — খোলা জিনিসগুলোর মধ্যে সেরাটা দেয়। "একটা threshold পেরোলে নতুন option খোলে, খোলা option-দের মধ্যে best নাও" — এমন গন্ধ পেলেই এই two-heaps pattern মনে করবে।

ছবিতে বোঝা¶

w = 0, k = 2, profits = [1, 2, 3], capital = [0, 1, 1]:

উদাহরণ

by_capital (min-heap, key=capital):  (0,p1) (1,p2) (1,p3)
affordable (max-heap, key=profit):   খালি

round 1: w=0 -> capital<=0 খোলো -> (0,p1) সরাও
   affordable: [profit 1]
   সবচেয়ে লাভজনক pop -> +1 -> w = 1

round 2: w=1 -> capital<=1 খোলো -> (1,p2),(1,p3) সরাও
   affordable: [profit 3, profit 2]
   সবচেয়ে লাভজনক pop -> +3 -> w = 4

k=2 শেষ  ->  উত্তর 4

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

Input w=0, k=2, profits=[1,2,3], capital=[0,1,1]:

by_capital min-heap: (0,1), (1,2), (1,3); affordable max-heap: খালি; w = 0
round 1: top capital 0 ≤ 0 → pop (0,1), affordable-এ profit 1 ঢালো; পরের top capital 1 > 0 → থামো। affordable = {1}
সবচেয়ে বড় profit pop → 1 → w = 0 + 1 = 1
round 2: top capital 1 ≤ 1 → pop (1,2) ঢালো; আবার top 1 ≤ 1 → pop (1,3) ঢালো; by_capital খালি। affordable = {3, 2}
সবচেয়ে বড় profit pop → 3 → w = 1 + 3 = 4
k = 2 শেষ → return 4

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

Python¶

Python

import heapq

def find_maximized_capital(k, w, profits, capital):
    # সব project capital দিয়ে min-heap-এ: (required_capital, profit)
    by_capital = list(zip(capital, profits))
    heapq.heapify(by_capital)
    affordable = []                      # profit-এর max-heap (negate করা)

    for _ in range(k):
        # বর্তমান w-তে যা যা afford হয়, সব affordable-এ সরাও
        while by_capital and by_capital[0][0] <= w:
            cap, prof = heapq.heappop(by_capital)
            heapq.heappush(affordable, -prof)   # negate: max-heap
        if not affordable:               # কিছুই afford হয় না -> থামো
            break
        w += -heapq.heappop(affordable)  # সবচেয়ে লাভজনকটা নাও
    return w

# ---- tests ----
assert find_maximized_capital(2, 0, [1, 2, 3], [0, 1, 1]) == 4
assert find_maximized_capital(3, 0, [1, 2, 3], [0, 1, 2]) == 6   # তিনটেই
assert find_maximized_capital(1, 2, [5], [5]) == 2               # afford হয় না
assert find_maximized_capital(0, 0, [1, 2], [0, 0]) == 0         # k=0
assert find_maximized_capital(10, 0, [1, 2, 3], [0, 1, 1]) == 6  # k > project সংখ্যা
print("সব test pass!")

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

by_capital = list(zip(capital, profits)) — প্রতিটা project-কে (capital, profit) জোড়ায় বাঁধি; tuple বলে heap capital দিয়ে sort করবে।
heapq.heapify(by_capital) — O(n)-এ min-heap; top সবসময় সবচেয়ে সস্তা (কম capital) project।
affordable = [] — যেগুলো খুলে গেছে তাদের profit-এর max-heap (negate করে রাখা)।
while by_capital and by_capital[0][0] <= w: — top-এর required capital বর্তমান w-এর নিচে থাকলেই সেটা affordable; pop করে সরাও।
heapq.heappush(affordable, -prof) — profit negate করে push; এতে min-heap max-heap-এর মতো আচরণ করে।
if not affordable: break — হাতে capital দিয়ে কোনো project-ই শুরু করা যায় না → আর এগোনো অর্থহীন, থামো।
w += -heapq.heappop(affordable) — সবচেয়ে বড় profit pop করে (negate ফিরিয়ে) w-তে যোগ।

Output মিলিয়ে দেখা¶

find_maximized_capital(2, 0, [1,2,3], [0,1,1]) section 14-এর dry run মেনে 4 দেয় — assert pass। k=3, capital=[0,1,2]-এ তিনটেই ধাপে ধাপে খুলে যায় → 1+2+3 = 6। w=2, capital=[5]-এ একমাত্র project-এর টিকিট 5, afford হয় না → affordable খালি → 2-ই ফেরে। k=0-তে loop চলে না → 0। k=10 কিন্তু project 3-টা → শেষে by_capital ও affordable খালি হয়ে break → 6। সব assert pass-এর পরে print হয়: সব test pass!।

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

সময়¶

O(n log n) — প্রতিটা project বড়জোর একবার by_capital থেকে pop হয়ে affordable-এ push হয় (n-টা move, প্রতিটা O(log n)), আর বড়জোর k বার max profit pop। k ≤ n ধরলে মোট O(n log n)।

অতিরিক্ত জায়গা¶

O(n) — দুই heap মিলে সব project ধরে রাখে। প্রতিটা project ঠিক একবার এক heap থেকে অন্যটায় যায়, একসাথে duplicate থাকে না, তাই memory project-সংখ্যার সমানুপাতিক।

যে ভুলগুলো এড়াতে হবে¶

profit-কে max-heap না বানিয়ে সরাসরি heapq ব্যবহার — তখন তুমি সবচেয়ে কম profit-এর project নিচ্ছ, ভুল উত্তর।
প্রতি round-এ পুরো list আবার scan/sort করা — capital শুধু বাড়ে বলে pointer শুধু সামনে এগোয়; বারবার scan নিখাদ অপচয় (O(k·n))।
affordable খালি হলে break না দেওয়া — তখন খালি heap-এ pop করে IndexError, বা ভুলভাবে loop চালিয়ে যাওয়া।
capital আর profit-এর order tuple-এ উল্টে ফেলা — heap তখন profit দিয়ে sort করবে, unlock logic ভেঙে যাবে।

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

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

ভিত্তি 08-এর concept.md-র max-heap-via-negation আর patterns.md-র Pattern 6 (Heap + greedy combos) — "একটা greedy নিয়ম ঠিক করে কী নেবে, heap সেটা সস্তায় দেয়"। এখানে twist হলো দুটো heap: একটা unlock-এর জন্য (capital), একটা selection-এর জন্য (profit)। 001-এর single-heap greedy এর সরল রূপ।

পরের অনুশীলন¶

Find Median from Data Stream — https://leetcode.com/problems/find-median-from-data-stream/ (এই tracker-এর #18; two heaps, কিন্তু balance-এর জন্য)
Furthest Building You Can Reach — https://leetcode.com/problems/furthest-building-you-can-reach/ (#14; heap + greedy resource allocation)
Single-Threaded CPU — https://leetcode.com/problems/single-threaded-cpu/ (#13; threshold দিয়ে unlock, তারপর best নাও)

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

Two heaps + greedy (unlock + select): একটা min-heap একটা threshold (এখানে capital) দিয়ে option গুলো ধীরে ধীরে খুলে দেয়; খোলা option-গুলো একটা max-heap-এ যায়, যেখান থেকে greedy সবসময় best-টা তোলে। "threshold পেরোলে নতুন option খোলে, খোলাদের মধ্যে সেরা নাও" — এই pattern scheduling, IPO, resource problem-এ বারবার ফিরে আসে।

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

ভবিষ্যতের আমাকে: IPO = দুই heap। min-heap project-গুলোকে capital দিয়ে সাজিয়ে রাখে (unlock gate), max-heap খোলা project-গুলোর profit ধরে (reward chest)। k বার: যা যা afford হয় সব gate থেকে chest-এ সরাও, তারপর chest থেকে সবচেয়ে লাভজনকটা নাও। capital শুধু বাড়ে — তাই একটা greedy "সেরাটা আগে" নিরাপদ, আর pointer পিছায় না।

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