078 — Pair Contribution Problems¶

075-076-এ contribution চিন্তা ছিল element নিয়ে — "তুমি কয়টা subarray-তে আছ?" এবার সেই চিন্তা pair নিয়ে: সব জোড়ার (i, j) উপর কিছু একটা যোগ করতে হবে। সরল পথ O(n²) — সব জোড়া ঘোরা। কিন্তু প্রশ্ন উল্টে দিলে: "প্রতিটা element কয়টা জোড়ায় কী ভূমিকায়?" — আর O(n)/O(n log n)-এ নেমে আসে। উদাহরণ হিসেবে নেব সব জোড়ার পার্থক্যের পরম মান (|a[i]−a[j]|)-এর যোগফল। ধীরে পড়ো।

Source¶

Original source: Classic CP exercise (pair contribution / per-element role counting)
Platform: Classic CP exercise — https://usaco.guide/silver/more-prefix-sums
Topic: Math-based programming fundamentals → Level 5: Prefix, Difference, Contribution
Difficulty: Medium
Pattern: pair contribution (count pairs each element participates in)
Basic idea inherited from: 075 — Contribution Technique Basic

1. Problem in simple words¶

একটা array a (দৈর্ঘ্য n) দেওয়া। সব জোড়া (i, j) যেখানে i < j — তাদের পার্থক্যের পরম মান |a[i] - a[j]| যোগ করতে হবে। মোট কত?

যেমন a = [1, 3, 2]-এর জোড়াগুলো: |1-3| + |1-2| + |3-2| = 2 + 1 + 1 = 4। তোমার কাজ এই যোগফল দ্রুত বের করা — সব জোড়া ধরে ধরে না গুনে। এটাই "pair contribution" ঘরানার একটা প্রতিনিধি problem; একই চিন্তা সব জোড়ার গুণফল, বা পার্থক্যের অন্য ফাংশনেও খাটে।

2. What is the math idea?¶

মূল idea হলো pair contribution + sorting — প্রতিটা element কয়টা জোড়ায় "বড়" আর কয়টায় "ছোট" সেটা গোনা।

|a[i] - a[j]|-এ absolute value ঝামেলা করে — কে বড় জানা দরকার। চাল: array sort করো। sorted array-তে s[0] ≤ s[1] ≤ ... ≤ s[n-1], তাই index i-এর element তার বাঁয়ের সব (i টা) element-এর চেয়ে বড়-বা-সমান। তাই sum-এ s[i] যোগ হয় i বার (বড় হিসেবে) আর বিয়োগ হয় (n-1-i) বার (ছোট হিসেবে)। guণতে prefix sum:

total = Σ ( i * s[i] - (s[0] + ... + s[i-1]) )
        i

মানে প্রতিটা s[i]-এর জন্য: সে তার বাঁয়ের i টা element-এর সাথে জোড়ায় বড়, পার্থক্যের যোগফল = i*s[i] - (বাঁয়ের prefix sum)।

3. Which basic idea does this inherit from?¶

মূলত 075 (Contribution Technique Basic) থেকে — "প্রতিটা উপাদান কয়টায় কী ভূমিকায়" এই গোনা। 075-এ ভূমিকা ছিল "subarray-তে উপস্থিত", এখানে "জোড়ায় বড়/ছোট"।

আর সহায়ক হিসেবে 067-068-এর prefix sum — বাঁয়ের সব element-এর যোগফল চটপট পেতে। sorting যোগ করে absolute value-এর "কে বড়" প্রশ্নটা সরল হয়। তাই contribution-চিন্তা (075) + prefix sum (067) + sorting — তিনটা মিলে এই pair problem। মূল মন্ত্র সেই একই: জোড়া ঘুরো না, প্রতিটা element-কে জিজ্ঞেস করো সে কয়টা জোড়ায় কী।

4. Real-life analogy¶

ভাবো একটা ক্লাসে কয়েকজনের উচ্চতা মাপা হলো। তুমি জানতে চাও — সব সম্ভাব্য জোড়ার উচ্চতার পার্থক্য মিলিয়ে মোট কত।

