কঠিন মিশ্র কৌশল — ছোট input-এ সম্পূর্ণ ছবি¶

Meet in the middle: [2,3,5,7], target 10¶

flowchart TD
    A["2,3,5,7"] --> L["বাঁ ভাগ: 2,3"]
    A --> R["ডান ভাগ: 5,7"]
    L --> LS["subset sums: 0,2,3,5"]
    R --> RS["subset sums: 0,5,7,12"]
    LS --> M["প্রতি বাঁ sum s-এর জন্য ডানে 10-s খুঁজি"]
    RS --> M

বাঁ sum s	ডানে চাই	পাওয়া যায়?	subset
0	10	না	—
2	8	না	—
3	7	হ্যাঁ	{3,7}
5	5	হ্যাঁ	{2,3,5}

Subset গুনতে হলে একই sum-এর frequency রাখতে হবে; set বানালে ভিন্ন subset-এর একই sum এক হয়ে যায়।

Nim: [3,4,5]-এ একটি জেতার চাল¶

প্রথম pile ছোট করে XOR শূন্য করি

চালের আগে
চিহ্নিত ঘর: 3
4
5
3 XOR 4 XOR 5 = 2; এই অবস্থায় জেতার চাল আছে।
প্রথম pile থেকে 2টি সরালাম
চিহ্নিত ঘর: 1
4
5
1 XOR 4 XOR 5 = 0; এই অবস্থাটি প্রতিপক্ষ পাবে।

Bit-এর হিসাব	প্রথম pile	দ্বিতীয় pile	তৃতীয় pile	XOR
চালের আগে	`011`	`100`	`101`	`010` = 2
চালের পরে	`001`	`100`	`101`	`000` = 0

প্রথম pile থেকে 2টি সরিয়ে প্রতিপক্ষকে XOR=0 অবস্থায় দিই। এই নিয়মে একটি pile থেকে যত খুশি positive সংখ্যক পাথর নেওয়া যায়, শেষ চালদাতা জেতে। Take-1-to-3 খেলায় এই pile-XOR সরাসরি বসানো যাবে না।

Grundy: এক heap থেকে 1 বা 2টি সরানো যায়¶

পাথর n	যাওয়া যায় এমন Grundy মান	mex: প্রথম অনুপস্থিত nonnegative মান
0	খালি	0
1	{0}	1
2	{1,0}	2
3	{2,1}	0
4	{0,2}	1

একটি state-এর Grundy 0 হলে এটি losing state; একাধিক স্বাধীন impartial normal-play game এক করলে Grundy মান XOR করি।

Burnside: 3টি পুঁতি, 2টি রং, শুধু rotation সমান¶

rotation	অপরিবর্তিত coloring সংখ্যা
0 ধাপ	2³ = 8
1 ধাপ	2: AAA, BBB
2 ধাপ	2: AAA, BBB

Distinct necklace (8+2+2)/3=4টি: AAA, BBB, AAB-এর ঘূর্ণনদল, ABB-এর ঘূর্ণনদল। এখানে reflection আলাদা operation হিসেবে ধরা হয়নি; bracelet হলে symmetry group বদলাবে।

Ternary search: একটি চূড়াওয়ালা function¶

ধরি f(x)=−(x−3)²+5, interval [0,9]। Function প্রথমে বাড়ে, তারপর কমে—একটি সর্বোচ্চ চূড়া।

interval	m1	f(m1)	m2	f(m2)	পরের interval
[0,9]	3	5	6	−4	[0,6]
[0,6]	2	4	4	4	[2,4]
[2,4]	8/3	44/9	10/3	44/9	[8/3,10/3]

প্রতিবার চূড়া রাখা interval ছোট হয়। এখানে symmetry-তে সমান মান পেলে মাঝের interval রাখছি। সাধারণ multimodal function-এ এই বাদ দেওয়া নিরাপদ নয়। Integer domain-এ interval ছোট হলে বাকি প্রতিটি candidate সরাসরি পরীক্ষা করো।

Expected value থেকে probability state¶

একটি fair coin-এর head indicator X: tail হলে 0, head হলে 1। তাই E[X]=0×0.5+1×0.5=0.5। দুটি fair toss-এর মোট head-এর expectation 1।

toss শেষ	0 head	1 head	2 head
0	1	0	0
1	0.5	0.5	0
2	0.25	0.5	0.25

প্রতিটি state-এর probability পরের ধাপে tail-এ একই head count ও head-এ এক বেশি count-এ ছড়ায়। প্রতিটি row-এর মোট 1 হওয়া sanity check।

ধারণায় ফিরি · সব সমস্যা ও অনুশীলন · মূল উৎস