Visualization Ideas — Greedy Math Tricks¶

Greedy-র প্রমাণ মুখে বলা কঠিন, কিন্তু এঁকে দেখানো সহজ। এখানে প্রতিটা pattern-এর জন্য আঁকার idea, আর শেষে 3টা worked ASCII example। খাতায় নিজে আঁকাটাই আসল অনুশীলন।

প্রতি concept-এর visualization idea¶

1. Exchange argument = টুকরো বদলের খেলা¶

দুটো সারি আঁকো — উপরে greedy-র solution, নিচে কোনো optimal solution। প্রথম যেখানে অমিল, সেই দুটো টুকরো তীর দিয়ে যুক্ত করে "swap" লেখো, আর পাশে দেখাও swap-এর পরে নিচের সারির মান কমেনি। কয়েক swap-এর পর দুই সারি এক — এটাই প্রমাণের ছবি।

2. Coin change fail = সিঁড়ি ভাঙা¶

6 ধাপের একটা সিঁড়ি আঁকো। Greedy লাফ দেয় 4 ধাপ, তারপর 1 + 1 — মোট 3 লাফ। পাশে আরেকটা সিঁড়িতে 3 + 3 — 2 লাফ। বড় লাফটা মাঝখানে এমন জায়গায় ফেলে যেখান থেকে বাকিটা খারাপভাবে ভাঙতে হয় — লোভের মাশুল চোখে দেখা যায়।

3. Furthest reach = টর্চের আলো¶

Array-টা রাস্তার ঘর; তুমি বাঁ থেকে হাঁটছ, হাতে টর্চ। প্রতিটা ঘরে পৌঁছে টর্চের আলো (furthest) বাড়তে পারে। কোনো ঘর আলোর বাইরে পড়লে — সেখানে যাওয়াই যায় না, খেলা শেষ। আলোর সীমানাটা প্রতি step-এ আঁকো।

4. Gas station = জ্বালানির গ্রাফ¶

x-অক্ষে station, y-অক্ষে tank-এর জ্বালানি — ভাঙা রেখা আঁকো। রেখা শূন্যের নিচে নামলেই লাল দাগ: "এই অংশের কেউ start হতে পারবে না", আর পরের station থেকে নতুন রেখা শুরু। মোট যোগফল ≥ 0 হলে শেষ reset-এর start-টাই উত্তর।

5. Candy two pass = দুই দিক থেকে ঢেউ¶

Rating গুলো bar chart-এ আঁকো। বাঁ থেকে একটা ঢেউ যায় — চড়াই পেলে candy বাড়ায়; ডান থেকে আরেকটা ঢেউ — উৎরাইয়ে বাড়ায়। প্রতি ঘরে দুই ঢেউয়ের বড়টা (max) রাখো। এক ঢেউয়ে কেন হয় না — ডানের তথ্য বাঁয়ের ঢেউ জানেই না, এই ছবিতেই পরিষ্কার।

6. Interval scheduling = timeline-এ রেখা¶

একটা timeline-এ interval গুলো আলাদা উচ্চতায় আঁকো। Earliest finish-টা সবুজ করো — তার ডান প্রান্ত সবচেয়ে বাঁয়ে, মানে ভবিষ্যতের জন্য সবচেয়ে বেশি জায়গা খালি রাখে। কোনো লম্বা interval-কে লাল করে দেখাও সে কতটা জায়গা গিলে ফেলত।

7. Median vs mean = দড়ি টানাটানি¶

সংখ্যারেখায় element গুলো dot; target-টা একটা পতাকা। পতাকা ডানে 1 ঘর সরালে বাঁয়ের প্রতিটা dot-এর দড়ি 1 করে লম্বা, ডানের গুলো 1 করে ছোট। দুই পাশে dot সমান হলে সরে লাভ-ক্ষতি কাটাকাটি — পতাকা median-এ স্থির। Outlier (100) টানলে mean নড়ে যায়, median নির্বিকার — এটাও আঁকো।

