# Math capstone — বিজ্ঞানমেলার প্রস্তুতি

একটি বিজ্ঞানমেলার জন্য খাবার, স্বেচ্ছাসেবক, মালপত্র ও সময়সূচির **একটি পরিকল্পনা রিপোর্ট** বানাবে। বড় সমস্যাটি ১২টি ছোট ধাপে ভাঙা আছে। একবারে সব algorithm লিখতে হবে না: একটি ধাপ শেষ করো, হাতে ফল মেলাও, সংশ্লিষ্ট test চালাও, তারপর পরের ধাপে যাও।

এই problem-এ Math-এর **Level 00–11 প্রত্যেকটির অন্তত একটি গুরুত্বপূর্ণ কৌশল** ব্যবহার হবে। এটি ১৫০টি problem-এর বিকল্প নয়। যেমন CRT শেখা মানে Miller–Rabin শেখা নয়; শেষের coverage table-এ কোনগুলো এখনও আলাদা করে করতে হবে তা পরিষ্কার দেওয়া আছে।

**সময় নিয়ে কাজ করো:** ভিত্তি ও হিসাব → পরিকল্পনা → advanced অংশ → একসঙ্গে report। আগে [Math chapter](../01-math-based-programming-fundamentals/README.md) ও [সমস্ত Math problem-এর তালিকা](../01-math-based-programming-fundamentals/roadmap.md) খুলে রাখো।

## ১. আগে কোন জিনিসগুলো পড়বে

Python-এর variable, `if`, `for`, function, list, tuple, dictionary, `//`, `%` ও exception জানা লাগবে। প্রতিটি row-তে আগে concept, তারপর ছোট problem, তারপর নিচের সংশ্লিষ্ট ধাপ।

| Level | আগে concept পড়বে | capstone-এর আগে ছোট অনুশীলন |
| --- | --- | --- |
| 00 — সংখ্যার ভিত্তি | [Digits ও parity](../01-math-based-programming-fundamentals/00-absolute-basics/concept-notes.md) | [002 — Sum of Digits](../01-math-based-programming-fundamentals/00-absolute-basics/problems/002-sum-of-digits.md), [001 — Even or Odd](../01-math-based-programming-fundamentals/00-absolute-basics/problems/001-even-or-odd.md) |
| 01 — ভাগ ও GCD | [GCD ও divisibility](../01-math-based-programming-fundamentals/01-divisibility-prime-gcd-lcm/concept-notes.md) | [018 — Euclidean GCD](../01-math-based-programming-fundamentals/01-divisibility-prime-gcd-lcm/problems/018-gcd-euclidean.md) |
| 02 — Modular arithmetic | [Remainder ও fast power](../01-math-based-programming-fundamentals/02-modular-arithmetic/concept-notes.md) | [031 — Large Number Mod](../01-math-based-programming-fundamentals/02-modular-arithmetic/problems/031-large-number-mod.md), [029 — Modular Exponentiation](../01-math-based-programming-fundamentals/02-modular-arithmetic/problems/029-modular-exponentiation.md) |
| 03 — Counting | [Combination](../01-math-based-programming-fundamentals/03-counting-combinatorics/concept-notes.md) | [041 — Combination](../01-math-based-programming-fundamentals/03-counting-combinatorics/problems/041-combination-basic.md) |
| 04 — Bits | [Mask ও bit operations](../01-math-based-programming-fundamentals/04-bit-manipulation/concept-notes.md) | [054 — Check ith Bit](../01-math-based-programming-fundamentals/04-bit-manipulation/problems/054-check-ith-bit.md), [062 — Subset Generation](../01-math-based-programming-fundamentals/04-bit-manipulation/problems/062-subset-generation-bits.md) |
| 05 — Prefix ও difference | [Range-এর হিসাব](../01-math-based-programming-fundamentals/05-prefix-difference-contribution/concept-notes.md) | [069 — Difference Array](../01-math-based-programming-fundamentals/05-prefix-difference-contribution/problems/069-difference-array.md), [068 — Range Sum](../01-math-based-programming-fundamentals/05-prefix-difference-contribution/problems/068-range-sum-query.md) |
| 06 — Sliding window | [Positive সংখ্যার window](../01-math-based-programming-fundamentals/06-two-pointers-sliding-window-math/concept-notes.md) | [087 — Minimum Size Subarray Sum](../01-math-based-programming-fundamentals/06-two-pointers-sliding-window-math/problems/087-minimum-size-subarray-sum.md) |
| 07 — Binary search | [উত্তরের উপর search](../01-math-based-programming-fundamentals/07-binary-search-on-answer/concept-notes.md) | [097 — Ship Packages](../01-math-based-programming-fundamentals/07-binary-search-on-answer/problems/097-ship-packages-d-days.md) |
| 08 — Greedy | [Exchange argument](../01-math-based-programming-fundamentals/08-greedy-math-tricks/concept-notes.md) | [107 — Interval Scheduling](../01-math-based-programming-fundamentals/08-greedy-math-tricks/problems/107-interval-scheduling.md) |
| 09 — Geometry | [Cross product ও hull](../01-math-based-programming-fundamentals/09-geometry-coordinate-math/concept-notes.md) | [116 — Orientation](../01-math-based-programming-fundamentals/09-geometry-coordinate-math/problems/116-orientation-three-points.md), [120 — Convex Hull](../01-math-based-programming-fundamentals/09-geometry-coordinate-math/problems/120-convex-hull-intro.md) |
| 10 — Advanced number theory | [Extended Euclid ও CRT](../01-math-based-programming-fundamentals/10-advanced-number-theory/concept-notes.md) | [125 — Extended Euclidean](../01-math-based-programming-fundamentals/10-advanced-number-theory/problems/125-extended-euclidean.md), [127 — CRT](../01-math-based-programming-fundamentals/10-advanced-number-theory/problems/127-crt-basic.md) |
| 11 — Mixed patterns | [অর্ধেক করে খোঁজা](../01-math-based-programming-fundamentals/11-hard-mixed-cp-patterns/concept-notes.md) | [139 — Meet in the Middle](../01-math-based-programming-fundamentals/11-hard-mixed-cp-patterns/problems/139-meet-in-the-middle.md) |

