150 — Constructive Math Problems¶
শেষ boss! এই একটা problem পেরোলেই math fundamentals সম্পূর্ণ — অভিনন্দন আগেভাগেই। Constructive problem হলো সেই ঘরানা যেখানে তোমাকে নিজে একটা উত্তর বানিয়ে দিতে হয়, নয়তো invariant দিয়ে প্রমাণ করতে হয় কেন উত্তর অসম্ভব। এতদিনের সব parity/invariant-চিন্তা এখানে একসাথে কাজে লাগবে। মনে রাখো, এই level CP-leaning, interview-এর জন্য optional (repo-র plan অনুযায়ী)।
Source¶
- Original source: Constructive algorithms — build a valid answer or prove impossible via invariant
- Platform: Codeforces constructive tag — https://codeforces.com/problemset?tags=constructive+algorithms
- 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 জুড়ে)
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 মাথায় উপভোগ করবে।
2. What is the math idea?¶
দুটো ধারণা একসাথে — construction আর invariant:
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-ই বিচারক।
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 বলা।
4. Real-life analogy¶
ভাবো তোমার কাছে বিভিন্ন ওজনের nটা বাটখারা (1, 2, ..., n গ্রাম), আর একটা দুই-পাল্লার দাঁড়িপাল্লা। তুমি সব বাটখারা দুই পাল্লায় ভাগ করে ভারসাম্য আনতে চাও।
প্রথমেই একটা সহজ চেক: মোট ওজন যদি বিজোড় হয়, কোনোভাবেই সমান দুই ভাগ হবে না — পাল্লা ছোঁয়ার আগেই তুমি "impossible" বলে দিতে পারো (এটাই invariant-প্রমাণ, parity দিয়ে)। মোট ওজন জোড় হলে তবেই হাতে লেগে পড়ো — সবচেয়ে ভারীটা এক পাল্লায় রেখে, লক্ষ্য-অর্ধেক পূরণ না হওয়া পর্যন্ত পরের ভারীগুলো যোগ করতে থাকো (এটাই construction)। মূল শিক্ষা: আগে invariant দিয়ে সম্ভব কিনা বুঝে নাও, তারপর বানাও।
5. Visual explanation¶
কখন সম্ভব (parity invariant) আর কীভাবে বানানো:
মোট যোগফল = 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 আসল ভাগটা বানাল।
6. Example input and output¶
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-এ ভাগ একাধিক হতে পারে — যেকোনো একটা বৈধ ভাগ দেখালেই চলে।
7. Brute force thinking¶
Parity invariant না জেনে — সব subset চেষ্টা করো: কোনো subset-এর যোগফল মোটের অর্ধেক কিনা দেখো (subset-sum):
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-ঘরানা:
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 করো।
11. Step-by-step dry run¶
n = 7 — দুই মোড হাতে চালাই:
- Prover: মোট
7·8/2 = 28— জোড়! তাই সম্ভব (7 % 4 = 3 ∈ {0,3}✓)। লক্ষ্যtarget = 14। - 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 ✓। - দল B: বাকি = {2, 3, 4, 5}, যোগ
2+3+4+5 = 14✓। - ফল:
{7, 6, 1}আর{2, 3, 4, 5}— দুই দলেরই যোগফল 14।
12. Python solution¶
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¶
এটাই Prover মোড — মোট যোগফল n(n+1)/2; জোড় হলেই কেবল সমান দুই ভাগ সম্ভব (parity invariant)। বিজোড় হলে অর্ধেক পূর্ণসংখ্যা নয়, তাই impossible।
Builder মোড — greedy বড় থেকে ছোট। লক্ষ্য target = total/2; প্রতিটা সংখ্যা যদি দল A-র যোগফলকে target-এর বেশি না করে, তবে A-তে যোগ করি। বড় সংখ্যা আগে নেওয়ায় ছোটগুলো বাকি ফাঁক ঠিক ভরে দেয় — তাই target সবসময় ছোঁয়।
দল A-তে যা নেই, সব দল B-তে। দুই দল মিলে পুরো 1..n, আর A-র যোগফল target হওয়ায় B-র যোগফলও target।
বাকি can_split_brute subset-sum দিয়ে স্বাধীনভাবে যাচাই করে, আর assert গুলো তিনভাবে মিলিয়ে দেখে: (১) parity-শর্ত vs subset-sum, (২) n % 4 pattern, (৩) construction সত্যিই সমান-যোগফলের বৈধ ভাগ দেয়। সব মিললে সব test pass!।
14. Output walkthrough¶
চালালে ছাপবে:
প্রথম লাইন 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!।
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¶
- এক case-এ আটকে general "impossible" দাবি — পারোনি ≠ impossible; invariant-প্রমাণ লাগবে (concept-notes mistake #9)।
- Parity invariant না খোঁজা — constructive-এ আটকে গেলে সবার আগে parity (তারপর sum/XOR) দেখো; এটাই সবচেয়ে সাধারণ invariant।
- Construction যাচাই না করা — বানানো উত্তর সত্যিই সব শর্ত মানে কিনা (এখানে: দুই দল মিলে 1..n, যোগফল সমান) কোড দিয়ে চেক করো।
- Greedy অন্ধভাবে বিশ্বাস — সব constructive-এ greedy খাটে না; এই বিশেষ problem-এ (consecutive 1..n) খাটে, কিন্তু কেন খাটে সেটা বোঝো।
- শর্ত আর construction গুলিয়ে ফেলা — আগে invariant দিয়ে সম্ভব কিনা ঠিক করো, তারপর বানাও; ক্রম উল্টে ফেললে অসম্ভব case-এ ভুল আউটপুট।
18. Harder problems that inherit this idea¶
- Codeforces — constructive algorithms tag (https://codeforces.com/problemset?tags=constructive+algorithms) — হাজারো build-or-prove problem।
- Codeforces — Even Split / array construction (https://codeforces.com/problemset?tags=constructive+algorithms) — parity/sum invariant-এর নানা রূপ।
- 123 — Grid Parity (এই repo-র level 9) — একই পরিবারের invariant-প্রমাণ।
19. Pattern learned¶
Constructive math (build + invariant) — "বানাও বা impossible বলো" problem-এ দুই মোড একসাথে: Builder (ছোট case → pattern → general/greedy) আর Prover (invariant, সবার আগে parity — শুরু আর লক্ষ্যে না মিললে impossible)। আগে সম্ভব কিনা জানো, তারপর বানাও।
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "constructive = বানাও বা impossible প্রমাণ করো; সবার আগে parity invariant দেখো (এখানে n(n+1)/2 জোড় কিনা = n%4∈{0,3}), সম্ভব হলে greedy/pattern-এ বানাও। এক case-এ না পারা ≠ impossible — invariant লাগবে। এটাই শেষ boss — math fundamentals শেষ!"
পরের ধাপ → math fundamentals সম্পূর্ণ! এবার মূল data structures — arrays থেকে শুরু (../../02-arrays-and-strings/); আর এই level-এর probability DP / counting DP-র পূর্ণ রূপ ../../12-dynamic-programming/-এ। শিকড় → invariant-চিন্তা পুরো level জুড়ে, বিশেষত 123 — Grid Parity।
ফিরে দেখা: এই level-এর map → ../README.md · চিন্তার ছাঁচ → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি করা হয়নি — বরং "CP-style pattern" / "common interview pattern" বলা হয়েছে।