Arrays ও Strings — দুই ডিভাইসের study report

একই পড়ার অ্যাপ ফোন ও ল্যাপটপে চালিয়েছ। দুই ডিভাইসের session আলাদাভাবে সময় অনুযায়ী সাজানো। একটি report-এ সেগুলো মিলিয়ে দেখতে হবে: নির্দিষ্ট অংশে কত score, একই বিষয় পুনরাবৃত্তি ছাড়া দীর্ঘতম অংশ কোনটি, এবং মোট score সবচেয়ে বেশি এমন টানা অংশ কোনটি। এই একটি report-এ merge, prefix sum, sliding window ও Kadane একসঙ্গে কাজে লাগবে।

কোর্স-সংযোগ: Microsoft কোর্সের Module 1-এর arrays/complexity এবং Module 2-এর sorted data নিয়ে কাজ করার অনুশীলন। এটি এই সাইটের নিজস্ব সমস্যা; কোর্সের official assignment নয়।

১. শুরু করার আগে যা পড়বে

ক্রম	পড়া ও অনুশীলন	নিজেকে যে প্রশ্ন করবে
1	Array-এর ধারণা, চিত্র	index ও value আলাদা কেন?
2	Merge Sorted Array	দুই input-এর পরের ছোট মান কোথায়?
3	Static Range Sum	prefix[0] = 0 রাখলে সুবিধা কী?
4	Longest Unique Substring	duplicate পেলে বাঁ পাশ কত দূর যাবে?
5	Maximum Subarray	আগের negative যোগফল রেখে লাভ হয় কি?

২. সমস্যার চুক্তি

session_report(left, right, queries) বানাও। প্রতিটি session হলো (time, tag, score)। time ও score integer; tag একটি খালি নয় এমন string। score negative হতে পারে, যেমন ভুল উত্তর বা penalty। প্রতিটি input সময়ের ছোট থেকে বড় ক্রমে থাকবে। সমান সময় হলে left-এর session আগে নেবে; একই batch-এর ক্রমও রাখবে। input বদলানো যাবে না।

• দুই batch মিলিয়ে 0 ≤ n ≤ 100000; 0 ≤ q ≤ 100000 query।
• প্রতিটি query (start, end) মিলিত array-র index; [start, end) মানে start থাকবে, end থাকবে না। 0 ≤ start ≤ end ≤ n। খালি range-এর যোগফল 0।
• unique_span: tag পুনরাবৃত্তি নেই এমন দীর্ঘতম span। সমান দৈর্ঘ্যে সবচেয়ে বাঁয়েরটি। খালি input-এ (0, 0)। tag-এর case বদলাবে না: A ও a আলাদা।
• best_score: সর্বোচ্চ score-এর খালি নয় এমন contiguous span ও score। সমান score হলে ছোট start, তারপর ছোট end। খালি input-এ None।
• ভুল sorted order, খালি tag বা ভুল query পেলে ValueError।

হাতে করা উদাহরণ

Python

left = [(1, "A", 3), (3, "B", -2)]
right = [(2, "C", 4), (4, "A", 5)]
queries = [(0, 3), (2, 4)]

মিলিত session-এর score; নিচের index দিয়েই query

1. সময় 1, 2, 3, 4 — tag A, C, B, A

   চিহ্নিত ঘর: 03

   চিহ্নিত ঘর: 14

   চিহ্নিত ঘর: 2-2

   35

   প্রথম তিন tag আলাদা। শেষ A এলে বাঁ পাশ 0 থেকে 1 হয়; আগের span-ই tie-তে জেতে।

2. প্রথম ঘর 0 রেখে prefix তৈরি

   চিহ্নিত ঘর: 00

   13

   27

   চিহ্নিত ঘর: 35

   410

   [0,3)-এর score = prefix[3] − prefix[0] = 5।

প্রত্যাশিত output:

Python

{
    "sessions": [(1, "A", 3), (2, "C", 4), (3, "B", -2), (4, "A", 5)],
    "range_scores": [5, 3],
    "unique_span": (0, 3),
    "best_score": {"score": 10, "span": (0, 4)},
}

দ্বিতীয় query-তে -2 + 5 = 3। সবচেয়ে লাভজনক span পুরো array: 3 + 4 - 2 + 5 = 10।

৩. চারটি guided milestone

ধাপ A — সময় অনুযায়ী এক করা

merge_sessions(left, right) লিখো। i ও j দিয়ে দুই batch-এর পরের unread session বোঝাও। ছোট timestamp-টি output-এ রাখো; শুধু সেই pointer বাড়াও। এক batch শেষ হলে অন্যটির বাকি অংশ নাও।