**Microsoft কোর্সের সঙ্গে সম্পর্ক — সহায়ক ভিত্তি:** ধাপ 07-এর binary search, Module 2 “Sorting and Searching Algorithms”-এর সঙ্গে সম্পর্কিত; ধাপ 08-এর greedy ও ধাপ 11-এর optimization কৌশল, Module 4–5-এর advanced problem-solving অনুশীলনে কাজে লাগে। এটি এই সাইটের নিজস্ব guided problem; Microsoft-এর official assignment নয়। Geometry ও advanced number theory-কে ওই কোর্সের আবশ্যিক পাঠ হিসেবে ধরা হয়নি। [Course mapping ও official syllabus-এর উৎস](../practice-map.md#course-map) দেখো।

## ২. সমস্যাটি ঠিক কী

তোমার দায়িত্ব মেলার coordinator-কে `build_report(data)` দিয়ে একটি Python dictionary দেওয়া। এতে থাকবে ১২টি ধাপের ফল এবং শেষে `can_dispatch`। নিচের নিয়মগুলোই এই অনুশীলনের চুক্তি।

1. কয়েক দিনের খাবারের চাহিদা আছে। পরে কিছু **পরপর দিনের** জন্য চাহিদা বাড়তে পারে। সব বৃদ্ধি যোগ হওয়ার পরেই packing, range sum, busy window ও shipping হিসাব করবে।
2. একটি দিনের খাবারের batch ভাঙা যাবে না। Batch-এর ক্রম বজায় রেখে সর্বোচ্চ `shipping_days` trip-এ সব পাঠাতে হবে। প্রতিটি trip-এর একই capacity; এর সর্বনিম্ন মান চাই। দিন ও trip এখানে একই একক: দিনে একটি trip।
3. Volunteer-দের দক্ষতা bitmask-এ দেওয়া। সব volunteer মিলিয়ে আবশ্যক দক্ষতাগুলো আছে কি না বলবে। আলাদাভাবে, `k` জনের সাধারণ team কতভাবে গঠন করা যায় সেটিও গুনবে। **ওই প্রতিটি team দক্ষতার শর্ত পূরণ করে—এমন দাবি করবে না।**
4. Session-এর শুরু ও শেষ সময় থেকে সর্বাধিক সংখ্যক সংঘর্ষহীন session বাছবে। একটি শেষ হওয়ার মুহূর্তেই অন্যটি শুরু করা যায়।
5. Booth-এর সব অবস্থান ঘিরে টানা convex boundary-এর ক্ষেত্রফলের দ্বিগুণ বের করবে। মাপটি শুধু জায়গার একটি হিসাব; জায়গার মধ্যে বাস্তবে booth বসবে কি না তার পরীক্ষা নয়।
6. কয়েকটি gate নির্দিষ্ট period পরপর খোলে। সব gate একই সময়ে খোলা থাকবে—এমন সবচেয়ে ছোট সময় চাই, যা `earliest_launch`-এর আগে নয়। না থাকলে `None`।
7. অতিরিক্ত equipment-এর প্রতিটি item সর্বোচ্চ একবার কেনা যাবে। Budget না ছাড়িয়ে যতটা সম্ভব টাকা খরচ হবে এমন একটি subset ফেরত দেবে। সব item সমান প্রয়োজনীয় ধরে নেওয়া হয়েছে; আলাদা utility/value নেই।
8. `can_dispatch = True` হবে কেবল যখন পুরো volunteer pool-এ আবশ্যক দক্ষতা আছে, booth boundary-এর area ধনাত্মক এবং gate-এর যৌথ সময় পাওয়া গেছে। অন্য হিসাবগুলো ওই সিদ্ধান্তের সঙ্গে রিপোর্টে থাকবে।

```mermaid
flowchart LR
    A["মেলার input"] --> B["চাহিদা ও গাড়ি"]
    A --> C["নিবন্ধন ও দল"]
    A --> D["সময় ও জায়গা"]
    A --> E["সরঞ্জাম"]
    B --> R["Planning report"]
    C --> R
    D --> R
    E --> R
```

| রিপোর্টের অংশ | ভেতরে যে কৌশল কাজে লাগবে |
| --- | --- |
| চাহিদা ও গাড়ি | Difference দিয়ে update → GCD দিয়ে packet size, prefix দিয়ে range total, window দিয়ে ব্যস্ত সময়, binary search দিয়ে capacity |
| নিবন্ধন ও দল | Digit summary, modular code, combination count, skill bitmask |
| সময় ও জায়গা | Greedy session selection, convex hull ও area, CRT দিয়ে gate-এর যৌথ সময় |
| সরঞ্জাম | Meet in the middle দিয়ে budget-এর মধ্যে subset |

### Input ও সীমা

সব index **0 থেকে**। Range `[l, r)`-তে `l` আছে, `r` নেই। নিচের সব field দিতে হবে; অজানা field বা সীমার বাইরের input হলে `ValueError`। `True`/`False` integer input হিসেবে গ্রহণ করা হবে না।

| Field | অর্থ ও সীমা |
| --- | --- |
| `batch_id` | 1–1000টি ASCII digit-এর string; শুরুতে zero থাকতে পারে |
| `volunteer_masks` | 1–2000টি integer; প্রত্যেকটি `0 <= mask < 2**20` |
| `required_mask` | আবশ্যক skill-এর mask; একই 20-bit সীমা |
| `team_size` | `0 <= k <= volunteer_count`; `k=0` হলে খালি team একটি |
| `base_demand` | 1–2000 দিনের চাহিদা; প্রতিটি `1..10**6` |
| `updates` | সর্বোচ্চ 2000টি `[l, r, extra]`; `0 <= l < r <= n`, `0 <= extra <= 10**6` |
| `queries` | সর্বোচ্চ 2000টি `[l, r]`; একই বৈধ range |
| `window_target` | `1..10**15`; window-এর যোগফল অন্তত এত চাই |
| `shipping_days` | `1..n`; সর্বোচ্চ অনুমোদিত trip |
| `sessions` | সর্বোচ্চ 2000টি `[start, finish]`; `0 <= start < finish <= 10**6` |
| `booths` | সর্বোচ্চ 2000টি `[x, y]`; integer coordinate `-10**6..10**6`; duplicate চলবে |
| `gate_cycles` | সর্বোচ্চ 8টি `[remainder, period]`; `1 <= period <= 1000`, `0 <= remainder < period` |
| `earliest_launch` | `0..10**12`; সমস্ত gate-এর জন্য একই ঘড়ির সময় |
| `equipment_costs` | সর্বোচ্চ 32টি integer cost; `0..10**9` |
| `budget` | `0..10**9` |

সব list-এর জায়গায় tuple-ও গ্রহণযোগ্য। `updates`, `queries`, `sessions`, `booths`, `gate_cycles`, `equipment_costs` খালি হতে পারে। Final demand ধনাত্মক থাকে; sliding window-এর যুক্তির জন্য এই শর্তটি জরুরি। `MOD = 1_000_000_007` ব্যবহার হবে registration code ও team count-এ।

## ৩. একটি ছোট উদাহরণ পুরো হাতে চালাও

```python
data = {
    "batch_id": "1204",
    "volunteer_masks": [1, 2, 3, 4], "required_mask": 7, "team_size": 2,
    "base_demand": [2, 4, 2, 6], "updates": [[1, 3, 2]],
    "queries": [[0, 2], [1, 4]], "window_target": 10, "shipping_days": 2,
    "sessions": [[0, 2], [1, 3], [2, 4], [4, 5]],
    "booths": [[0, 0], [4, 0], [4, 3], [0, 3], [2, 1]],
    "gate_cycles": [[2, 4], [4, 6]], "earliest_launch": 11,
    "equipment_costs": [6, 4, 7, 3], "budget": 11,
}
```

```dsa
kind: array
title: "Range update থেকে shipping plan"
steps:
  - label: "আগের চাহিদা"
    values: [2, 4, 2, 6]
    active: [1, 2]
    note: "[1,3) range-এর দুই দিনে 2 করে যোগ হবে।"
  - label: "সব update-এর পরে"
    values: [2, 6, 4, 6]
    note: "মোট 18; সমান packet-এর সবচেয়ে বড় মাপ gcd = 2।"
  - label: "Trip 1"
    values: [2, 6]
    note: "Load 8; পরের batch 4 যোগ করলে capacity 10 ছাড়াবে।"
  - label: "Trip 2"
    values: [4, 6]
    note: "Load 10; দুই trip-এ সব পাঠানো গেল।"
```

| ধাপ | হাতে হিসাব | প্রত্যাশিত ফল |
| --- | --- | --- |
| 00 | `1+2+0+4=7`; শেষ digit `4` | 4 digit, sum 7, even |
| 01 | `gcd(2,6,4,6)` | packet size `2` |
| 02 | `1204**4 = 2_101_386_547_456`; তারপর `% MOD` | `386532749` |
| 03 | 4 জন থেকে 2 জন: `4*3/2` | `6` team |
| 04 | `001 OR 010 OR 011 OR 100 = 111` | required `111` পূরণ |
| 05 | update-এর পরে `[2,6,4,6]`; `[0,2)` ও `[1,4)` | total `18`; query `[8,16]` |
| 06 | `[6,4]` অথবা `[4,6]`-এর যোগ 10; এক দিনে সর্বোচ্চ 6 | length `2` |
| 07 | capacity 9-এ `[2,6]`, `[4]`, `[6]`: তিন trip; 10-এ দুই trip | capacity `10` |
| 08 | session 0 → 2 → 3: `[0,2)`, `[2,4)`, `[4,5)` | indices `[0,2,3]` |
| 09 | বাইরের rectangle `4*3=12`; `(2,1)` ভিতরে | doubled area `24` |
| 10 | `t % 4=2`, `t % 6=4` মেলে `10,22,34...`; `t>=11` | launch `22` |
| 11 | cost 4 ও 7 নিলে budget 11 পুরো ব্যবহার | spent `11`, indices `[1,2]` |

উপরের input-এর report:

```python
{
    "badge": {"digits": 4, "digit_sum": 7, "even": True},
    "packing_unit": 2,
    "registration_code": 386532749,
    "team_count_mod": 6,
    "skills": {"available_mask": 7, "missing_mask": 0, "ready": True},
    "demand": {"daily": [2, 6, 4, 6], "total": 18, "range_totals": [8, 16]},
    "shortest_busy_window": 2,
    "delivery_capacity": 10,
    "session_indices": [0, 2, 3],
    "booth_area2": 24,
    "launch_time": 22,
    "equipment": {"spent": 11, "remaining": 0, "indices": [1, 2]},
    "can_dispatch": True,
}
```

Equipment-এর সমান ভালো একাধিক subset থাকলে **যেকোনো একটি** গ্রহণযোগ্য। এই উদাহরণে আরেকটি বৈধ subset `[0,1]` নয়: তার খরচ 10, অথচ 11 পাওয়া যায়। Integer index-কে cost ভেবে ফেলবে না।

## ৪. Guided milestones — নিজে লিখে মিলিয়ে দেখো

নিচের function নামগুলো reference implementation ও unit test-এ একই রাখা হয়েছে। প্রথমে function-এর চুক্তি বোঝো, তারপর উদাহরণ কাগজে চালাও। `build_report` শেষে লিখবে; dependency থাকার কারণে **ধাপ 05-এর final demand দিয়ে ধাপ 01, 06, 07 চালাবে**। পাঠের level-order ও program-এর execution-order এক হওয়া বাধ্যতামূলক নয়।

### ধাপ 00 — Badge-এর সহজ হিসাব

**লিখবে:** `badge_summary(batch_id)` → `digits`, `digit_sum`, `even`। পুরো string-কে integer বানাবে না; leading zero-ও digit হিসেবে গণনা হবে।

**Invariant:** প্রথম `i`টি character পড়ার পরে running sum ওই `i`টি digit-এর যোগফল। Parity শুধু শেষ digit নির্ধারণ করে।

**Hint:** প্রতিটি ASCII digit-এর মান `ord(char) - ord("0")`।

**Checkpoint:** `"007"` → 3 digit, sum 7, odd; `"0000"` → 4 digit, sum 0, even। Test: `test_badges_zeroes_and_large_decimal`।

### ধাপ 01 — সর্বোচ্চ সমান packet size

**লিখবে:** `packing_unit(demand)` → এমন সবচেয়ে বড় positive integer যা প্রতিটি দিনের final demand-কে নিঃশেষে ভাগ করে।

**Invariant:** প্রথম `i`টি demand প্রক্রিয়া করার পর accumulator তাদের সবার GCD। নতুন সংখ্যার সঙ্গে GCD নিলে আগের কোনো divisibility শর্ত হারায় না।

**Hint:** `gcd(gcd(a,b),c)` ব্যবহার করো। শুধু সবচেয়ে ছোট সংখ্যাটিকে উত্তর ধরে নিও না।

**Checkpoint:** `[12,18,30]` → `6`; `[2,6,4,6]` → `2`। Test: `test_counts_and_masks`।

### ধাপ 02 — বড় batch ID-এর reproducible code

**লিখবে:** `registration_code(batch_id, volunteer_count)` → `int(batch_id)**volunteer_count % MOD`-এর সমান ফল, বড় integer power না বানিয়ে। এটি authentication, encryption বা collision-free identifier নয়।

**Invariant:** digit পড়ার পরে `remainder` এখন পর্যন্ত পড়া সংখ্যার `% MOD`; exponent loop-এ `result * base**remaining_exponent` মূল power-এর সমান modulo `MOD`।

**Hint:** নতুন digit এলে `remainder = (10 * remainder + digit) % MOD`। Exponent odd হলে `result`-এ base গুণ করো, প্রতিবার base square এবং exponent অর্ধেক করো।

**Checkpoint:** `"1204"`, 4 জন → `386532749`; 1000-digit ID দিয়েও কাজ করতে হবে। Test: `test_badges_zeroes_and_large_decimal` ও পুরো example।

### ধাপ 03 — কতটি team বানানো সম্ভব

**লিখবে:** `team_count(n, k)` → unordered `k`-person subset-এর সংখ্যা `% MOD`।

**Invariant:** `i` ধাপের পরে count হলো `C(n-k+i, i)`। তাই `count * (n-k+i) // i` প্রতিবার পূর্ণসংখ্যা।

**Hint:** প্রথমে `k=min(k,n-k)`। এই input সীমায় Python-এর exact integer দিয়ে পুরো combination হিসাব করে **শেষে** modulo নাও। মাঝখানে modulo নিয়ে সাধারণ `// i` করলে ফল নষ্ট হবে।

**Checkpoint:** `C(4,2)=6`, `C(n,0)=1`, `C(n,n)=1`। Test: `test_counts_and_masks`।

### ধাপ 04 — দক্ষতার union

**লিখবে:** `skills_report(masks, required)` → `available_mask`, `missing_mask`, `ready`। যেমন bit 0 = registration, bit 1 = logistics, bit 2 = first aid।

**Invariant:** এখন পর্যন্ত দেখা volunteer-দের সব skill-এর union হলো `available`। একই skill দ্বিতীয়বার এলেও OR সেটি মুছে দেয় না।

**Hint:** `available |= mask`; missing skill হলো `required & ~available`। এখানে XOR ব্যবহার করলে দুইজনের common skill ভুল করে বাদ যাবে।

**Checkpoint:** `[1,2]`, required `7` → missing `4`, ready `False`। Test: `test_counts_and_masks`। `team_count=6` মানে 6টি skill-complete team নয়—এই পার্থক্য নিজের ভাষায় বোলো।

### ধাপ 05 — চাহিদা বাড়ানো ও range total

**লিখবে:** `demand_report(base, updates, queries)` → `daily`, `total`, `range_totals`। Input list বদলাবে না।

**Invariant:** difference array-এর prefix sum হলো বর্তমান দিনে সক্রিয় সমস্ত বাড়তি চাহিদা; `prefix[i]` হলো final demand-এর প্রথম `i` দিনের মোট।

**Hint:** `[l,r)` update-এ `difference[l] += extra`, `difference[r] -= extra`। Sentinel-এর জন্য `n+1` ঘর লাগবে। Query-এর ফল `prefix[r]-prefix[l]`।

**Checkpoint:** example-এ difference `[0,2,0,-2,0]`, final `[2,6,4,6]`, prefix `[0,2,8,12,18]`। Test: `test_difference_and_prefix_against_direct_updates`।

### ধাপ 06 — সবচেয়ে ছোট ব্যস্ত সময়

**লিখবে:** `shortest_busy_window(demand, target)` → যোগফল অন্তত target এমন সবচেয়ে ছোট **পরপর** দিনের সংখ্যা; অসম্ভব হলে `0`।

**Invariant:** `running` সবসময় window `[left,right]`-এর যোগফল। শর্ত পূরণ হলে বাম দিক ছোট করতে করতে ওই right-এর সবচেয়ে ছোট বৈধ window পরীক্ষা হয়।

**Hint:** right এক ঘর বাড়াও; যোগফল target ছুঁলেই `while` দিয়ে left সরাও। `if` দিলে একবারের বেশি shrink হবে না। ধনাত্মক demand থাকার কারণেই এই যুক্তি চলে।

**Checkpoint:** `[2,6,4,6]`, target 10 → `2`; target 19 → `0`; target 1 → `1`। Test: `test_windows_against_all_subarrays`। Negative চাহিদা অনুমতি দিলে এই algorithm যথেষ্ট নয়।

### ধাপ 07 — গাড়ির সর্বনিম্ন capacity

**লিখবে:** `delivery_capacity(demand, days)` → সব batch ক্রম বজায় রেখে সর্বোচ্চ days trip-এ পাঠানোর minimum capacity।

**Invariant:** `low..high`-এর মধ্যে optimal capacity আছে। `feasible(C)=True` হলে বড় capacity-ও feasible। একটি capacity-তে যতক্ষণ সম্ভব একই trip ভরলে প্রয়োজনীয় trip-এর সংখ্যা সর্বনিম্ন হয়।

**Hint:** lower bound `max(demand)`, upper bound `sum(demand)`। Middle capacity-তে পরের batch না ধরলে নতুন trip। Feasible হলে `high=middle`, নইলে `low=middle+1`।

**Checkpoint:** example-এ capacity 9 ব্যর্থ, 10 সফল; days 1 হলে উত্তর 18, days 4 হলে 6। Test: `test_capacity_against_all_partitions`।

### ধাপ 08 — সবচেয়ে বেশি session রাখো

**লিখবে:** `choose_sessions(intervals)` → original zero-based indices, নির্বাচিত সময়ের ক্রমে। Finish time, তারপর start, তারপর original index দিয়ে sort করবে, যাতে tie-তেও ফল স্থির থাকে।

**Invariant:** নির্বাচিত session-গুলো সংঘর্ষহীন; একই সংখ্যক session নেওয়া অন্য কোনো feasible prefix-এর চেয়ে আমাদের শেষ সময় পরে নয়।

**Hint:** সবচেয়ে আগে শেষ হওয়া compatible session নাও। কোনো optimal solution-এর প্রথম session-কে এর বদলে বসালে পরের session-এর সুযোগ কমে না—এটাই exchange argument।

**Checkpoint:** `[0,2)`, `[1,3)`, `[2,4)`, `[4,5)` → indices `[0,2,3]`। Test: `test_greedy_sessions_against_all_subsets`। সবচেয়ে ছোট duration বেছে নেওয়া একই নিয়ম নয়।

### ধাপ 09 — booth-গুলো ঘিরে boundary

**লিখবে:** `booth_area2(points)` → convex hull-এর দ্বিগুণ area। Floating-point distance বা angle দরকার নেই।

**Invariant:** lower/upper chain-এর consecutive তিন point বাঁ দিকে ঘুরবে; clockwise turn অথবা collinear middle point boundary থেকে বাদ যায়।

**Hint:** unique point sort করো; cross product `<=0` হলে শেষ point pop করো। Lower ও upper chain মেলাও। Shoelace: পরপর point `(x1,y1),(x2,y2)` থেকে `x1*y2-y1*x2` যোগ করে absolute value নাও।

**Checkpoint:** example rectangle-এর doubled area 24; `(0,0),(1,0),(0,1)` → 1; সব point একই সরলরেখায় → 0। Test: `test_geometry_known_shapes_and_degeneracy`। Duplicate ও negative coordinate বাদ দিও না।

### ধাপ 10 — সব gate কখন একসঙ্গে খুলবে

**লিখবে:** `synchronized_launch(congruences, earliest)` → প্রথম সময় `t>=earliest`, অথবা `None`। একটি pair `[r,m]` মানে `t % m == r`। Period-গুলো coprime ধরে নেওয়া যাবে না।

**Invariant:** প্রতিটি merge-এর পরে সব পুরোনো শর্তের সমাধান ঠিক `t ≡ residue (mod period)`; period হলো merged period-গুলোর LCM।

**Hint:** আগের solution `a mod M`, নতুনটি `b mod m`। `g=gcd(M,m)` যদি `b-a`-কে ভাগ না করে, কোনো solution নেই। নইলে `M*k ≡ b-a (mod m)`-কে `g` দিয়ে ভাগ করে extended Euclid-এর coefficient দিয়ে `k` বের করো। নতুন period `M*(m/g)`। শেষে প্রয়োজনমতো পুরো period যোগ করে earliest-এ পৌঁছাও।

**Checkpoint:** `[2,4]` ও `[4,6]` → `10 mod 12`, earliest 11 → 22। `[0,2]` ও `[1,2]` একসঙ্গে অসম্ভব। খালি gate list হলে earliest-ই উত্তর। Test: `test_generalized_crt_against_exhaustive_search`।

### ধাপ 11 — budget পুরো কাজে লাগাও

**লিখবে:** `equipment_budget(costs, budget)` → `spent`, `remaining`, `indices`। একই item দুবার নেওয়া যাবে না।

**Invariant:** প্রতিটি অর্ধেকের generated list-এ ওই অর্ধেকের সব budget-এর মধ্যে থাকা subset-এর sum ও mask থাকে। প্রতিটি left sum-এর জন্য right থেকে সবচেয়ে বড় compatible sum নিলেই ওই left-এর সেরা জোড়া পাওয়া যায়।

**Hint:** সর্বোচ্চ 32 item-কে দুই ভাগে ভাগ করো। এক ভাগের sum sort করো; অন্য ভাগের প্রতিটি sum `s`-এর জন্য `budget-s`-এর upper bound খোঁজো। Mask থেকে original index ফেরত আনো। `2**32` subset সরাসরি পরীক্ষা করা এই সমস্যার উদ্দেশ্য নয়।

**Checkpoint:** `[6,4,7,3]`, budget 11 → spent 11; খালি input বা budget 0-এ empty subset গ্রহণযোগ্য। Test: `test_equipment_against_exhaustive_subsets`। শুধু spent মেলালে হবে না—indices unique কি না এবং তাদের cost-এর sum মেলে কি না দেখবে।

## ৫. সব অংশ একসঙ্গে জুড়বে যেভাবে

`build_report(data)` প্রথমে input যাচাই করবে। এরপর final demand একবারই বানাবে। সেই ফল GCD, busy window ও capacity function-এ পাঠাবে। বাকি অংশগুলো তাদের প্রয়োজনীয় data পাবে। শেষে উপরের example-এর মতো dictionary ফিরবে। Caller-এর input বদলানো যাবে না।

শুধু function call করা যথেষ্ট নয়—চুক্তি ঠিক আছে কি না খেয়াল করো:

- `None` launch মানে অসম্ভব; `0` launch কিন্তু একটি বৈধ সময় হতে পারে। তাই `launch is not None` দিয়ে পরীক্ষা করবে।
- `booth_area2=0` হলে জায়গা degenerate; এই model-এ dispatch false।
- সমস্ত required skill মিলে গেলেও প্রতিটি ছোট team সেই skill বহন করে না। Report-এ এই দুই metric আলাদা।
- Registration code security token নয়। Modulo-তে collision হতে পারে।
- Gate সময়, session সময় ও demand-এর day index তিনটি আলাদা input ক্ষেত্র; তাদের মধ্যে কোনো গোপন conversion ধরা হয়নি।

## ৬. Unit test, reference solution ও অনুশীলনের পদ্ধতি

প্রথমবার solution না দেখে নিজের `practice/math_lab.py` লিখতে পারো। Download করা test file একই `practice/` folder-এ রাখো; terminal খুলবে তার **parent folder**-এ। এই lab-এ Python 3.10+ এবং standard library যথেষ্ট; কোনো package install লাগে না।

- [Unit test ডাউনলোড](../practice/test_math_lab.py){ download }
- [সম্পূর্ণ runnable reference solution](../practice/math_lab.py){ download }

```bash
python -m unittest discover -s practice -p 'test_math_lab.py' -v
python practice/math_lab.py
```

দ্বিতীয় command হাতে-চালানো example-এর JSON report print করবে। নিজের input পরীক্ষা করতে:

```python
from practice.math_lab import build_report

report = build_report(data)  # আগের পূর্ণ example-এর data dictionary
assert report["delivery_capacity"] == 10
assert report["launch_time"] == 22
```

Test file-এ 12টি test method আছে; একেকটি method-এর মধ্যে অনেক input পরীক্ষা হয়। এগুলো শুধু reference function-এর logic নকল করে না:

| পরীক্ষা | স্বাধীনভাবে expected ফল কীভাবে বের হয় |
| --- | --- |
| Worked example | উপরের হাতে করা নির্দিষ্ট output |
| Range update/query | ছোট array-তে প্রতিটি ঘর সরাসরি বদলে, slice sum |
| Sliding window | ছোট positive array-এর **সব subarray** পরীক্ষা |
| Shipping | ছোট input-এর **সব অনুমোদিত partition** পরীক্ষা |
| Greedy schedule | ছোট session list-এর **সব subset** পরীক্ষা |
| CRT | ছোট modulus-এ এক পূর্ণ LCM cycle সরাসরি scan |
| Equipment | ছোট input-এর সব subset; ফেরত দেওয়া index-ও পরীক্ষা |
| Geometry | triangle, rectangle, diamond, line, duplicate এবং translation |
| Integration | input অপরিবর্তিত; তিন dispatch শর্ত একেকটি ব্যর্থ করে দেখা |
| Invalid input | negative value, ভুল range, zero period, unknown field, ভুল type |

**নিজের শেখার পরীক্ষা:** test pass করার পরে একটি ছোট case-এ intentionally `right`-কে inclusive করে দেখো। কোন test ব্যর্থ হচ্ছে এবং কেন, বোঝাতে পারলে boundary convention-টি পরিষ্কার হয়েছে। তারপর ভুলটি ফিরিয়ে ঠিক করো।

## ৭. সময় ও memory-এর হিসাব

এখানে `n` = demand দিন, `u` = update, `q` = query, `v` = volunteer, `d` = batch ID digit, `s` = session, `p` = booth, `e` = equipment, `S` = total final demand। নিচের সাধারণ bound-গুলো arithmetic operation ধরে লেখা; Python-এর বড় integer-এ bit-length অনুযায়ী অতিরিক্ত খরচ হয়।

| অংশ | সময় | অতিরিক্ত memory |
| --- | --- | --- |
| Badge ও registration | `O(d + log v)` | `O(1)` accumulator |
| GCD packing | `O(n log A)`; `A` = সর্বোচ্চ final demand | `O(1)` |
| Team count | `O(min(k,v-k))` বড় integer operation | একটি বড় integer; exact count সর্বোচ্চ `O(v)` bit |
| Skill union | `O(v)` | `O(1)`; fixed 20 bit |
| Difference ও prefix | `O(n+u+q)` | `O(n+q)` output-সহ |
| Busy window | `O(n)`; প্রতিটি pointer সামনে যায় | `O(1)` |
| Shipping | `O(n log S)` | `O(1)` |
| Sessions | `O(s log s)` | `O(s)` |
| Convex hull | `O(p log p)` | `O(p)` |
| CRT | সর্বোচ্চ 8টি extended-GCD merge | কয়েকটি বড় integer; period সর্বোচ্চ input period-গুলোর product |
| Equipment | `O(e * 2**(e/2))` | `O(2**(e/2))` |

সবচেয়ে ব্যয়বহুল অংশ equipment search। তাই 32 item-এর সীমা উদ্দেশ্যপূর্ণ। এখানে চাহিদা ধনাত্মক, update শুধু যোগ হয়, cost ঋণাত্মক নয়—এই তিন শর্ত সরিয়ে দিলে আগের correctness proof পুনরায় পরীক্ষা করতে হবে।

## ৮. এই একটি project কী cover করল, কী এখনও বাকি

নিচের “বাকি” কলামের সমস্যা আলাদা করে অনুশীলন করবে। একই level-এর নাম থাকলেই তার সব কৌশল এই এক project-এ এসে যায় না।

| Level | এই capstone-এ ব্যবহার | এখনও আলাদা অনুশীলনের উদাহরণ |
| --- | --- | --- |
| 00 | Digit scan, parity, বড় number string | Reverse, palindrome, Armstrong |
| 01 | Euclidean GCD, divisibility, সমান packing | Sieve, prime factorization, divisor count, totient |
| 02 | Decimal remainder, binary modular power | Modular inverse, modular division, Fermat |
| 03 | Combination ও exact counting | Stars-and-bars, inclusion-exclusion, Catalan, derangement |
| 04 | OR/AND masks; subset mask পুনর্গঠন | XOR uniqueness, Gray code, maximum XOR pair |
| 05 | Difference array, prefix sum, range update/query | 2D prefix, contribution, subarray minimums |
| 06 | Positive-sum variable sliding window | Three Sum, distinct-count window, product window |
| 07 | Monotonic feasibility, minimum capacity | Aggressive Cows, median partition, kth table item |
| 08 | Earliest-finish greedy ও exchange argument | Candy, Gas Station, rearrangement constraints |
| 09 | Orientation, convex hull, shoelace area | Line intersection, circle tests, Pick's theorem |
| 10 | Extended Euclid, non-coprime CRT | Miller–Rabin, Pollard Rho, Möbius, matrix power |
| 11 | Meet in the middle, binary-search join | Nim, Grundy, probability DP, Burnside, constructive |

শেষ করার মানদণ্ড: ১২টি ধাপের ফল নিজে ব্যাখ্যা করতে পারবে, tests pass হবে, এবং অন্তত **একটি** brute-force comparison নিজের হাতে লিখতে পারবে। তারপর [পূর্ণ problem তালিকা](../01-math-based-programming-fundamentals/roadmap.md) থেকে “বাকি” কৌশলগুলোর নোটে ফিরে যাও।