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]|)-এর যোগফল। ধীরে পড়ো।

Problem link ও উৎস

• 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

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

একটা 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; একই চিন্তা সব জোড়ার গুণফল, বা পার্থক্যের অন্য ফাংশনেও খাটে।

Input ও 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 মানে)।

চেনা উদাহরণে বোঝা

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

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

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

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

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

ভেতরের অঙ্ক

মূল 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)।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

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

Python

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

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

কোথায় বেশি কাজ হতে পারে

দুটো 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-এ জানা যায়।

আরও ভালোভাবে ভাবা

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

Python

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²) থেকে নেমে এল।

ভাবনার পরিবর্তন

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

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

ছবিতে বোঝা

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) একবারে বিয়োগ। জোড়া ঘোরা লাগল না।

ছোট input-এ ধাপে ধাপে

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 তার বাঁয়ের সবার সাথে পার্থক্য জমাল।

কোড ও ব্যাখ্যা

Python

Python

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!")

কোডের প্রতিটি অংশ

উদাহরণ

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!।

Output মিলিয়ে দেখা

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!

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

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

শেখা ও পরের অনুশীলন

এই ধারণার পরের অনুশীলন

• 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-এর সাথে যোগসূত্র।

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে এক লাইনে: "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" লেখো।