8. Reorganize string = চেয়ারে বসানো¶

n টা চেয়ার এক সারিতে। সবচেয়ে frequent character-এর লোকগুলোকে আগে এক চেয়ার ফাঁক রেখে বসাও (0, 2, 4...)। ফাঁকগুলোতে বাকিরা। কারো লোকসংখ্যা (n+1)//2 ছাড়ালে দুজন পাশাপাশি পড়বেই — ছবিতেই অসম্ভবতা ধরা পড়ে।

Worked ASCII example 1: Jump Game-এর furthest reach¶

nums  = [ 2 ,  3 ,  1 ,  1 ,  4 ]
index =   0    1    2    3    4

i=0: দাঁড়িয়ে 0-তে, টর্চ পৌঁছায় 0+2 = 2 পর্যন্ত
     [ 0 ]──আলো──▶ 2            furthest = 2

i=1: 1 ≤ 2 ✓, নতুন আলো 1+3 = 4
     [ 1 ]────আলো────▶ 4        furthest = 4

i=2: 2 ≤ 4 ✓, 2+1 = 3 < 4       furthest = 4 (বাড়ল না)
i=3, i=4: সবই আলোর ভেতরে ✓  →  True

ব্যর্থ case: nums = [3, 2, 1, 0, 4]
furthest: 3 → 3 → 3 → 3 → i=4 এ এসে 4 > 3 ✗ আলো শেষ → False

ছবির শিক্ষা: কোন পথে এলাম ভুলে যাও — শুধু আলোর সীমানা মনে রাখো।

Worked ASCII example 2: Minimum Platforms-এর event sweep¶

ট্রেন A: 900 ──────▶ 910
ট্রেন B: 940 ────────────────────▶ 1200
ট্রেন C: 950 ──────────────▶ 1120

events (sorted): 900   910   940   950   1120   1200
delta:            +1    −1    +1    +1     −1     −1
running:           1     0     1     2      1      0
                              ┌─────┐
platform গণনা:    ▁▁▁▁▁▁▁▁▁▁▁▁│ ২টা │▁▁▁▁▁▁▁▁
                              └─────┘
best = 2  →  950 থেকে 1120 পর্যন্ত B আর C একসাথে — 2 platform লাগবেই

ছবির শিক্ষা: ট্রেন আলাদা করে না ভেবে শুধু "+1/−1-এর স্রোত" ভাবো — এটাই sweep।

Worked ASCII example 3: median vs mean দড়ি টানাটানি (a = [1, 2, 100])¶

সংখ্যারেখা:  1   2                                   100
             ●   ●  ・・・・・・・・・・・・・・・・・・  ●

target = median (2):
  দড়ি:      |1−2| + |2−2| + |100−2|  =  1 + 0 + 98  =  99

target = mean (≈34):
  দড়ি:      |1−34| + |2−34| + |100−34| = 33 + 32 + 66 = 131  ✗

পতাকা 2 থেকে 3-এ সরালে কী হয়?
  বাঁয়ে 2টা dot (1, 2): প্রত্যেকের দড়ি +1  →  +2
  ডানে 1টা dot (100):  দড়ি −1            →  −1
  নিট পরিবর্তন: +1  →  সরলেই খারাপ! median-এই থাকো।

ছবির শিক্ষা: median-এর দুই পাশে dot-সংখ্যার ভারসাম্যই প্রমাণ — outlier কত দূরে সেটা median-এর কাছে অপ্রাসঙ্গিক।

নিজে আঁকার চ্যালেঞ্জ¶

Candy-র ratings = [1, 2, 2] — দুই ঢেউয়ের ছবি এঁকে দেখাও সমান rating-এ candy কমে যেতে পারে কেন বৈধ
Interval scheduling-এ "shortest interval first" fail করে এমন 3টা interval-এর timeline আঁকো
Coin set {1, 3, 4}-এ amount 6 ছাড়াও আর কোন amount-এ greedy হারে — সিঁড়ির ছবি এঁকে খুঁজে বের করো