সবাইকে লাইনে দাঁড় করাও খাটো থেকে লম্বা (sort)। এবার প্রতিটা ছাত্রকে জিজ্ঞেস করো: "তোমার বাঁয়ে (তোমার চেয়ে খাটো) কতজন?" ধরো i জন। তাহলে এই ছাত্র ওই i জনের প্রত্যেকের সাথে জোড়ায় "লম্বা" — প্রতিটায় তার উচ্চতা যোগ হয়, আর ওই খাটোদের উচ্চতা বিয়োগ হয়। বাঁয়ের সবার মোট উচ্চতা (prefix sum) এক ঝলকেই জানা।

তাই সবার জোড়া আলাদা করে না মেপে, প্রতিটা ছাত্রের "আমি বাঁয়ের i জনের সাথে কত পার্থক্য যোগ করি" জমালেই মোট। লাইনে দাঁড়ানোই (sort) absolute value-এর ঝামেলা মেটায়।

5. Visual explanation¶

a = [1, 3, 2] → sort করে s = [1, 2, 3]। প্রতিটা index-এর অবদান (বাঁয়ের সাথে পার্থক্য):

sorted s:    [ 1 ]  [ 2 ]  [ 3 ]
index i:       0      1      2
prefix(বাঁ):   0      1      3     ← বাঁয়ের element-দের যোগফল (s[0..i-1])

i=0:  বাঁয়ে কেউ নেই            → 0*1 - 0 = 0
i=1:  বাঁয়ে {1}, 1টা element   → 1*2 - 1 = 1      (|2-1| = 1)
i=2:  বাঁয়ে {1,2}, 2টা element → 2*3 - 3 = 3      (|3-1| + |3-2| = 2+1 = 3)

মোট = 0 + 1 + 3 = 4

মিলিয়ে দেখো সব জোড়া ধরে:

|1-3| = 2
|1-2| = 1
|3-2| = 1
যোগ = 4   ✓ একই উত্তর!

মূল কথা: sorted array-তে s[i] তার বাঁয়ের i টা element-এর প্রতিটার চেয়ে বড়, তাই i বার যোগ হয়; বাঁয়ের মোট (prefix sum) একবারে বিয়োগ। জোড়া ঘোরা লাগল না।

6. Example input and output¶

a = [1, 3, 2]          -> 4       (|1-3|+|1-2|+|3-2|)
a = [4]                -> 0       (একটাই element, কোনো জোড়া নেই)
a = [1, 2, 3, 4]       -> 10
a = [5, 5, 5]          -> 0       (সব সমান, পার্থক্য 0)
a = [-1, 2, -3, 4]     -> 24      (negative-ও ঠিক)

Edge case: একটা বা শূন্য element হলে কোনো জোড়া নেই, উত্তর 0। সব সমান হলেও 0। আর negative সংখ্যাতেও sort + prefix কৌশল অবিকল কাজ করে (sort signed order মানে)।

7. Brute force thinking¶

সব জোড়া (i, j) ঘুরে |a[i] - a[j]| যোগ:

def sum_pair_abs_brute(a):
    n = len(a)
    total = 0
    for i in range(n):
        for j in range(i + 1, n):
            total += abs(a[i] - a[j])
    return total

সরল, ঠিক উত্তর — প্রতিটা জোড়ার পার্থক্যের পরম মান সরাসরি যোগ করে।

8. Why brute force may be slow¶

দুটো nested loop — সব জোড়া, প্রায় n²/2 টা — O(n²)।

n = 50000 হলে:
  brute force: ~1.25 × 10^9 operation  (O(n²)) — TLE
  sort + prefix: ~50000 log 50000      ≈ 8×10^5 — দ্রুত

অপচয়টা: একই element বহু জোড়ায় বারবার আসছে। অথচ "সে কয়টা জোড়ায় বড়, কয়টায় ছোট, আর ওদের মোট কত" — sort করলে এক pass-এ জানা যায়।

9. Better thinking¶

মূল insight: sort করলে s[i] তার বাঁয়ের i টা element-এর চেয়ে বড়। তাই তার অবদান = i*s[i] - (বাঁয়ের prefix sum)। চলার পথে prefix sum রাখলেই এক pass:

