นับจำนวนทีมที่เป็นไปได้ใน C++

ปัญหา: Count Number of Teams

มีทหาร n คน ยืนเรียงติดกัน แต่ละคนมีคะแนน (rating) ไม่ซ้ำกัน ต้องจัดทีม 3 คน โดยดัชนี (i, j, k) ที่ i < j < k ทีมถูกต้องถ้า:

• เพิ่มขึ้น: rating[i] < rating[j] < rating[k]
• ลดลง: rating[i] > rating[j] > rating[k]

หาจำนวนทีมทั้งหมดที่เป็นไปได้ (ทหารคนหนึ่งอาจอยู่ในหลายทีม)

ตัวอย่าง

rating = [2, 5, 3, 4, 1]

ทีมที่ถูกต้อง 3 ทีม:

• (2, 3, 4) – เพิ่มขึ้น
• (5, 4, 1) – ลดลง
• (5, 3, 1) – ลดลง

แนวทางแก้ปัญหา

วิธีที่ 1: Brute Force O(n³)

วนลูป 3 ชั้น ตรวจสอบทุก triplet – ใช้ได้กับ n ≤ 200

วิธีที่ 2: Optimized O(n²) – แนะนำ

สำหรับแต่ละ j (ตำแหน่งกลาง) นับ:

• leftLess = จำนวน i < j ที่ rating[i] < rating[j]
• leftGreater = จำนวน i < j ที่ rating[i] > rating[j]
• rightLess = จำนวน k > j ที่ rating[k] < rating[j]
• rightGreater = จำนวน k > j ที่ rating[k] > rating[j]

ทีมเพิ่มขึ้นผ่าน j: leftLess * rightGreater
ทีมลดลงผ่าน j: leftGreater * rightLess

ตัวอย่างโค้ด C++ (O(n²))

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

class Solution {
public:
    int numTeams(vector<int>& rating) {
        int n = rating.size();
        int ans = 0;

        for (int j = 1; j < n - 1; j++) {
            int leftLess = 0, leftGreater = 0;
            int rightLess = 0, rightGreater = 0;

            for (int i = 0; i < j; i++) {
                if (rating[i] < rating[j]) leftLess++;
                else if (rating[i] > rating[j]) leftGreater++;
            }
            for (int k = j + 1; k < n; k++) {
                if (rating[k] < rating[j]) rightLess++;
                else if (rating[k] > rating[j]) rightGreater++;
            }

            ans += leftLess * rightGreater;   // increasing
            ans += leftGreater * rightLess;   // decreasing
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {2, 5, 3, 4, 1};
    cout << ob.numTeams(v); // Output: 3
    return 0;
}

ตัวอย่างโค้ด Brute Force (O(n³)) – ใช้ได้ n ≤ 200

class Solution {
public:
    int numTeams(vector<int>& v) {
        int ret = 0, n = v.size();
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                for (int k = j + 1; k < n; k++)
                    if ((v[i] < v[j] && v[j] < v[k]) ||
                        (v[i] > v[j] && v[j] > v[k]))
                        ret++;
        return ret;
    }
};

ความซับซ้อน

ข้อสังเกต

• วิธี O(n²) เร็วกว่ามากเมื่อ n ใหญ่ (n=1000 → 10⁶ vs 10⁹ operations)
• สามารถเพิ่มประสิทธิภาพเป็น O(n log n) ได้ด้วย Fenwick Tree / Segment Tree
• โจทย์ระบุ "soldiers can be part of multiple teams" → ไม่ต้องกังวลการซ้ำ