Invariant: output-এ এখন পর্যন্ত নেওয়া সব session সঠিক ক্রমে আছে; i + j হলো নেওয়া session-এর সংখ্যা। Hint: timestamp সমান হলে <= ব্যবহার করলেই left আগে থাকবে।

Checkpoint: test_stable_merge, test_no_input_mutation, test_unsorted_and_invalid_session পাস করো। নিজের কাগজে দুটি batch-এ একই timestamp দিয়ে trace করো।

ধাপ B — query-র উত্তর এক বিয়োগে

prefix_scores(scores)-এ length n + 1 prefix বানাও। তারপর range_scores(prefix, queries) লিখো। এখানে prefix[i]-তে index i-এর মান নেই; আছে তার আগের সব মানের যোগফল।

Invariant: prefix[i + 1] = prefix[i] + scores[i]। Hint: [start,end)-এর উত্তর prefix[end] - prefix[start]; end + 1 ব্যবহার করবে না।

Checkpoint: খালি query (2,2)-এর উত্তর 0, এবং sample-এর দুই উত্তর [5,3]। invalid query যেন array থেকে ভুল মান পড়তে না পারে।

ধাপ C — একই tag ছাড়া দীর্ঘতম অংশ

longest_unique_span(tags)-এ last[tag] রাখো। প্রতিটি ডান প্রান্তে duplicate-এর আগের অবস্থান দেখে start = max(start, last[tag] + 1) করো। তারপর last update করো।

Invariant: [start,end]-এ কোনো tag দুইবার নেই এবং start কখনো পিছোয় না। Hint: abba-তে শেষ a দেখে start পিছিয়ে দিলে ভুল হবে। শুধু কঠোরভাবে বড় দৈর্ঘ্য পেলেই best বদলালে tie-র নিয়ম মেনে চলবে।

Checkpoint: abba → (0,2); সব tag আলাদা হলে পুরো array।

ধাপ D — সবচেয়ে ভালো contiguous score ও সম্পূর্ণ report

best_score_span(scores) লিখো। প্রতিটি index-এ দুটি পথ: বর্তমান score দিয়ে নতুন span শুরু, অথবা আগের span বাড়ানো। আগের চলতি sum negative হলেই নতুন শুরু করো। শূন্য হলে আগের start রাখলে earliest-start tie ঠিক থাকে।

Invariant: চলতি sum হলো বর্তমান index-এ শেষ হওয়া সেরা span-এর sum। পুরো input-এর best আলাদা করে রাখো। সব score negative হলেও একটি session বেছে নিতে হবে।

Checkpoint: [-3,-1,-1] → score -1, span (1,2); [0,1,-1,1] → score 1, span (0,2)। এবার চার helper-কে session_report-এ যুক্ত করো।

৪. Unit test, solution ও নিজের যাচাই

Python reference implementation · Unit tests

প্রথমে উপরের function contract ধরে নিজে implement করো। reference-এ দুই pointer, একটি prefix array, একটি last-position dictionary ও একটি চলতি sum কীভাবে একই report-এ পৌঁছায় তা পরে মিলিয়ে দেখো। ফাইল দুটি project-এর practice/ folder-এ রেখে root থেকে চালাও:

Bash

python -m unittest discover -s practice -p 'test_arrays_lab.py' -v

৯টি test-এ sample, stable merge, input না-বদলানো, empty input, invalid query এবং negative/tie আছে। আরও ১৫০টি ছোট random case-এ window ও best score-কে সব সম্ভব span পরীক্ষা করা ধীর সমাধানের সঙ্গে মেলানো হয়। শুধু sample পাস হওয়া যথেষ্ট নয়।

৫. কী যুক্ত হলো, কী আলাদা পড়তে হবে

Technique	এই সমস্যায় ব্যবহার
Two pointers	sorted session merge
Prefix sum	index-range score query
String equality + sliding window	পুনরাবৃত্তি ছাড়া tag-এর span
Kadane + tie handling	সর্বোচ্চ score-এর contiguous span
আলাদা অনুশীলন	rotation, anagram grouping, minimum-cover window, rain water ও KMP এই report-এর অংশ নয়

সব helper মিলিয়ে সময় O(n + q); report, prefix ও tag map-সহ অতিরিক্ত memory O(n + q)। range query করার পরে score বদলালে পুরনো prefix অচল হবে—এই সংস্করণে update নেই। পরের চ্যালেঞ্জ: score update দরকার হলে Fenwick/Segment Tree ব্যবহার করে report-এর range অংশ বদলাও।