def sum_pair_abs(a):
    s = sorted(a)
    total = 0
    prefix = 0
    for i in range(len(s)):
        total += i * s[i] - prefix    # বাঁয়ের i টার সাথে পার্থক্যের যোগফল
        prefix += s[i]                # নিজেকে prefix-এ জমা
    return total

sort O(n log n) + এক pass O(n) — মোট O(n log n)। O(n²) থেকে নেমে এল।

10. Thinking tweak¶

আসল "আহা!" মুহূর্ত: জোড়া ঘুরো না — প্রতিটা element-কে জিজ্ঞেস করো "আমি কয়টা জোড়ায় বড়, কয়টায় ছোট, আর তাদের মোট কত?" sort করলে এই প্রশ্নের উত্তর সহজ: বাঁয়ের সবাই ছোট-বা-সমান, ডানের সবাই বড়-বা-সমান।

দ্বিতীয় tweak: absolute value-এর "কে বড়" ঝামেলা sort মিটিয়ে দেয় — sorted order-এ সবসময় ডান > বাঁ, তাই |.| খুলে যায় নিশ্চিত sign-এ। আর বাঁয়ের মোট চটপট পেতে prefix sum (067)। এই "sort করে contribution + prefix" combo টা pair-ঘরানার বহু problem-এর master key (পার্থক্য, গুণফল, ইত্যাদি)।

11. Step-by-step dry run¶

a = [1, 2, 3, 4] (ইতিমধ্যে sorted) → s = [1, 2, 3, 4]। total = 0, prefix = 0:

i	s[i]	prefix (বাঁয়ের যোগ)	i*s[i] - prefix	total
0	1	0	0*1 - 0 = 0	0
1	2	1	1*2 - 1 = 1	1
2	3	3	2*3 - 3 = 3	4
3	4	6	3*4 - 6 = 6	10

শেষ অবস্থা: total = 10। যাচাই: |1-2|+|1-3|+|1-4|+|2-3|+|2-4|+|3-4| = 1+2+3+1+2+1 = 10 ✓। প্রতিটা step-এ element তার বাঁয়ের সবার সাথে পার্থক্য জমাল।

12. Python solution¶

def sum_pair_abs(a):
    """সব জোড়া (i<j)-র |a[i]-a[j]|-এর যোগফল; sort + contribution + prefix, O(n log n)।"""
    s = sorted(a)
    total = 0
    prefix = 0
    for i in range(len(s)):
        total += i * s[i] - prefix    # s[i] বাঁয়ের i টার চেয়ে বড়
        prefix += s[i]
    return total


def sum_pair_abs_brute(a):
    """ধীর O(n^2) version — সব জোড়া ঘুরে; মিলিয়ে দেখার জন্য।"""
    n = len(a)
    total = 0
    for i in range(n):
        for j in range(i + 1, n):
            total += abs(a[i] - a[j])
    return total


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert sum_pair_abs([1, 3, 2]) == 4
assert sum_pair_abs([4]) == 0
assert sum_pair_abs([1, 2, 3, 4]) == 10
assert sum_pair_abs([5, 5, 5]) == 0        # সব সমান
assert sum_pair_abs([-1, 2, -3, 4]) == 24  # negative
assert sum_pair_abs([]) == 0               # খালি array

# fast আর brute একই উত্তর কিনা (random brute-force cross-check):
import random
random.seed(31)
for _ in range(500):
    arr = [random.randint(-9, 9) for _ in range(random.randint(0, 12))]
    assert sum_pair_abs(arr) == sum_pair_abs_brute(arr)

print(sum_pair_abs([1, 3, 2]))       # 4
print(sum_pair_abs([1, 2, 3, 4]))    # 10
print("সব test pass!")

13. Line-by-line explanation¶

s = sorted(a)

array sort করছি — যাতে s[i] তার বাঁয়ের সব element-এর চেয়ে বড়-বা-সমান, absolute value-এর sign নিশ্চিত হয়।

total += i * s[i] - prefix

