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

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

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

সময় নিয়ে কাজ করো: ভিত্তি ও হিসাব → পরিকল্পনা → advanced অংশ → একসঙ্গে report। আগে Math chapter ও সমস্ত Math problem-এর তালিকা খুলে রাখো।

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

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

Level	আগে concept পড়বে	capstone-এর আগে ছোট অনুশীলন
00 — সংখ্যার ভিত্তি	Digits ও parity	002 — Sum of Digits, 001 — Even or Odd
01 — ভাগ ও GCD	GCD ও divisibility	018 — Euclidean GCD
02 — Modular arithmetic	Remainder ও fast power	031 — Large Number Mod, 029 — Modular Exponentiation
03 — Counting	Combination	041 — Combination
04 — Bits	Mask ও bit operations	054 — Check ith Bit, 062 — Subset Generation
05 — Prefix ও difference	Range-এর হিসাব	069 — Difference Array, 068 — Range Sum
06 — Sliding window	Positive সংখ্যার window	087 — Minimum Size Subarray Sum
07 — Binary search	উত্তরের উপর search	097 — Ship Packages
08 — Greedy	Exchange argument	107 — Interval Scheduling
09 — Geometry	Cross product ও hull	116 — Orientation, 120 — Convex Hull
10 — Advanced number theory	Extended Euclid ও CRT	125 — Extended Euclidean, 127 — CRT
11 — Mixed patterns	অর্ধেক করে খোঁজা	139 — Meet in the Middle

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-এর উৎস দেখো।

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

তোমার দায়িত্ব মেলার 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-এর যৌথ সময় পাওয়া গেছে। অন্য হিসাবগুলো ওই সিদ্ধান্তের সঙ্গে রিপোর্টে থাকবে।

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,
}

Range update থেকে shipping plan

1. আগের চাহিদা

   02

   চিহ্নিত ঘর: 14

   চিহ্নিত ঘর: 22

   36

   [1,3) range-এর দুই দিনে 2 করে যোগ হবে।

2. সব update-এর পরে

   02

   16

   24

   36

   মোট 18; সমান packet-এর সবচেয়ে বড় মাপ gcd = 2।

3. Trip 1

   02

   16

   Load 8; পরের batch 4 যোগ করলে capacity 10 ছাড়াবে।

4. Trip 2

   04

   16

   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 ডাউনলোড
• সম্পূর্ণ runnable reference solution

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 তালিকা থেকে “বাকি” কৌশলগুলোর নোটে ফিরে যাও।