นับ quadruples จากอาร์เรย์ 4 ตัวที่เรียงแล้ว ผลรวมเท่ากับ x ใน C++

ภาพรวมปัญหา

ให้อาร์เรย์ 4 ตัว A[], B[], C[], D[] ขนาดเท่ากัน N ต้องการนับ quadruples (A[i], B[j], C[k], D[l]) ที่ผลรวมเท่ากับ x

ตัวอย่าง

Input: A={1,2,3}, B={2,3,2}, C={4,3,1}, D={3,1,1}, X=12

Output: 4

คำอธิบาย: (2,3,4,3), (3,2,4,3), (3,3,3,3), (3,2,4,3)

Input: A={1,1,1}, B={2,2,2}, C={3,3,3}, D={4,4,4}, X=15

Output: 0

แนวทาง Naive (4 Nested Loops)

1. ฟังก์ชัน countQuads(int a[], int b[], int c[], int d[], int x, int n)
2. ใช้ 4 nested loops วนทุกการจับคู่ i, j, k, l
3. ถ้า a[i]+b[j]+c[k]+d[l] == x ให้เพิ่ม count

โค้ดตัวอย่าง (Naive)

#include <bits/stdc++.h>
using namespace std;

int countQuads(int a[], int b[], int c[], int d[], int x, int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                for (int l = 0; l < n; l++) {
                    if (a[i] + b[j] + c[k] + d[l] == x) {
                        count++;
                    }
                }
            }
        }
    }
    return count;
}

int main() {
    int A[] = {1,1,1}, B[] = {2,2,2}, C[] = {3,3,3}, D[] = {4,4,4};
    int X = 15, N = 3;
    cout << "Number of quadruples: " << countQuads(A,B,C,D,X,N);
    return 0;
}

ผลลัพธ์

Number of quadruples: 0

แนวทางที่มีประสิทธิภาพมากกว่า (Meet-in-the-Middle)

ลดความซับซ้อนจาก O(N⁴) เป็น O(N² log N²)

1. คำนวณผลรวมทุกคู่ของ A+B เก็บใน vector sumAB
2. คำนวณผลรวมทุกคู่ของ C+D เก็บใน vector sumCD
3. เรียง sumCD
4. สำหรับแต่ละค่าใน sumAB ค้นหา x - val ใน sumCD ด้วย binary_search

โค้ดที่ปรับปรุงแล้ว

int countQuads_fast(int a[], int b[], int c[], int d[], int x, int n) {
    vector<int> sumAB, sumCD;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            sumAB.push_back(a[i] + b[j]);
            sumCD.push_back(c[i] + d[j]);
        }
    sort(sumCD.begin(), sumCD.end());
    
    long long count = 0;
    for (int val : sumAB) {
        int target = x - val;
        auto range = equal_range(sumCD.begin(), sumCD.end(), target);
        count += range.second - range.first;
    }
    return count;
}

ความซับซ้อน

หมายเหตุ

โจทย์ระบุ "four sorted arrays" แต่วิธี Naive ไม่ได้ใช้ข้อมูลที่เรียงแล้ว Meet-in-the-middle ใช้ได้ทั้ง sorted และ unsorted