Visualization Ideas — Hard Mixed CP Patterns¶
এই level-এর pattern গুলো বিমূর্ত — কিন্তু প্রতিটার পেছনে একটা পরিষ্কার ছবি লুকিয়ে আছে। ছবিটা ধরতে পারলে formula আর code নিজে থেকেই দাঁড়িয়ে যায়। নিচে প্রতিটা মূল idea-র আঁকার/animation কৌশল, আর শেষে 3টা worked ASCII example। খাতায় নিজে আঁকো — সেটাই আসল শিক্ষক।
প্রতি concept-এর visualization idea¶
1. Meet in the middle = সেতুর দুই পাড়¶
পুরো array-টাকে একটা নদীর দুই পাড় ভাবো — বাঁ পাড় আর ডান পাড়। প্রতি পাড় আলাদাভাবে তার সব subset-sum বানায় (2^(n/2) করে, পুরো 2^n নয়)। তারপর ডান পাড়ের list-টা sort করে রাখো; বাঁ পাড়ের প্রতিটা sum s-এর জন্য ডান পাড়ে T − s খোঁজো — এটাই সেতু পারাপার। Animation idea: মাঝখানে array কাটার একটা কাঁচি, দুই পাশে দুটো বাক্স ভরে উঠছে, তারপর বাঁ থেকে একটা তীর ডান পাশের sorted সারিতে গিয়ে binary search-এর জায়গা খুঁজছে।
2. Ternary search = পাহাড়ের চূড়ায় দুই লাঠি¶
একটা একচূড়া পাহাড় (unimodal: আগে শুধু ওঠে, পরে শুধু নামে) আঁকো। দুটো probe m1 আর m2 রাখো — দুটো লাঠি দিয়ে মাটি ছুঁয়ে উচ্চতা মাপার মতো। যেদিকের লাঠি নিচু, সেই দিকের প্রান্ত ছেঁটে ফেলো — চূড়া কখনো নিচু-লাঠির বাইরের অংশে থাকতে পারে না। Animation idea: প্রতি frame-এ দুটো লাঠি কাছাকাছি আসছে, range সংকুচিত হচ্ছে (প্রতিবার ~2/3 গুণ), শেষে চূড়ার উপর দুটো লাঠি মিলে যাচ্ছে।
3. Nim XOR = bit-কলামের ভারসাম্য-দাঁড়িপাল্লা¶
প্রতিটা pile-কে binary-তে লিখে কলাম সাজাও — যেন কয়েকটা সংখ্যা উপর-নিচে। প্রতিটা bit-কলামে কতগুলো 1 আছে গোনো। XOR = 0 মানে প্রতিটা কলামে 1-এর সংখ্যা জোড় — পুরো dāঁড়িপাল্লা ভারসাম্যে। তুমি যে চালই দাও, কোনো-না-কোনো কলামের জোড় ভাঙবে (XOR ≠ 0); opponent তখন আরেকটা চাল দিয়ে আবার সব কলাম জোড় করে দেয় — তোমার চালের আয়না-জবাব। Animation idea: প্রতি চালে একটা কলামের পাল্লা কাত হয়, পরের চালে আবার সমান।
pile bit3 bit2 bit1 bit0
3 = 0 0 1 1
4 = 1 0 0 0
5 = 1 0 1 1
────────────────────
1-গোনা: 2 0 2 2 ← সব জোড়? এখানে কলাম-3,1,0 জোড়, কিন্তু XOR=2≠0
4. Burnside necklace = ঘুরন্ত চাকতির আয়না-গণনা¶
পুঁতির necklace-কে একটা ঘুরন্ত চাকতি ভাবো। প্রতিটা rotation (0-ঘোরা, 1-ঘোরা, ...) একেকটা "আয়না"; সেই আয়নায় যে coloring গুলো অপরিবর্তিত থাকে (fixed), তাদের গোনো। Burnside বলে: distinct necklace = সব আয়নার fixed-সংখ্যার গড়। Animation idea: চাকতিটা ধাপে ধাপে ঘুরছে, প্রতি ধাপে যে রঙ-বিন্যাস হুবহু আগের মতো দেখায় তাকে হাইলাইট করা — identity ঘোরায় সব হাইলাইট, বড় ঘোরায় শুধু এক-রঙা গুলো।
●───● rotation k-তে পুঁতিগুলো gcd(k,n)-টা cycle-এ ভাঙে;
╱ ╲ প্রতি cycle এক রঙ হলে তবেই fixed
● ● (এটাই k^gcd(k,n)-এর উৎস)
╲ ╱
●───●
Worked ASCII example 1: meet in the middle (arr = [3, 1, 4, 2], T = 5)¶
কাঁচি মাঝখানে: বাঁ = [3, 1] ডান = [4, 2]
বাঁ-এর subset sums: {}→0 {3}→3 {1}→1 {3,1}→4 → L = [0, 3, 1, 4]
ডান-এর subset sums: {}→0 {4}→4 {2}→2 {4,2}→6 → R = [0, 4, 2, 6]
R sort করে: R = [0, 2, 4, 6]
বাঁ থেকে স্ক্যান (চাই T − s = 5 − s):
s = 0 → চাই 5 → R-এ নেই ✗
s = 3 → চাই 2 → R-এ আছে ✓ ({3} + {2} = 5)
s = 1 → চাই 4 → R-এ আছে ✓ ({1} + {4} = 5)
s = 4 → চাই 1 → R-এ নেই ✗
মোট 2টা subset-এর যোগফল 5: {3,2} আর {1,4} ✓
খরচ: প্রতি পাড়ে 2^(n/2) = 4, sort + binary search মিলিয়ে O(2^(n/2) · n/2) — 2^n-এর জগৎ থেকে নেমে আসা।
Worked ASCII example 2: ternary search (চূড়া x = 3, f = −(x−3)² + 5)¶
পাহাড়: ▲ (চূড়া x=3)
• •
╱ ╲
range [0, 10]: lo=0 ............... hi=10
step 1: m1 = 0 + 10/3 ≈ 3.33 f(m1) ≈ 4.89
m2 = 10 − 10/3 ≈ 6.67 f(m2) ≈ −8.45
f(m1) > f(m2) → চূড়া বাঁ দিকে → hi = m2 = 6.67
step 2: range [0, 6.67], আবার দুই probe... → range আরও সরু
...প্রতি step-এ range × ~2/3, কয়েক ডজন step-এ lo ≈ hi ≈ 3.0 ✓
লক্ষ করো: f(m1) > f(m2) দেখেই আমরা ডান প্রান্ত ছাঁটলাম — চূড়া নিচু-probe-এর বাইরে থাকতেই পারে না। এক-চূড়া না হলে এই যুক্তি ভাঙে, তাই আগে unimodality প্রমাণ করো।
Worked ASCII example 3: Burnside necklace (n = 4 পুঁতি, 2 রঙ, শুধু rotation)¶
4টা rotation: 0, 1, 2, 3 ঘোরা। fixed = অপরিবর্তিত coloring-এর সংখ্যা = 2^(cycle সংখ্যা)
rotation 0 (identity): প্রতি পুঁতি আলাদা cycle → 4 cycle → fixed = 2^4 = 16
rotation 1: সব পুঁতি এক বড় cycle → 1 cycle → fixed = 2^1 = 2
rotation 2: 2টা cycle (বিপরীত জোড়া) → 2 cycle → fixed = 2^2 = 4
rotation 3: সব পুঁতি এক cycle → 1 cycle → fixed = 2^1 = 2
distinct necklace = (16 + 2 + 4 + 2) / 4 = 24 / 4 = 6
হাতে মিলাও — 4-পুঁতির 2-রঙা distinct necklace ঠিক 6টা (সব সমান নয়, ঘোরালে এক হলে এক ধরা): RRRR, BBBB, RRRB, RRBB, RBRB, RBBB ✓। cycle সংখ্যা = gcd(rotation, n) — concept-notes.md-র k^gcd(r,n) সূত্রটা এখান থেকেই।
নিজে practice করার নিয়ম¶
- Meet in the middle-এর সেতু-ছবি ছোট array (n = 4) দিয়ে নিজে একবার পুরো এঁকে ফেলো — দুই পাড়, sort, তীর
- Ternary search-এ প্রতি step-এ
lo | m1 | m2 | hi | কোন দিক ছাঁটলাম— এই 5-কলামের টেবিল হাতে বানাও - Nim-এর bit-কলাম ছবিটা
[1, 2, 3](XOR = 0) দিয়ে আঁকো, তারপর নিজে এক চাল দিয়ে দেখো কীভাবে এক কলামের জোড় ভাঙে - Burnside-এর rotation-by-rotation cycle গোনা n = 3 আর n = 6-এও করো — gcd pattern নিজ চোখে ফুটে উঠবে