008 — Watermelon¶

Source¶

Original source: Codeforces problem 4A
Platform: Codeforces — https://codeforces.com/problemset/problem/4/A
Topic: math / array (parity warm-up)
Difficulty: Easy
Pattern: parity warm-up (modulo arithmetic)
Basic idea inherited from: Math fundamentals-এর modulo arithmetic — even/odd parity দিয়ে সিদ্ধান্ত

1. Problem in simple words¶

একটা পূর্ণসংখ্যা ওজন w দেওয়া। বলো এটাকে কি দুটো positive even (জোড়) অংশে ভাগ করা যায় — যেখানে দুই অংশই কমপক্ষে 2, দুটোই even, আর যোগ করলে w হয়। সম্ভব হলে True, নাহলে False।

w = 8 -> True   (যেমন 2 + 6, বা 4 + 4)
w = 2 -> False  (একমাত্র ভাগ 1 + 1, কিন্তু 1 even নয়)

2. Which basic idea does this inherit from?¶

ভিত math fundamentals-এর modulo / parity — w % 2 দিয়ে even/odd চেনা। দুটো even সংখ্যার যোগফল সবসময় even; তাই w even না হলে দুই even অংশে ভাঙা অসম্ভব। গভীরে: ../../01-math-based-programming-fundamentals/02-modular-arithmetic/।

3. What is the hidden math or logic?¶

লুকানো logic দুই ধাপে:

দুই even-এর যোগফল even → তাই w অবশ্যই even হতে হবে (w % 2 == 0)।
প্রতিটা অংশ positive even মানে কমপক্ষে 2, তাই w কমপক্ষে 2 + 2 = 4 হতে হবে (w > 2)।

দুটো শর্ত একসাথে মিললেই উত্তর হ্যাঁ। অর্থাৎ: w even এবং w > 2।

4. Which data structure is needed?¶

কোনো data structure লাগে না — শুধু একটা সংখ্যা আর একটা modulo check। O(1) সব দিক থেকে।

5. Why this data structure fits¶

এটা pure arithmetic decision — array, map, কিছুরই দরকার নেই। একটা % 2 আর একটা তুলনা constant time-এ উত্তর দেয়; কোনো loop বা storage লাগে না।

6. Real-life analogy¶

একটা তরমুজ দুই বন্ধুর মধ্যে এমনভাবে কাটতে চাও যেন দুজনেই জোড় সংখ্যক টুকরো পায় (গল্পের শর্ত: জোড় ভাগ = সুখী ভাগ)। খুব ছোট তরমুজ (2 টুকরো) হলে দুজনকে 1 করে দিতে হয় — বিজোড়, তাই হবে না। যথেষ্ট বড় আর মোট জোড় হলেই কেবল জোড়-জোড় ভাগ সম্ভব।

7. Visual explanation¶

w জোড় ভাগে ভাঙা যায় কিনা:

w=8:  even? হ্যাঁ (8%2=0)।  >2? হ্যাঁ।  -> True   (4 + 4)
w=4:  even? হ্যাঁ।          >2? হ্যাঁ।  -> True   (2 + 2)
w=2:  even? হ্যাঁ।          >2? না।    -> False  (শুধু 1+1)
w=3:  even? না (3%2=1)।                 -> False

8. Example input and output¶

Input : w = 8 -> True
Input : w = 4 -> True

Edge case 1 (সবচেয়ে ছোট জোড়): w = 2 -> False
Edge case 2 (বিজোড়):          w = 3 -> False

9. Brute force thinking¶

প্রথম সরল চিন্তা: 2 থেকে w-2 পর্যন্ত প্রতিটা সম্ভাব্য প্রথম অংশ a ধরো, দেখো a আর w-a দুটোই even কিনা।

for a in range(2, w-1):
    if a % 2 == 0 and (w - a) % 2 == 0:
        return True
return False

10. Why brute force is slow¶

এই loop O(w) — w বড় হলে অযথা অনেক ধাপ। অথচ parity-র নিয়ম বলেই দিচ্ছে: দুই even-এর যোগফল even, তাই পুরো loop চালানোর দরকার নেই — একটা % 2 check-ই যথেষ্ট।

