Problem link ও উৎস
- **Original source:** Classic CP trick (Manhattan ↔ Chebyshev rotation)
- **Platform:** — (classic competitive programming technique)
- **Topic:** Math-based programming fundamentals → Level 9: Geometry & Coordinate Math
- **Difficulty:** Medium
- **Pattern:** 45° rotation (coordinate ঘুরিয়ে Manhattan-কে Chebyshev বানানো)
- **Basic idea inherited from:** 113 — Distance Between Points
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো বিন্দুর **Manhattan distance** হলো `|x1 − x2| + |y1 − y2|` — অর্থাৎ গ্রিড ধরে (শুধু আড়াআড়ি-খাড়া, কোনাকুনি নয়) হাঁটলে যত ঘর পেরোতে হয়। এটা নিজে সহজ। আসল মজা শুরু হয় যখন অনেক বিন্দু থাকে আর জিজ্ঞেস করা হয়:
> `n`টা বিন্দুর মধ্যে যেকোনো দুটোর সর্বোচ্চ Manhattan distance কত?
সরল উপায় — প্রতিটা জোড়া ধরে দূরত্ব মাপা, O(n²)। কিন্তু একটা চমৎকার coordinate-trick দিয়ে এটা O(n)-এ নামানো যায়। এই note-এ আমরা trick-টা শিখব, তারপর সেটা দিয়ে "max pairwise Manhattan distance" দ্রুত বের করব।
মনে রাখো — Manhattan distance-এ ওই `+` চিহ্নটাই (দুটো absolute যোগ) সব জোড়া একসাথে optimize করা কঠিন করে; trick-টা সেই `+`-কে সরিয়ে দেয়।
### Input ও output {#6-example-input-and-output}
```text
দুই-বিন্দু Manhattan:
(1,2),(4,6) -> 7 (3 + 4)
(0,0),(0,0) -> 0 (একই বিন্দু)
(-1,-1),(2,3) -> 7 (3 + 4)
max pairwise Manhattan (বিন্দুর তালিকা):
[(0,0),(4,0),(0,4),(2,2)] -> 8 ((4,0)–(0,4))
[(1,1),(1,1)] -> 0 (সব একই)
[(0,0),(10,0)] -> 10 (এক জোড়া)
[(-5,-5),(5,5),(0,0)] -> 20 ((-5,-5)–(5,5): 10+10)
```
মূল edge case: **একই বিন্দু** (দূরত্ব 0), **negative coordinate** (absolute নিলে ঠিকই কাজ করে), আর **সব বিন্দু একই** (max pairwise 0)। trick-এ negative নিয়ে ভয় নেই — `u, v` negative হলেও range (max − min) ঠিক থাকে।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা শহরের রাস্তা সব উত্তর-দক্ষিণ আর পূর্ব-পশ্চিম বরাবর (গ্রিড শহর, যেমন ম্যানহাটান — তাই নাম!)। দুই জায়গার মধ্যে ট্যাক্সিকে শুধু রাস্তা ধরে যেতে হয়, কোনাকুনি বাড়ির ভেতর দিয়ে নয় — তাই দূরত্ব `|Δx| + |Δy|`।
এবার ভাবো একজন মানুষ যে শুধু **কোনাকুনি (diagonal)** হাঁটতে পারে, আর আড়াআড়ি/খাড়াও — অর্থাৎ রাজার মতো আট দিকে এক ঘর (Chebyshev)। তার কাছে দূরত্ব `max(|Δx|, |Δy|)`। trick-টা বলছে: ট্যাক্সির শহরের মানচিত্রটা যদি তুমি ঠিক 45° কাত করে ধরো, তাহলে ট্যাক্সির গ্রিড-দূরত্ব দেখতে হবে অবিকল রাজার কোনাকুনি-দূরত্বের মতো। মানে একই দূরত্ব, শুধু চোখটা 45° ঘুরিয়ে দেখলে হিসাবটা সহজ হয়ে যায় — যোগের ঝামেলা মিলিয়ে গিয়ে দুটো স্বাধীন max হয়ে যায়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা দাঁড়িয়ে আছে **113 — Distance Between Points**-এর উপর। 113-এ তুমি দূরত্বের ভিত্তি (Euclidean squared distance, আর coordinate পার্থক্য `Δx, Δy`) শিখেছিলে। এখানে সেই coordinate-পার্থক্যের ধারণাকেই একটা **নতুন coordinate system**-এ নিয়ে যাচ্ছি — distance-এর সংজ্ঞা একই রকম থাকছে, শুধু অক্ষ দুটো 45° ঘুরে যাচ্ছে।
নতুন যেটা যোগ হলো — Manhattan vs Chebyshev-এর সম্পর্ক, আর coordinate transform-কে একটা সমস্যা-সরলীকরণের হাতিয়ার হিসেবে ব্যবহার করা। এই "অক্ষ ঘুরিয়ে সমস্যা সহজ করা" চিন্তাটা 122 (Rotate Matrix)-এও ফিরবে অন্য মোড়কে। তাই 113-এর distance-ভিত্তি + একটা চালাক রূপান্তর = এই problem।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল গাণিতিক রূপান্তর — প্রতিটা বিন্দু `(x, y)`-কে নতুন coordinate-এ পাঠাও: **`u = x + y`, `v = x − y`** (এটাই 45° ঘোরানো + scaling)। তখন আশ্চর্য সত্য:
> Manhattan distance `|Δx| + |Δy|` = Chebyshev distance `max(|Δu|, |Δv|)`।
কেন? `|Δx| + |Δy|` সবসময় `max(|Δx + Δy|, |Δx − Δy|)`-এর সমান (চারটে চিহ্ন-সমন্বয় খুলে দেখলেই মেলে)। আর `Δu = Δx + Δy`, `Δv = Δx − Δy` — তাই `max(|Δu|, |Δv|)`।
এর বড় লাভ: Chebyshev distance-এ `u` আর `v` **আলাদা আলাদা** optimize করা যায় (max আর min independent), কিন্তু Manhattan-এ যোগের কারণে তা যেত না। তাই max pairwise Manhattan = `max( max(u) − min(u), max(v) − min(v) )` — সব বিন্দু একবার ঘেঁটে u, v-এর max/min বের করলেই হলো, O(n)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরল চিন্তা — সব জোড়া বিন্দু ধরো, প্রতিটার Manhattan distance মাপো, সবচেয়ে বড়টা রাখো:
```python
def max_pair_brute(points):
n = len(points)
best = 0
for i in range(n):
for j in range(i + 1, n):
d = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
best = max(best, d)
return best
```
এটা প্রতিটা জোড়া পরীক্ষা করে, তাই নিশ্চিত ঠিক উত্তর — asserts-এ এটাই reference। ছোট তালিকায় চমৎকার ও পড়তে সহজ।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
জোড়ার সংখ্যা `n(n−1)/2` — O(n²)। `n = 100000` হলে প্রায় 500 কোটি জোড়া, contest-এ নিশ্চিত Time Limit Exceeded।
```text
n = 100000 হলে:
brute (সব জোড়া): ~5,000,000,000 distance হিসাব (ধীর, O(n^2))
rotation trick : ~100,000 × 2 ধাপ (O(n), এক pass-এ u,v range)
```
মূল অপচয় — আমরা সব জোড়া আলাদা করে দেখছি, যেখানে max distance আসলে নির্ভর করে শুধু কয়েকটা "প্রান্তিক" বিন্দুর উপর (u বা v-তে সবচেয়ে বড়/ছোট)। Manhattan-এর `+` চিহ্নের কারণে সরাসরি সেই প্রান্ত ধরা যায় না — কিন্তু 45° ঘুরিয়ে দিলে যায়, কারণ তখন u আর v স্বাধীন।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — `(x, y) -> (u, v) = (x + y, x − y)` রূপান্তরে Manhattan = Chebyshev, আর Chebyshev-এ u, v আলাদা optimize হয়। তাই দুই-বিন্দুর দূরত্ব এক সূত্রে, আর max pairwise এক pass-এ:
```python
def manhattan(p, q):
return abs(p[0] - q[0]) + abs(p[1] - q[1])
def max_pair_manhattan(points):
us = [x + y for x, y in points]
vs = [x - y for x, y in points]
return max(max(us) - min(us), max(vs) - min(vs))
```
`us` আর `vs` বানাতে O(n), তাদের max/min বের করতে O(n)। সব মিলিয়ে O(n) — O(n²) থেকে বিশাল লাফ। (একই trick 3D/higher-D-তেও বাড়ে, প্রতিটা চিহ্ন-সমন্বয়ের জন্য একটা অক্ষ।)
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "magic" — **Manhattan distance-এর `|Δx| + |Δy|` (যোগ) = `max(|Δx + Δy|, |Δx − Δy|)` (দুই স্বাধীন রাশির max)।** এই সমতাটাই গোটা trick।
কেন এটা শক্তিশালী? "যোগফল max করা" সব জোড়াকে একসাথে বাঁধে (একটা বিন্দুর x বড় হলেও y ছোট হলে যোগফল মাঝারি), তাই সহজে প্রান্ত ধরা যায় না। কিন্তু `max(|u|, |v|)`-এ u আর v আলাদা — তাই max distance = u-এর সবচেয়ে দূর জোড়া বা v-এর সবচেয়ে দূর জোড়া, যা শুধু চারটে প্রান্তিক মান (max u, min u, max v, min v) দেখলেই পাওয়া যায়। "Manhattan + অনেক বিন্দু + max/min খুঁজতে হবে" দেখলেই এই 45° রূপান্তর মাথায় আসুক।
### ছবিতে বোঝা {#5-visual-explanation}
প্রথমে Manhattan distance কী, একটা ছবি — গ্রিড ধরে হাঁটা:
```text
Manhattan distance (1,2) থেকে (4,6):
y=6 ........... B(4,6)
y=5 . .
y=4 . . |Δx| = |4-1| = 3
y=3 . . |Δy| = |6-2| = 4
y=2 A(1,2) ----+ distance = 3 + 4 = 7
x=1 x=4 (কোনাকুনি নয়, ধাপে ধাপে)
```
এবার 45° রূপান্তরের ছবি — `(x,y) -> (u,v) = (x+y, x-y)`:
```text
পুরোনো অক্ষ (x,y) 45° ঘুরিয়ে নতুন অক্ষ (u,v)
y v u
| /diamond\ \ /
| / \ ===> X u = x + y (এক কর্ণ বরাবর)
| / Manhattan / \ v = x - y (অন্য কর্ণ বরাবর)
| / "বল" (◇)
+---------- x Manhattan-এর হীরে (◇) -> Chebyshev-এর বর্গ (□)
সূত্র: |Δx| + |Δy| = max(|Δu|, |Δv|)
```
max pairwise distance কীভাবে O(n)-এ — শুধু u আর v-এর range:
```text
বিন্দু: (0,0) (4,0) (0,4) (2,2)
u=x+y: 0 4 4 4 -> max(u)-min(u) = 4-0 = 4
v=x-y: 0 4 -4 0 -> max(v)-min(v) = 4-(-4) = 8
max pairwise Manhattan = max(4, 8) = 8 (যেমন (4,0) ও (0,4): 4+4=8)
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`points = [(0,0), (4,0), (0,4), (2,2)]`-এ max pairwise Manhattan বের করি:
1. শুরু: প্রতিটা বিন্দুর `u = x + y` আর `v = x − y` হিসাব করি।
2. `us` = `[0+0, 4+0, 0+4, 2+2]` = `[0, 4, 4, 4]`।
3. `vs` = `[0−0, 4−0, 0−4, 2−2]` = `[0, 4, −4, 0]`।
4. u-এর range: `max(us) − min(us)` = `4 − 0` = 4।
5. v-এর range: `max(vs) − min(vs)` = `4 − (−4)` = 8।
6. উত্তর: `max(4, 8)` = **8**।
যাচাই: v-তে সবচেয়ে দূর জোড়া হলো max v (=4, বিন্দু (4,0)) আর min v (=−4, বিন্দু (0,4))। তাদের Manhattan = `|4−0| + |0−4|` = `4 + 4` = 8 — মিলে গেল, brute force-এর সাথেও।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def manhattan(p, q):
"""দুই বিন্দুর Manhattan distance |Δx| + |Δy|।"""
return abs(p[0] - q[0]) + abs(p[1] - q[1])
def manhattan_via_rotation(p, q):
"""একই দূরত্ব, 45° রূপান্তরে: max(|Δu|, |Δv|), u=x+y, v=x-y।"""
pu, pv = p[0] + p[1], p[0] - p[1]
qu, qv = q[0] + q[1], q[0] - q[1]
return max(abs(pu - qu), abs(pv - qv))
def max_pair_manhattan(points):
"""n বিন্দুর মধ্যে সর্বোচ্চ pairwise Manhattan distance — O(n)।"""
us = [x + y for x, y in points]
vs = [x - y for x, y in points]
return max(max(us) - min(us), max(vs) - min(vs))
def max_pair_brute(points):
"""সব জোড়া পরীক্ষা — reference (O(n^2))।"""
n = len(points)
best = 0
for i in range(n):
for j in range(i + 1, n):
best = max(best, manhattan(points[i], points[j]))
return best
# --- দুই-বিন্দু test (সরল ও rotation দুটো মেলে) ---
assert manhattan((1, 2), (4, 6)) == 7
assert manhattan((0, 0), (0, 0)) == 0
assert manhattan((-1, -1), (2, 3)) == 7
assert manhattan_via_rotation((1, 2), (4, 6)) == 7
assert manhattan_via_rotation((-1, -1), (2, 3)) == 7
# --- max pairwise test ---
assert max_pair_manhattan([(0, 0), (4, 0), (0, 4), (2, 2)]) == 8
assert max_pair_manhattan([(1, 1), (1, 1)]) == 0
assert max_pair_manhattan([(0, 0), (10, 0)]) == 10
assert max_pair_manhattan([(-5, -5), (5, 5), (0, 0)]) == 20
# --- cross-check: rotation == সরল, আর fast == brute (random) ---
import random
random.seed(1)
for _ in range(5000):
p = (random.randint(-30, 30), random.randint(-30, 30))
q = (random.randint(-30, 30), random.randint(-30, 30))
assert manhattan(p, q) == manhattan_via_rotation(p, q), (p, q)
for _ in range(3000):
n = random.randint(2, 8)
pts = [(random.randint(-20, 20), random.randint(-20, 20)) for _ in range(n)]
assert max_pair_manhattan(pts) == max_pair_brute(pts), pts
print(manhattan((1, 2), (4, 6))) # 7
print(max_pair_manhattan([(0, 0), (4, 0), (0, 4), (2, 2)])) # 8
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
def manhattan(p, q):
return abs(p[0] - q[0]) + abs(p[1] - q[1])
```
সরাসরি সংজ্ঞা — x-পার্থক্য আর y-পার্থক্যের absolute যোগ। এটাই "গ্রিড ধরে হাঁটার" দূরত্ব।
```text
pu, pv = p[0] + p[1], p[0] - p[1]
...
return max(abs(pu - qu), abs(pv - qv))
```
প্রতিটা বিন্দুকে `(u, v) = (x + y, x − y)`-তে পাঠাই (45° রূপান্তর)। নতুন coordinate-এ Manhattan = Chebyshev = দুই অক্ষের পার্থক্যের max। এটা `manhattan`-এর সমান উত্তর দেয় (cross-check তাই প্রমাণ করে)।
```text
us = [x + y for x, y in points]; vs = [x - y for x, y in points]
return max(max(us) - min(us), max(vs) - min(vs))
```
max pairwise distance-এর মূল চাল। সব বিন্দুর u আর v আলাদা list-এ রাখি। Chebyshev-এ u, v স্বাধীন বলে — সর্বোচ্চ দূরত্ব হয় u-অক্ষে সবচেয়ে দূর জোড়া (`max u − min u`) বা v-অক্ষে সবচেয়ে দূর জোড়া (`max v − min v`), দুটোর বড়টা। এক pass-এ চারটে প্রান্তিক মান বের করলেই উত্তর।
cross-check অংশে 5000 জোড়ায় দুই সূত্র, আর 3000 তালিকায় fast vs brute মিলিয়ে দেখা — সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
7
8
সব test pass!
```
প্রথম লাইন: `manhattan((1,2),(4,6))` = `3 + 4` = 7। দ্বিতীয়: `max_pair_manhattan([(0,0),(4,0),(0,4),(2,2)])` → dry run-এ পাওয়া 8 ((4,0)–(0,4) জোড়া)। তার আগের সব `assert` (দুই-বিন্দু + max pairwise + 8000টা random cross-check) চুপচাপ pass। সবশেষে `সব test pass!` — rotation trick সরল হিসাবের সাথে সর্বত্র মিলেছে।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
দুই-বিন্দু distance: **O(1)** — কয়েকটা বিয়োগ ও যোগ। max pairwise: **O(n)** — u, v list বানানো O(n), max/min বের করা O(n)। brute-এর O(n²) থেকে বিশাল সাশ্রয়, কারণ আর প্রতিটা জোড়া ছুঁই না, শুধু প্রান্তিক মান।
### অতিরিক্ত জায়গা {#16-space-complexity}
দুই-বিন্দু: **O(1)**। max pairwise: **O(n)** — `us` আর `vs` list রাখতে। চাইলে list না বানিয়ে এক pass-এ চারটে running max/min রেখে O(1) বাড়তি স্মৃতিতেও করা যায়। মূল গণনায় বাড়তি কিছু লাগে না।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **রূপান্তর ভুল লেখা** — সঠিক `u = x + y`, `v = x − y`। চিহ্ন উল্টে গেলে Chebyshev সমতা ভাঙে; দুই-বিন্দু cross-check দিয়ে যাচাই করো।
2. **max pairwise-এ শুধু এক অক্ষ দেখা** — `max(u)−min(u)` আর `max(v)−min(v)` দুটোরই বড়টা নিতে হবে; একটা বাদ দিলে কম উত্তর।
3. **negative coordinate ভয় পাওয়া** — `u, v` negative হলেও range (max − min) ঠিক; আলাদা handle লাগে না।
4. **Manhattan-কে Euclidean ভাবা** — `|Δx| + |Δy|` (গ্রিড) আর `√(Δx² + Δy²)` (সরলরেখা) আলাদা; এই trick শুধু Manhattan-এ খাটে।
5. **একই বিন্দুর জোড়া না ভাবা** — সব বিন্দু এক হলে max pairwise 0; brute-এ `i < j` ঠিক রাখো (নিজের সাথে জোড়া বাদ)।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **Codeforces — Watchmen** (