Problem link ও উৎস
- **Original source:** Constructive algorithms — build a valid answer or prove impossible via invariant
- **Platform:** Codeforces constructive tag —
- **Topic:** Math-based programming fundamentals → Level 11: Hard Mixed CP Patterns
- **Difficulty:** Hard
- **Pattern:** build + invariant (construction বা parity-proof)
- **Basic idea inherited from:** — (constructive আলাদা শাখা; invariant-চিন্তা level জুড়ে)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা concrete constructive problem নিই: সংখ্যা `1, 2, 3, ..., n` — এদের **দুই দলে** ভাগ করতে চাই যেন **দুই দলের যোগফল সমান** হয়। সম্ভব হলে একটা ভাগ দেখাও; অসম্ভব হলে বলো "impossible" (আর কেন, প্রমাণসহ)।
উদাহরণ:
- `n = 3`: যোগফল `1+2+3 = 6`, প্রতি দল 3 → `{3}` আর `{1, 2}`। সম্ভব।
- `n = 4`: যোগফল 10, প্রতি দল 5 → `{4, 1}` আর `{2, 3}`। সম্ভব।
- `n = 2`: যোগফল 3 — বিজোড়, সমান দুই ভাগ অসম্ভব। **Impossible**।
মূল কাজ দুটো: কখন সম্ভব সেটা চেনা (একটা সহজ শর্ত), আর সম্ভব হলে আসল ভাগটা **বানানো**।
> এটা CP-leaning level। Interview-পথে থাকলে এড়িয়ে মূল DS topic-এ যেতে পারো; এতদিনের invariant-চিন্তা এখানে fresh মাথায় উপভোগ করবে।
### Input ও output {#6-example-input-and-output}
```text
n সম্ভব? একটা ভাগ (দল A | দল B)
-----------------------------------------------------
1 না — (যোগফল 1, বিজোড়)
2 না — (যোগফল 3, বিজোড়)
3 হ্যাঁ {3} | {1, 2}
4 হ্যাঁ {4, 1} | {2, 3}
7 হ্যাঁ {7, 6, 1} | {2, 3, 4, 5}
8 হ্যাঁ {8, 7, 3} | {1, 2, 4, 5, 6}
n % 4: 0 বা 3 -> সম্ভব; 1 বা 2 -> impossible
```
মূল edge case: `n = 1, 2` impossible (যোগফল বিজোড়); আর construction-এ ভাগ একাধিক হতে পারে — যেকোনো একটা বৈধ ভাগ দেখালেই চলে।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তোমার কাছে বিভিন্ন ওজনের `n`টা বাটখারা (1, 2, ..., n গ্রাম), আর একটা দুই-পাল্লার দাঁড়িপাল্লা। তুমি সব বাটখারা দুই পাল্লায় ভাগ করে **ভারসাম্য** আনতে চাও।
প্রথমেই একটা সহজ চেক: মোট ওজন যদি বিজোড় হয়, কোনোভাবেই সমান দুই ভাগ হবে না — পাল্লা ছোঁয়ার আগেই তুমি "impossible" বলে দিতে পারো (এটাই invariant-প্রমাণ, parity দিয়ে)। মোট ওজন জোড় হলে তবেই হাতে লেগে পড়ো — সবচেয়ে ভারীটা এক পাল্লায় রেখে, লক্ষ্য-অর্ধেক পূরণ না হওয়া পর্যন্ত পরের ভারীগুলো যোগ করতে থাকো (এটাই construction)। মূল শিক্ষা: আগে invariant দিয়ে সম্ভব কিনা বুঝে নাও, তারপর বানাও।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
Constructive একটা আলাদা শাখা (তাই inherited from: —), কিন্তু এর **invariant-চিন্তা** পুরো math fundamentals জুড়ে ছড়ানো। Level 9-এর grid parity (problem 123) ছিল একই পরিবারের — সেখানেও parity দিয়ে "অসম্ভব" প্রমাণ। Level 0-এর even/odd থেকে শুরু করে যত জায়গায় "শেষ bit / জোড়-বিজোড়" দেখেছ — সব এখানে এসে invariant-অস্ত্রে রূপ নেয়।
নতুন যেটা: দুই মোড **একসাথে** চালানো — হয় বানাও, নয় অসম্ভব প্রমাণ করো; আর কোনটা কখন তা parity invariant দিয়ে ঠিক করা। এটা পুরো level-এর invariant-অভিজ্ঞতার চূড়ান্ত প্রয়োগ — তাই একে শেষ boss বলা।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
দুটো ধারণা একসাথে — **construction** আর **invariant**:
```text
Builder মোড: ছোট case হাতে বানাও -> pattern খোঁজো -> general construction
Prover মোড: একটা invariant খোঁজো (যে রাশি কোনো বৈধ উত্তরে বদলায় না);
শুরু আর লক্ষ্যে সেই রাশি না মিললে -> impossible, প্রমাণসহ
```
এই problem-এ মূল invariant **parity (জোড়/বিজোড়)**: দুই সমান দলে ভাগ করতে হলে মোট যোগফল `1+2+...+n = n(n+1)/2` অবশ্যই **জোড়** হতে হবে (নাহলে অর্ধেক পূর্ণসংখ্যা হয় না)। `n(n+1)/2` জোড় ⟺ `n % 4 ∈ {0, 3}`। এই শর্ত মিটলে construction সম্ভব, না মিটলে impossible — parity-ই বিচারক।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
Parity invariant না জেনে — সব subset চেষ্টা করো: কোনো subset-এর যোগফল মোটের অর্ধেক কিনা দেখো (subset-sum):
```python
def can_split_brute(n):
total = n * (n + 1) // 2
if total % 2 != 0:
return False
target = total // 2
reachable = {0}
for v in range(1, n + 1): # প্রতিটা সংখ্যা যোগ করার চেষ্টা
reachable |= {s + v for s in reachable}
return target in reachable # অর্ধেক বানানো যায়?
```
এটা subset-sum feasibility — ঠিক উত্তর দেয় (`can_split_brute(3)` → True)। আর parity-শর্ত যাচাইয়ের নিখুঁত মাপকাঠি। কিন্তু subset-sum সাধারণভাবে exponential/pseudo-polynomial।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
Subset-sum-এর `reachable` set বড় হতে পারে (`target` পর্যন্ত মান), আর সাধারণ subset-sum NP-ঘরানা:
```text
target = n(n+1)/4 প্রায় n² মাপের -> reachable set ~O(n²)
প্রতি সংখ্যায় set আপডেট -> O(n · n²) = O(n³) (এই বিশেষ case-এ)
সাধারণ subset-sum -> exponential worst case
invariant + construction: O(1) সিদ্ধান্ত (n % 4), O(n) construction
```
মূল কথা — এই problem-এ পুরো subset-sum চালানোই অপ্রয়োজনীয়; parity invariant `O(1)`-এ সিদ্ধান্ত দেয়, আর greedy `O(n)`-এ ভাগ বানায়। invariant চিনলে exponential খরচ পুরো এড়ানো যায়।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight (দুই মোড):
- **Prover (কখন impossible):** মোট যোগফল `n(n+1)/2` বিজোড় হলে সমান দুই ভাগ অসম্ভব — এটাই parity invariant। `n(n+1)/2` জোড় ⟺ `n % 4 ∈ {0, 3}`।
- **Builder (কীভাবে বানানো):** শর্ত মিটলে greedy — লক্ষ্য `target = total/2`; সবচেয়ে বড় সংখ্যা থেকে শুরু করে, `target` না ছাড়িয়ে যতটা যোগ করা যায় দল A-তে রাখো। বাকিরা দল B। (বড়-থেকে-greedy এখানে সবসময় target ছোঁয় — কারণ ছোট সংখ্যাগুলো ফাঁক ভরাট করে।)
আগে invariant দিয়ে সম্ভব কিনা জানো, তারপরই বানাও — এটাই constructive-এর সঠিক ক্রম।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
এক লাইনের "আহা": **"বানাও বা impossible বলো" দেখলে দুই মোড একসাথে চালাও — আগে invariant (সবার আগে parity!) দিয়ে সম্ভব কিনা ঠিক করো, তারপর pattern/greedy দিয়ে আসল উত্তর বানাও।**
সবচেয়ে বড় ফাঁদ: **এক case-এ আটকে general "impossible" দাবি করা** (concept-notes mistake #9)। `n = 5`-এ পারোনি মানেই সব impossible না; impossible বলতে হলে একটা invariant-প্রমাণ লাগবে (এখানে parity)। আর checklist মনে রাখো — আটকে গেলে: parity দেখো → sum/XOR invariant দেখো → ছোটতম impossible case খোঁজো → general করো।
### ছবিতে বোঝা {#5-visual-explanation}
কখন সম্ভব (parity invariant) আর কীভাবে বানানো:
```text
মোট যোগফল = n(n+1)/2; সমান দুই ভাগ চাইলে এটা জোড় হতে হবে
n : 1 2 3 4 5 6 7 8
যোগ: 1 3 6 10 15 21 28 36
জোড়? না না হ্যাঁ হ্যাঁ না না হ্যাঁ হ্যাঁ
সম্ভব? ✗ ✗ ✓ ✓ ✗ ✗ ✓ ✓
^ pattern: n % 4 ∈ {0, 3}
construction (n = 4, লক্ষ্য অর্ধেক = 5), greedy বড় থেকে:
4 ≤ 5 ? হ্যাঁ -> দল A = {4}, যোগ 4
3, 4+3=7 > 5 ? হ্যাঁ -> বাদ
2, 4+2=6 > 5 ? হ্যাঁ -> বাদ
1, 4+1=5 ≤ 5 ? হ্যাঁ -> দল A = {4, 1}, যোগ 5 ✓
দল B = বাকি = {2, 3}, যোগ 5 ✓
```
লক্ষ করো — প্রথমে parity বলে দিল সম্ভব কিনা; তারপর greedy construction আসল ভাগটা বানাল।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`n = 7` — দুই মোড হাতে চালাই:
1. **Prover:** মোট `7·8/2 = 28` — জোড়! তাই সম্ভব (`7 % 4 = 3 ∈ {0,3}` ✓)। লক্ষ্য `target = 14`।
2. **Builder (greedy বড় থেকে):**
- 7: `0 + 7 = 7 ≤ 14` → A = {7}, যোগ 7।
- 6: `7 + 6 = 13 ≤ 14` → A = {7, 6}, যোগ 13।
- 5: `13 + 5 = 18 > 14` → বাদ।
- 4: `13 + 4 = 17 > 14` → বাদ।
- 3: `13 + 3 = 16 > 14` → বাদ।
- 2: `13 + 2 = 15 > 14` → বাদ।
- 1: `13 + 1 = 14 ≤ 14` → A = {7, 6, 1}, যোগ 14 ✓।
3. **দল B:** বাকি = {2, 3, 4, 5}, যোগ `2+3+4+5 = 14` ✓।
4. **ফল:** `{7, 6, 1}` আর `{2, 3, 4, 5}` — দুই দলেরই যোগফল 14।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def can_split_equal(n):
"""1..n সমান দুই দলে ভাগ করা সম্ভব কি — parity invariant।"""
total = n * (n + 1) // 2
return total % 2 == 0 # জোড় ⟺ n % 4 ∈ {0, 3}
def build_split(n):
"""সম্ভব হলে (দল A, দল B) সমান যোগফলে ফেরত; নাহলে None।"""
total = n * (n + 1) // 2
if total % 2 != 0:
return None # invariant: impossible
target = total // 2
group_a, s = [], 0
for v in range(n, 0, -1): # greedy: বড় থেকে ছোট
if s + v <= target:
group_a.append(v)
s += v
in_a = set(group_a)
group_b = [v for v in range(1, n + 1) if v not in in_a]
return group_a, group_b
def can_split_brute(n):
"""subset-sum দিয়ে যাচাই — invariant-শর্ত ঠিক কিনা।"""
total = n * (n + 1) // 2
if total % 2 != 0:
return False
target = total // 2
reachable = {0}
for v in range(1, n + 1):
reachable |= {s + v for s in reachable}
return target in reachable
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert can_split_equal(3) is True
assert can_split_equal(4) is True
assert can_split_equal(2) is False # যোগফল 3, বিজোড়
assert can_split_equal(1) is False
# parity-শর্ত আর subset-sum (স্বাধীন পথ) মেলে — invariant-এর প্রমাণ
for n in range(1, 25):
assert can_split_equal(n) == can_split_brute(n), n
# আর n % 4 ∈ {0,3} এর সাথেও মেলে
assert can_split_equal(n) == (n % 4 in (0, 3)), n
# construction সঠিক: দুই দল মিলে 1..n, যোগফল সমান
for n in range(1, 30):
res = build_split(n)
if can_split_equal(n):
a, b = res
assert sorted(a + b) == list(range(1, n + 1)), n # সব সংখ্যা একবার
assert sum(a) == sum(b), n # যোগফল সমান
else:
assert res is None, n
print(can_split_equal(7), build_split(7)) # True ([7, 6, 1], [2, 3, 4, 5])
print(can_split_equal(2), build_split(2)) # False None
print([n for n in range(1, 13) if can_split_equal(n)]) # [3,4,7,8,11,12]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
total = n * (n + 1) // 2
return total % 2 == 0
```
এটাই Prover মোড — মোট যোগফল `n(n+1)/2`; জোড় হলেই কেবল সমান দুই ভাগ সম্ভব (parity invariant)। বিজোড় হলে অর্ধেক পূর্ণসংখ্যা নয়, তাই impossible।
```text
target = total // 2
for v in range(n, 0, -1):
if s + v <= target:
group_a.append(v)
s += v
```
Builder মোড — greedy বড় থেকে ছোট। লক্ষ্য `target = total/2`; প্রতিটা সংখ্যা যদি দল A-র যোগফলকে `target`-এর বেশি না করে, তবে A-তে যোগ করি। বড় সংখ্যা আগে নেওয়ায় ছোটগুলো বাকি ফাঁক ঠিক ভরে দেয় — তাই `target` সবসময় ছোঁয়।
```text
group_b = [v for v in range(1, n + 1) if v not in in_a]
```
দল A-তে যা নেই, সব দল B-তে। দুই দল মিলে পুরো `1..n`, আর A-র যোগফল `target` হওয়ায় B-র যোগফলও `target`।
বাকি `can_split_brute` subset-sum দিয়ে স্বাধীনভাবে যাচাই করে, আর `assert` গুলো তিনভাবে মিলিয়ে দেখে: (১) parity-শর্ত vs subset-sum, (২) `n % 4` pattern, (৩) construction সত্যিই সমান-যোগফলের বৈধ ভাগ দেয়। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
True ([7, 6, 1], [2, 3, 4, 5])
False None
[3, 4, 7, 8, 11, 12]
সব test pass!
```
প্রথম লাইন `n=7` সম্ভব, একটা ভাগ `{7,6,1}` | `{2,3,4,5}` (দুই দলই যোগফল 14)। দ্বিতীয় `n=2` impossible (None)। তৃতীয় — 1..12-এর মধ্যে যেগুলোয় সম্ভব (`n % 4 ∈ {0,3}`)। তার আগের সব `assert` চুপচাপ pass — parity invariant, subset-sum, `n%4`, আর construction সব একমত। সবশেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
সিদ্ধান্ত (সম্ভব কিনা): **O(1)** — শুধু `n(n+1)/2`-এর parity। Construction: **O(n)** — একবার বড়-থেকে-ছোট হেঁটে greedy ভাগ। brute force ছিল subset-sum (pseudo-polynomial/exponential) — invariant চিনে সেই খরচ পুরো এড়ানো গেল।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(n)** — দল A আর B-র list (মোট `n`টা সংখ্যা)। সিদ্ধান্ত-অংশ `O(1)`। brute version `reachable` set-এ `O(target) = O(n²)` নেয় — invariant সেটাও বাঁচায়।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **এক case-এ আটকে general "impossible" দাবি** — পারোনি ≠ impossible; invariant-প্রমাণ লাগবে (concept-notes mistake #9)।
2. **Parity invariant না খোঁজা** — constructive-এ আটকে গেলে সবার আগে parity (তারপর sum/XOR) দেখো; এটাই সবচেয়ে সাধারণ invariant।
3. **Construction যাচাই না করা** — বানানো উত্তর সত্যিই সব শর্ত মানে কিনা (এখানে: দুই দল মিলে 1..n, যোগফল সমান) কোড দিয়ে চেক করো।
4. **Greedy অন্ধভাবে বিশ্বাস** — সব constructive-এ greedy খাটে না; এই বিশেষ problem-এ (consecutive 1..n) খাটে, কিন্তু কেন খাটে সেটা বোঝো।
5. **শর্ত আর construction গুলিয়ে ফেলা** — আগে invariant দিয়ে সম্ভব কিনা ঠিক করো, তারপর বানাও; ক্রম উল্টে ফেললে অসম্ভব case-এ ভুল আউটপুট।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **Codeforces — constructive algorithms tag** (