11. Key observation¶

মূল observation: যদি w even হয় এবং w > 2 হয়, তাহলে 2 + (w-2) সবসময় একটা বৈধ ভাগ — কারণ w-2-ও তখন even আর ≥ 2। তাই আলাদা করে খোঁজার কিছু নেই; শুধু দুটো শর্ত মেলাও।

12. Optimized intuition¶

দুটো প্রশ্ন করো: w কি even? আর w কি 2-এর বড়? দুটোর উত্তরই হ্যাঁ হলে ভাঙা যায়, নাহলে যায় না। এক লাইনের boolean।

13. Thinking tweak¶

মোচড়: "সব ভাগ try করব" ভুলে গিয়ে parity-র নিয়ম মনে করো — "দুই even = even যোগফল।" তখন পুরো খোঁজা একটা w % 2 == 0 and w > 2-এ মিলিয়ে যায়।

14. Step-by-step dry run¶

Input w = 2:

w % 2 == 0? → 2 % 2 = 0, হ্যাঁ।
w > 2? → 2 > 2, না।
দুটো শর্ত একসাথে সত্য নয় → False। (ঠিক: 2-কে শুধু 1+1 করা যায়, যা even নয়।)

15. Python solution¶

def can_split(w):
    # দুটো positive even অংশে ভাঙা যায় iff w even এবং w > 2
    return w % 2 == 0 and w > 2

# ---- tests ----
assert can_split(8) == True
assert can_split(4) == True
assert can_split(2) == False     # শুধু 1+1, even নয়
assert can_split(3) == False     # বিজোড়
print("সব test pass!")

16. Line-by-line code explanation¶

w % 2 == 0 — w even কিনা; দুই even অংশের যোগফল even হতেই হবে।
and w > 2 — প্রতিটা অংশ কমপক্ষে 2, তাই মোট কমপক্ষে 4; 2 বাদ।
return ... — দুটো শর্ত একসাথে সত্য হলে True, নাহলে False।

17. Output walkthrough¶

8: even আর >2 → True। 4: even আর >2 → True। 2: even কিন্তু >2 নয় → False। 3: even নয় → False। সব assert pass; শেষে print: সব test pass!।

18. Time complexity¶

O(1) — একটা modulo আর একটা তুলনা, input-এর আকার নির্বিশেষে।

19. Space complexity¶

O(1) — কোনো extra storage নেই।

20. Common mistakes¶

w = 2-কে ভুলে True বলা — 1+1 ভাগ even নয়, তাই w > 2 শর্ত জরুরি।
শুধু "even কিনা" দেখা, "> 2 কিনা" ভুলে যাওয়া।
"দুই সমান অংশ" ভেবে ফেলা — অংশ দুটো সমান হতে হবে না (যেমন 2 + 6); শুধু দুটোই even হলেই চলবে।

21. Which basic problem this inherits from¶

ভিত্তি: modulo arithmetic আর parity (even/odd) — math fundamentals-এর একদম গোড়ার idea। এই parity-warm-up পরে আরো বড় number-theory/greedy যুক্তির প্রথম ধাপ। দেখো ../../01-math-based-programming-fundamentals/02-modular-arithmetic/।

22. Similar harder problems¶

Find Numbers with Even Number of Digits (parity of digit count) — https://leetcode.com/problems/find-numbers-with-even-number-of-digits/
Number of 1 Bits (bit-level parity warm-up) — https://leetcode.com/problems/number-of-1-bits/
Counting Bits — https://leetcode.com/problems/counting-bits/

23. Pattern learned¶

Parity / modulo decision: loop না চালিয়ে even/odd নিয়মে সরাসরি সিদ্ধান্ত — O(1)। অনেক math problem-এর প্রথম filter।

24. Final summary¶

ভবিষ্যতের আমাকে: "দুই even অংশে ভাঙা যায় iff w even আর w > 2।" 'জোড়/বিজোড়', 'সমান ভাগ', 'pair নিয়ে চাহিদা' দেখলেই আগে parity (% 2) দিয়ে ভাবো — অনেক সময় পুরো loop বাদ পড়ে যায়।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।