Problem link ও উৎস
- **Original source:** Classic complement-lookup exercise (CP scale)
- **Platform:** CSES —
(task name: Sum of Two Values)
- **Topic:** hash map (complement lookup)
- **Difficulty:** Medium
- **Pattern:** complement lookup
- **Basic idea inherited from:** CP input size-এ Two Sum — একই tweak, কিন্তু বড় n আর 1-indexed উত্তর
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`n`টা সংখ্যা আর একটা target `x` দেওয়া আছে। এমন **দুটো ভিন্ন position** খুঁজে বের করতে হবে যাদের সংখ্যা দুটো যোগ করলে ঠিক `x` হয়, আর সেই দুটো position ছাপতে হবে। CSES-এর নিয়মে position **1 থেকে গোনা** (1-indexed)। কোনো জোড়া না থাকলে `IMPOSSIBLE` ছাপতে হয়।
```text
nums = [2, 7, 5, 1], x = 9 (1-indexed)
2 + 7 = 9 → position 1 ও 2
উত্তর: 1 2
```
### Input ও output {#8-example-input-and-output}
```text
Input : nums = [2, 7, 5, 1], x = 9 Output: 1 2
Input : nums = [1, 4, 5, 3, 11], x = 9 Output: 2 3 (4 + 5)
Input : nums = [1, 2, 3], x = 100 Output: IMPOSSIBLE
Input : nums = [5, 5], x = 10 Output: 1 2 (একই value, ভিন্ন position)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা বড় হলঘরে অনেক লোক, প্রত্যেকের গায়ে একটা নম্বর-ব্যাজ। তুমি এমন জোড়া খুঁজছ যাদের নম্বরের যোগ ঠিক `x`। তুমি সবার সাথে সবাইকে মেলাও না — নতুন একজন এলে শুধু ভাবো "`x` পেতে হলে এর partner-এর নম্বর কত? আগে কি সেই নম্বরের কাউকে দেখেছি, আর কোথায় দাঁড়িয়ে ছিল?" তোমার মাথার সেই "নম্বর → কে কোথায়" তালিকাটাই hash map।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা হুবহু **Two Sum** (#1)-এর complement lookup — শুধু পোশাক বদলেছে। দুটো পার্থক্য: (১) CSES competitive scale-এ `n` অনেক বড় হতে পারে (10^5+), তাই O(n^2) একদম চলবে না, hash map লাগবেই; (২) উত্তর হলো 1-indexed position, array index নয়। [../patterns.md](../patterns.md)-তে এটা Pattern 2।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
সেই একই সরল বীজগণিত: দুটো সংখ্যা `a + b = x` চাই, তাই হাতে থাকা `v`-এর জন্য দরকারি partner একটাই — `x - v` (complement)। প্রশ্নটা বদলে যায় "এই নির্দিষ্ট complement কি আগে কোনো position-এ দেখেছি?"-তে। যেহেতু আমরা position ফেরত দিচ্ছি, map-এ মান হিসেবে value-র **position** রাখতে হবে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **hash map** (`value → 1-indexed position`)। শুধু "complement আছে কি না" জানলে হবে না — তার **position**-টাও দরকার, কারণ আমরা index ছাপছি। CP-তে Python-এর `dict` যথেষ্ট দ্রুত।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
`need in seen` membership-check গড়ে **O(1)**, পুরো scan O(n)। `n = 2·10^5`-এ O(n^2) মানে ৪০ বিলিয়ন অপারেশন — time limit-এ অসম্ভব; hash map সেটাকে রৈখিক করে দেয়। সাথে map প্রতিটা value-র প্রথম position ধরে রাখে, ঠিক যা ছাপতে হবে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা জোড়া position `(i, j)` ধরে দেখি যোগফল `x` কি না।
```text
প্রতিটা i-র জন্য:
প্রতিটা j > i-র জন্য:
nums[i] + nums[j] == x হলে print(i+1, j+1) # 1-indexed
কিছু না পেলে print("IMPOSSIBLE")
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
দুটো nested loop মানে **O(n^2)**। ছোট LeetCode input-এ চলে গেলেও CSES-এর বড় `n`-এ time limit ফেটে যাবে। অপচয়টা Two Sum-এর মতোই: প্রতিটা সংখ্যার জন্য আমরা বাকি পুরো array আবার scan করছি, যদিও ঠিক জানি কোন একটাই সংখ্যা (`x - v`) দরকার। জানা জিনিস খুঁজতে scan লাগে না।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **partner অনুমান নয়, হিসেব করা যায় — `x - v`।** তাই কাজটা "একটা নির্দিষ্ট value আগে কোন position-এ এসেছিল?" দেখায় নেমে আসে, যা hash map গড়ে O(1)-এ বলে। বড় `n`-এ এটাই একমাত্র বাঁচার পথ।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
array-র উপর একবারই হাঁটো, position 1 থেকে গোনা। প্রতিটা `v`-তে জিজ্ঞেস করো "`x - v` কি `seen`-এ আছে?" — থাকলে জোড়া পেয়ে গেছ, দুটো position ফেরত দাও (আগের + এখনকার)। না থাকলে নিজেকে (`v → এখনকার position`) `seen`-এ রেখে এগোও। এক pass, O(n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** *জোড়া খুঁজো না — এ পর্যন্ত কী দেখেছ, কোথায় দেখেছ, সেটা মনে রাখো।* এটি Two Sum-এরই tweak ("search না করে remember করো"), শুধু এখানে index-এর বদলে 1-indexed position টুকে রাখছি। CP-তে এই tweak আয়ত্তে থাকলে অনেক "pair with sum/diff" problem তাৎক্ষণিক সমাধান হয়।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [2, 7, 5, 1]`, `x = 9`। `seen` (value → 1-indexed position) ভরে; প্রতি ধাপে `need = x - v` খুঁজি:
```text
pos=1 v=2 need=9-2=7 7 in {}? না → seen={2:1}
pos=2 v=7 need=9-7=2 2 in {2:1}? হ্যাঁ → উত্তর (seen[2], 2) = (1, 2)
```
partner-কে সামনে খুঁজি না — শুধু *পেছনের* স্মৃতিতে তাকাই, তাই ছোট position সবসময় আগে আসে।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `nums = [1, 4, 5, 3, 11]`, `x = 9`:
1. শুরু: `seen = {}` (খালি)।
2. `pos=1, v=1`: `need = 8`; `8 in {}?` না → `seen = {1: 1}`।
3. `pos=2, v=4`: `need = 5`; `5 in {1:1}?` না → `seen = {1:1, 4:2}`।
4. `pos=3, v=5`: `need = 4`; `4 in seen?` হ্যাঁ (position 2) → উত্তর `(2, 3)`।
5. শেষ: `4 + 5 = 9`, position 2 ও 3।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def sum_of_two_values(nums, x):
seen = {} # value -> 1-indexed position
for i, v in enumerate(nums, start=1): # CSES position 1 থেকে গোনে
need = x - v # partner হিসেব করো
if need in seen: # অতীত কি partner দিয়েছে?
return (seen[need], i) # ছোট position আগে (need আগে দেখা)
seen[v] = i # নিজেকে position সহ মনে রাখো
return None # কোনো জোড়া নেই → "IMPOSSIBLE"
# ---- tests ----
assert sum_of_two_values([2, 7, 5, 1], 9) == (1, 2)
assert sum_of_two_values([1, 4, 5, 3, 11], 9) == (2, 3) # 4 + 5
assert sum_of_two_values([1, 2, 3], 100) is None # IMPOSSIBLE
assert sum_of_two_values([5, 5], 10) == (1, 2) # একই value, ভিন্ন position
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `seen = {}` — খালি hash map, `value → প্রথম যে position-এ দেখা`।
- `enumerate(nums, start=1)` — position 1 থেকে গোনা শুরু, কারণ CSES 1-indexed উত্তর চায়।
- `need = x - v` — `v`-এর জন্য দরকারি partner হিসেব।
- `if need in seen` — সেই partner কি আগে দেখেছি? `dict`-এ গড়ে O(1)।
- `return (seen[need], i)` — পেলে partner-এর আগের position আর এখনকার position; আগেরটা ছোট, তাই আগে।
- `seen[v] = i` — না পেলে নিজেকে position সহ টুকে রাখি, যাতে পরে কেউ partner হিসেবে পায়।
- `return None` — loop শেষেও জোড়া না মিললে; বাস্তব submission-এ এখানে `IMPOSSIBLE` ছাপা হতো।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[2,7,5,1]` x=9-এ position 1-এ 2 যায় seen-এ; position 2-এ `v=7`, `need=2`, যা seen-এ আছে → `(1, 2)`। `[1,4,5,3,11]`-এ জোড়া হয় position 2 ও 3 (`4+5`) → `(2, 3)`। `[1,2,3]` x=100-এ কোনো partner মেলে না → `None` (অর্থাৎ IMPOSSIBLE)। `[5,5]`-এ দ্বিতীয় 5-এর complement 5 আগে position 1-এ দেখা → `(1, 2)`। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — array-র উপর একবারই হাঁটি, প্রতি element-এ hash map operation গড়ে O(1)। বড় CSES input-এ এটাই গ্রহণযোগ্য।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — worst case-এ প্রায় সব value `seen` map-এ জমতে পারে।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- 0-indexed ফেরত দেওয়া — CSES **1-indexed** চায়; `enumerate(..., start=1)` ব্যবহার না করলে উত্তর এক ঘর কম হয়ে wrong answer।
- lookup-এর আগে insert করা — `seen[v] = i` আগে করলে `x` জোড় হলে একই element নিজের সাথে জোড়া বানিয়ে এক position দুবার দেয়; সবসময় আগে check, পরে insert।
- O(n^2) brute force দিয়ে চেষ্টা করা — CSES-এর বড় `n`-এ time limit exceed; hash map বাধ্যতামূলক।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Two Sum (#1)-এর complement lookup। এই note দেখায় একই pattern কীভাবে competitive scale-এ (বড় `n`, 1-indexed I/O) প্রয়োগ হয় — algorithm এক, শুধু input-আকার আর output-ফরম্যাট বদলায়। সম্পূর্ণ চাল [../patterns.md](../patterns.md)-র Pattern 2-এ (CSES "Sum of Two Values" উদাহরণসহ উল্লেখিত)।
### পরের অনুশীলন {#22-similar-harder-problems}
- Two Sum —