Problem link ও উৎস
- **Original source:** Classic exercise (grid reachability / parity)
- **Platform:** — (classic competitive programming exercise)
- **Topic:** Math-based programming fundamentals → Level 9: Geometry & Coordinate Math
- **Difficulty:** Medium
- **Pattern:** parity reachability (জোড়/বিজোড় দিয়ে পৌঁছানো সম্ভব কিনা)
- **Basic idea inherited from:** 001 — Even or Odd
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা অসীম গ্রিডে তুমি শুরুতে `(0, 0)`-তে দাঁড়িয়ে। প্রতি ধাপে চার দিকের যেকোনো একটায় এক ঘর সরতে পারো — উপরে, নিচে, বাঁয়ে বা ডানে (কোনাকুনি নয়)। প্রশ্ন:
> ঠিক **`s`টা ধাপে** (এক ধাপও কম নয়, বেশিও নয়) তুমি কি `(x, y)` ঘরে পৌঁছাতে পারো?
লক্ষ করো — "ঠিক `s` ধাপে" শব্দটা গুরুত্বপূর্ণ। শুধু পৌঁছানো নয়, **ঠিক ততগুলো** ধাপ ব্যবহার করতে হবে। যেমন `(2, 0)`-তে সরাসরি 2 ধাপে যাওয়া যায়; কিন্তু 3 ধাপে? আর 4 ধাপে?
উদাহরণ: target `(2, 1)`। সবচেয়ে কম ধাপ লাগে `|2| + |1| = 3`। তাই 3 ধাপে যায় (যেমন ডান, ডান, উপর)। 4 ধাপে যায় না (নিচে দেখব কেন)। 5 ধাপে আবার যায় (3 ধাপে গিয়ে, তারপর এক ঘর এদিক-ওদিক করে ফিরে এসে 2 ধাপ "নষ্ট")।
### Input ও output {#6-example-input-and-output}
```text
x y s reachable? কেন
-----------------------------------------------------------
2 1 3 True d=3, s-d=0 জোড়
2 1 4 False d=3, s-d=1 বিজোড় (parity ভুল)
2 1 5 True d=3, s-d=2 জোড়
0 0 0 True শুরুতেই সেখানে (d=0, s-d=0)
0 0 1 False d=0, কিন্তু 1 ধাপে ফিরে আসা যায় না (বিজোড়)
0 0 2 True 1 ঘর গিয়ে ফিরে আসা
1 0 1 True d=1, এক ধাপ
3 4 7 True d=7, ঠিক সোজা পথ
3 4 6 False s < d, অসম্ভব
-2 -3 9 True d=5, s-d=4 জোড় (negative-ও একই নিয়ম)
```
মূল edge case: **`s = 0`** (শুধু `(0,0)`-এই, তাও d=0 হলে), **`(0,0)`-তে ফেরা** (লাগে জোড় ধাপ — 1 ধাপে ফেরা যায় না!), আর **negative coordinate** (absolute নেওয়ায় নিয়ম একই)। অনেকে `(0,0)`-এ 1 ধাপে "থাকা যায়" ভেবে ভুল করে — যায় না, কারণ এক ধাপ সরতেই হবে।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা দাবার/চেকার বোর্ড — সাদা আর কালো ঘর পালা করে সাজানো। তুমি একটা ঘরে দাঁড়িয়ে, আর প্রতি চালে পাশের ঘরে (উপর/নিচ/বাঁ/ডান) যাও। লক্ষ করো — **প্রতিবার তুমি ঘরের রঙ বদলাও**: সাদা থেকে কালো, কালো থেকে সাদা। এক চালে কখনো একই রঙে থাকতে পারো না।
তাই শুরুর ঘর যদি সাদা হয়, তাহলে 1 চাল পরে তুমি অবশ্যই কালোয়, 2 চাল পরে আবার সাদায়, 3 চালে কালোয় — অর্থাৎ চালের সংখ্যা জোড় হলে শুরুর রঙে, বিজোড় হলে উল্টো রঙে। এখন target ঘরটা যদি কালো হয়, আর তুমি সাদা থেকে শুরু করো, তাহলে শুধু **বিজোড়** সংখ্যক চালেই সেখানে থাকা সম্ভব — জোড় চালে কখনো নয়, যত বড় সংখ্যাই হোক। এই "রঙ মেলে কিনা" = parity মেলে কিনা। আর অবশ্যই, target যত দূরেই হোক, অন্তত সরাসরি দূরত্বটুকু চাল তো লাগবেই।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা সরাসরি দাঁড়িয়ে আছে একদম শুরুর **001 — Even or Odd**-এর উপর — গোটা repo-র প্রথম problem! 001-এ তুমি শিখেছিলে `% 2` দিয়ে parity (জোড়/বিজোড়) বোঝা, আর "প্রতি ধাপে কিছু একটা উল্টে যায়" ধরনের চিন্তা। এখানে সেই parity-ই গ্রিডে রূপ নিয়েছে: প্রতিটা চলন `x + y`-এর parity উল্টে দেয়, ঠিক যেমন একটা সংখ্যায় 1 যোগ করলে even ↔ odd উল্টায়।
নতুন যেটা যোগ হলো — parity-কে একটা **পৌঁছানোর শর্ত** (reachability invariant) হিসেবে ব্যবহার করা, আর সেটাকে গ্রিড/চেকার-বোর্ডের রঙের সাথে যুক্ত করা। এই "প্রতি move-এ একটা পরিমাণ flip হয়, তাই parity একটা invariant" চিন্তাটা গ্রিড-BFS, game theory, graph 2-coloring-এ বারবার ফিরবে। তাই 001-এর ছোট্ট `% 2` এখানে একটা শক্তিশালী হাতিয়ার হয়ে দাঁড়াল — শিকড়ে ফেরার দারুণ উদাহরণ।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল গাণিতিক সত্য দুটো শর্তে ধরা। ধরো **`d = |x| + |y|`** (Manhattan distance, ন্যূনতম প্রয়োজনীয় ধাপ)। তাহলে ঠিক `s` ধাপে `(x, y)` পৌঁছানো যায় **যদি এবং কেবল যদি**:
1. **`s >= d`** — অন্তত d ধাপ তো লাগবেই (এর কমে অসম্ভব), আর
2. **`(s − d)` জোড় (even)** — বাড়তি ধাপগুলো জোড়ায় জোড়ায় "নষ্ট" করতে হয়।
দ্বিতীয় শর্তটাই আসল গণিত — **parity**। কেন বাড়তি ধাপ জোড় হতে হবে? প্রতিটা ধাপে `x + y`-এর জোড়/বিজোড়তা (parity) **উল্টে যায়** (এক ঘর সরলে x বা y-এর একটা ±1 বদলায়, তাই যোগফলের parity flip)। শুরুতে `(0,0)`-এ `x + y = 0` (জোড়)। তাই `s` ধাপ পরে আমার parity হবে `s`-এর parity। target-এ পৌঁছাতে হলে target-এর parity (`(x + y) mod 2`) আর `s`-এর parity মিলতে হবে — যা ঠিক `(s − d)` জোড় হওয়ার সমান (কারণ `d = |x|+|y|` আর `x+y`-এর parity এক)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরল চিন্তা — সত্যি সত্যি সব সম্ভাব্য পথ অনুকরণ করো। ঠিক `s` ধাপে কোন কোন ঘরে পৌঁছানো যায়, সেই সেট বানাও ধাপে ধাপে, শেষে target আছে কিনা দেখো:
```python
def reachable_brute(x, y, s):
positions = {(0, 0)}
for _ in range(s):
nxt = set()
for (a, b) in positions:
for da, db in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nxt.add((a + da, b + db))
positions = nxt
return (x, y) in positions
```
এটা প্রতিটা ধাপে সম্ভাব্য ঘরের সেট বাড়ায় (একরকম BFS-by-layer), তাই নিশ্চিত ঠিক উত্তর — asserts-এ এটাই reference। ছোট `s`-এ চমৎকার, কিন্তু সেট দ্রুত বড় হয়।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
`s` ধাপ পরে সম্ভাব্য ঘরের সংখ্যা প্রায় `O(s²)` (একটা হীরে-আকৃতির এলাকা), আর প্রতি ধাপে আগের সব ঘর থেকে নতুন ঘর বানানো — সব মিলিয়ে প্রায় `O(s³)` কাজ ও `O(s²)` স্মৃতি।
```text
s = 100000 হলে:
brute (set সিমুলেশন): ~s^3 ≈ 10^15 কাজ, s^2 ≈ 10^10 স্মৃতি (সম্পূর্ণ অসম্ভব)
parity সূত্র : O(1) — দুটো তুলনা আর একটা % 2 (তাৎক্ষণিক)
```
মূল অপচয় বিশাল — আমরা প্রতিটা পথ/ঘর সিমুলেট করছি, যেখানে গণিত (দূরত্ব + parity) দুটো লাইনে উত্তর দিয়ে দেয়। আসলে "পৌঁছানো যায় কিনা" পুরো পথের উপর নির্ভর করে না, শুধু দুটো invariant-এর উপর: যথেষ্ট ধাপ আছে কি, আর parity মেলে কি।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — পথ সিমুলেট করার দরকারই নেই; দুটো শর্ত যথেষ্ট: যথেষ্ট ধাপ (`s >= d`) আর parity মেলা (`(s − d)` জোড়):
```python
def reachable(x, y, s):
d = abs(x) + abs(y) # ন্যূনতম প্রয়োজনীয় ধাপ (Manhattan)
return s >= d and (s - d) % 2 == 0
```
মাত্র দুটো তুলনা আর একটা `% 2` — O(1)। দূরত্ব বলে দেয় "অন্তত কত লাগবে", আর parity বলে দেয় "বাড়তিটুকু জোড়ায় নষ্ট করা যায় কিনা"। এই এক লাইন সিমুলেশনের সব কাজ মুছে দেয়।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" — **পৌঁছানো যায় কিনা পুরো পথের উপর নির্ভর করে না; শুধু দুটো জিনিসে: (১) যথেষ্ট ধাপ আছে কি, আর (২) parity মেলে কি।**
দ্বিতীয়টাই মূল মোচড়: প্রতিটা চলন `x + y`-এর parity উল্টে দেয় (চেকার বোর্ডের রঙ বদলানোর মতো), তাই `s` ধাপ পরের parity বাঁধা — `s`-এর সাথে মেলে। target-এর parity মিলতে হবে, আর বাড়তি ধাপ সবসময় জোড়ায় ("গিয়ে-ফিরে") শোষণ করা যায়, বিজোড়ে নয়। "ঠিক k ধাপে / move-এ পৌঁছানো/ফেরা যায় কি" দেখলেই এই দূরত্ব + parity জোড়া মাথায় আসুক — search নয়, গণিত। (001-এর `% 2` এখানে গ্রিডের ভাষায় কথা বলছে।)
### ছবিতে বোঝা {#5-visual-explanation}
প্রথমে চেকার-বোর্ডের parity — প্রতি ঘরে `(x + y) % 2`, সাদা/কালো:
```text
গ্রিডে (x+y) parity (0=সাদা ·, 1=কালো #):
y=2 · # · #
y=1 # · # ·
y=0 · # · # (0,0) সাদা (·)
y=-1 # · # ·
x=0 1 2 3
প্রতি move রঙ বদলায় -> s চালে রঙ = s-এর parity-র সাথে মেলে
```
এবার target `(2,1)`: `d = |2|+|1| = 3` (কালো ঘর)। কোন `s`-এ পৌঁছানো যায়:
```text
s s>=d? (s-d) জোড়? পৌঁছানো যায়?
0 না - না
1 না - না
2 না - না (2 < 3)
3 হ্যাঁ 0 জোড় হ্যাঁ <- সরাসরি: ডান,ডান,উপর
4 হ্যাঁ 1 বিজোড় না (parity মেলে না: 4 জোড়, target কালো)
5 হ্যাঁ 2 জোড় হ্যাঁ <- 3 ধাপে গিয়ে, 1 ঘর গিয়ে-ফিরে (2 নষ্ট)
6 হ্যাঁ 3 বিজোড় না
```
"বাড়তি ধাপ জোড়ায় নষ্ট" কেন — এক ঘর সরে আবার ফিরে এলে 2 ধাপ লাগে, অবস্থান একই:
```text
এক জোড়া "নষ্ট" ধাপ: X --ডান--> Y --বাঁ--> X (2 ধাপ, X-এই ফিরে এলাম)
তাই বাড়তি ধাপ সবসময় জোড় সংখ্যায় শোষণ করা যায়, বিজোড় নয়।
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
target `(2, 1)`, তিনটা `s` মান পরীক্ষা করি:
**s = 3:**
1. `d = |2| + |1|` = `2 + 1` = 3।
2. `s >= d`? `3 >= 3` → হ্যাঁ।
3. `(s − d) % 2` = `(3 − 3) % 2` = `0 % 2` = 0 (জোড়) → হ্যাঁ।
4. দুই শর্তই সত্যি → **True**। (পথ: ডান, ডান, উপর।)
**s = 4:**
1. `d` = 3 (একই)।
2. `s >= d`? `4 >= 3` → হ্যাঁ।
3. `(s − d) % 2` = `(4 − 3) % 2` = `1 % 2` = 1 (বিজোড়) → না।
4. দ্বিতীয় শর্ত ব্যর্থ → **False**। (parity মেলে না — 4 জোড় ধাপ মানে শেষে সাদা ঘর, কিন্তু (2,1) কালো।)
**s = 5:**
1. `d` = 3; `5 >= 3` হ্যাঁ; `(5 − 3) % 2` = `2 % 2` = 0 জোড় → হ্যাঁ → **True**। (3 ধাপে (2,1)-এ, তারপর এক ঘর উপরে-নিচে করে 2 ধাপ নষ্ট।)
তিনটাই brute force সিমুলেশনের সাথে মিলে গেল।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def reachable(x, y, s):
"""(0,0) থেকে ঠিক s ধাপে (4-দিক চলন) (x,y)-তে পৌঁছানো যায় কিনা। O(1)।"""
d = abs(x) + abs(y) # ন্যূনতম প্রয়োজনীয় ধাপ (Manhattan)
return s >= d and (s - d) % 2 == 0
def reachable_brute(x, y, s):
"""সব পথ স্তরে স্তরে সিমুলেট করে — reference (ছোট s)।"""
positions = {(0, 0)}
for _ in range(s):
nxt = set()
for (a, b) in positions:
for da, db in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nxt.add((a + da, b + db))
positions = nxt
return (x, y) in positions
# --- হাতে বাছা test ---
assert reachable(2, 1, 3) is True # d=3, s-d=0
assert reachable(2, 1, 4) is False # parity ভুল
assert reachable(2, 1, 5) is True # d=3, s-d=2
assert reachable(0, 0, 0) is True # শুরুতেই সেখানে
assert reachable(0, 0, 1) is False # 1 ধাপে ফেরা যায় না
assert reachable(0, 0, 2) is True # গিয়ে-ফিরে
assert reachable(1, 0, 1) is True # এক ধাপ
assert reachable(3, 4, 7) is True # সোজা পথ
assert reachable(3, 4, 6) is False # s < d
assert reachable(-2, -3, 9) is True # negative-ও একই নিয়ম
# --- brute force-এর সাথে cross-check (random, ছোট s) ---
import random
random.seed(5)
for _ in range(3000):
x = random.randint(-4, 4)
y = random.randint(-4, 4)
s = random.randint(0, 9)
assert reachable(x, y, s) == reachable_brute(x, y, s), (x, y, s)
print(reachable(2, 1, 3)) # True
print(reachable(2, 1, 4)) # False
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
d = abs(x) + abs(y)
```
`(0,0)` থেকে `(x,y)`-তে ন্যূনতম কত ধাপ লাগে — Manhattan distance। কোনাকুনি চলা যায় না বলে এটাই সবচেয়ে ছোট পথ, এর কমে পৌঁছানো অসম্ভব।
```text
return s >= d and (s - d) % 2 == 0
```
দুটো শর্ত একসাথে। `s >= d`: অন্তত d ধাপ থাকতেই হবে (নইলে দূরত্বই পেরোনো যায় না)। `(s - d) % 2 == 0`: বাড়তি ধাপ `s − d` জোড় কিনা — কারণ বাড়তি দূরত্ব শুধু "এক ঘর গিয়ে আবার ফিরে" (২ ধাপ) করে শোষণ করা যায়, বিজোড় বাড়তি ধাপ কখনো শোষণ হয় না। দুটোই সত্যি হলে ঠিক s ধাপে পৌঁছানো সম্ভব। (এটাই parity invariant — প্রতি চলন রঙ/parity উল্টায়।)
cross-check অংশে 3000টা random `(x, y, s)`-তে O(1) সূত্র আর স্তর-সিমুলেশন brute মিলিয়ে দেখা (negative ও `(0,0)` সহ) — সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
True
False
সব test pass!
```
প্রথম লাইন: `reachable(2,1,3)` → dry run-এ পাওয়া True (d=3, s−d=0 জোড়)। দ্বিতীয়: `reachable(2,1,4)` → False (s−d=1 বিজোড়, parity মেলে না)। তার আগের সব `assert` (হাতে বাছা edge case + 3000টা random cross-check) চুপচাপ pass। সবশেষে `সব test pass!` — parity সূত্র প্রতিটা কেসে সিমুলেশনের সাথে মিলেছে।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(1)** — কয়েকটা absolute, একটা যোগ, একটা তুলনা আর একটা `% 2`। `s`, `x`, `y` যত বড়ই হোক কাজ বাড়ে না। (brute সিমুলেশনের O(s³)-এর তুলনায় আকাশ-পাতাল — পথ ঘোরার বদলে সরাসরি গণিত।)
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু `d` আর কয়েকটা মান; কোনো set, array বা grid লাগছে না। (brute reference-এ সম্ভাব্য ঘরের set O(s²) জায়গা নেয়, কিন্তু আসল সমাধান ধ্রুবক।)
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **parity শর্ত ভুলে যাওয়া** — শুধু `s >= d` চেক করলে ভুল; `(s − d)` জোড় হওয়াও লাগবেই (নইলে `(2,1)`-এ 4 ধাপ ভুল করে True হবে)।
2. **`(0,0)`-এ ফেরা ভুল ভাবা** — শুরুর ঘরে 1 ধাপে থাকা যায় না (এক ধাপ সরতেই হবে); d=0 হলেও parity লাগে, তাই বিজোড় s-এ False।
3. **কোনাকুনি চলন ধরে নেওয়া** — এই নিয়ম 4-দিক (Manhattan) চলনের; 8-দিক (রাজা) হলে দূরত্ব Chebyshev হয়, শর্ত বদলায়।
4. **negative coordinate ভুল** — `abs` নিতে ভুলো না; `d = |x| + |y|`, `x + y` নয় (parity এক হলেও দূরত্ব আলাদা)।
5. **strict "ঠিক s" বনাম "≤ s" গুলিয়ে ফেলা** — এখানে **ঠিক** s ধাপ; "অন্তত s" বা "≤ s ধাপে পৌঁছানো" হলে শর্ত আলাদা হতো (শুধু `s >= d`)।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Reachable Nodes With Restrictions / grid BFS variants** — গ্রিড-চলনে parity ও দূরত্ব invariant একই পরিবার।
- **Codeforces — Theatre Square** (