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

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

```mermaid
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]-এ একটি জেতার চাল

```dsa
kind: array
title: "প্রথম pile ছোট করে XOR শূন্য করি"
steps:
  - label: "চালের আগে"
    values: [3, 4, 5]
    indices: false
    active: [0]
    note: "3 XOR 4 XOR 5 = 2; এই অবস্থায় জেতার চাল আছে।"
  - label: "প্রথম pile থেকে 2টি সরালাম"
    values: [1, 4, 5]
    indices: false
    active: [0]
    note: "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।

[ধারণায় ফিরি](concept-notes.md) · [সব সমস্যা ও অনুশীলন](problems/README.md) · [মূল উৎস](source-map.md)