হৃদয়। s[i] তার বাঁয়ের i টা element-এর সাথে জোড়ায় বড়; প্রতিটায় পার্থক্য = s[i] - (সেই element)। সব মিলে i*s[i] - (বাঁয়ের সবার যোগফল) = i*s[i] - prefix। এটাই s[i]-এর contribution।

prefix += s[i]

নিজেকে prefix sum-এ জমালাম — পরের (বড়) element-দের জন্য, যাদের কাছে আমি "বাঁয়ের ছোট"।

বাকি assert গুলো নির্দিষ্ট উদাহরণ + random array-তে fast আর brute মিলিয়ে দেখছে (brute-force cross-check), negative ও খালি array সহ। সব মিললে সব test pass!।

14. Output walkthrough¶

a = [1, 3, 2] → sort → s = [1, 2, 3]:

i=0: 0*1 - 0 = 0, prefix → 1
i=1: 1*2 - 1 = 1, prefix → 3, total = 1
i=2: 2*3 - 3 = 3, prefix → 6, total = 4
return 4 → প্রথম print
[1,2,3,4] → 10 → দ্বিতীয় print
সব assert pass → সব test pass!

ছাপা output:

4
10
সব test pass!

15. Time complexity¶

O(n log n) — sort-এর খরচ O(n log n), তারপর এক pass O(n)। sort-ই প্রধান খরচ। brute force-এর O(n²) থেকে বড় উন্নতি, বিশেষত বড় n-এ।

16. Space complexity¶

O(n) — sorted copy s রাখতে (Python sorted নতুন list বানায়)। in-place sort করলে O(1) extra (input বদলালে চলবে)। prefix আর total শুধু scalar।

17. Common mistakes¶

sort না করে absolute value সামলানোর চেষ্টা — sort ছাড়া "কে বড়" অনিশ্চিত, contribution-এর sign ভুল হয়। আগে sort।
prefix কখন যোগ হবে — আগে না পরে — আগে total += i*s[i] - prefix, তারপর prefix += s[i]; উল্টালে নিজেকে নিজের সাথে জোড়া ধরা হয়।
i বনাম i+1 গুলিয়ে ফেলা — বাঁয়ে ঠিক i টা element (index 0..i-1), তাই গুণফল i*s[i]; (i+1) নয়।
pair count আর pair sum গুলিয়ে ফেলা — এখানে পার্থক্যের যোগফল চাই, শুধু জোড়ার সংখ্যা নয়; মান অবশ্যই লাগবে।
overflow (অন্য ভাষায়) — বড় n আর বড় মানে যোগফল বিশাল; C++/Java-তে long long। Python নিশ্চিন্ত।

18. Harder problems that inherit this idea¶

LeetCode — Sum of Absolute Differences in a Sorted Array (https://leetcode.com/problems/sum-of-absolute-differences-in-a-sorted-array/) — হুবহু এই pair-contribution + prefix।
Codeforces-style — sum of all pairwise products — Σ_{i<j} a[i]*a[j] = ((Σa)² - Σa²) / 2; একই "pair ভেঙে element" চিন্তা।
LeetCode — Sum of Subarray Ranges (https://leetcode.com/problems/sum-of-subarray-ranges/) — max-min contribution; 077-এর সাথে যোগসূত্র।

19. Pattern learned¶

Pair contribution (sort + prefix) — সব জোড়ার পার্থক্য = Σ (i*s[i] - prefix) sorted array-তে। বড় শিক্ষা: সব জোড়া ঘুরো না; প্রতিটা element-কে জিজ্ঞেস করো "আমি কয়টা জোড়ায় বড়/ছোট, আর তাদের মোট কত" — sort absolute value-এর sign ঠিক করে, prefix sum বাঁয়ের মোট দেয়।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "pair-এর পার্থক্য-যোগফল = sort করে Σ (i*s[i] - prefix)। জোড়া ঘুরো না — প্রতিটা element কয়টা জোড়ায় বড়, বাঁয়ের মোট কত (prefix)। sort + contribution = O(n log n)।"

পরের ধাপ → 079 — Imos Method Basic (difference-চিন্তা event-এর জগতে)।

ফিরে দেখা: শিকড় → 075 — Contribution Technique Basic, 067 — Prefix Sum · এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।

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