Memilih Algoritma

Soal CP selalu memberikan constraint eksplisit pada input — n ≤ 10^5, |a[i]| ≤ 10^9, dst. Constraint ini bukan sekadar informasi; constraint menentukan batas atas kompleksitas algoritma yang masih bisa lolos time limit. Pada Chapter ini kita akan memetakan hubungan constraint → kompleksitas maksimal → kelompok algoritma, lalu mendemonstrasikan tiga implementasi berbeda untuk soal yang sama (Two Sum) dengan kompleksitas berbeda. Tujuan akhirnya: ketika membaca soal baru, kita langsung tahu kompleksitas yang dibutuhkan sebelum berpikir tentang algoritma spesifik.

Aturan: Constraint Menentukan Kompleksitas #

Judge modern menjalankan ~10^8 operasi sederhana per detik. Time limit standar 1–2 detik memberi budget ~10^8 hingga 2×10^8 operasi. Berdasarkan ini, kita dapat memetakan constraint n ke kompleksitas maksimal yang masih aman:

Constraint `n`	Kompleksitas Maks	Kelompok Algoritma
`n ≤ 10`	`O(n!)`	Permutasi penuh, brute search
`n ≤ 20`	`O(2^n)`	Bitmask DP, subset enumeration
`n ≤ 100`	`O(n^3)`	Floyd-Warshall, triplet enumeration
`n ≤ 1000`	`O(n^2)`	DP klasik, nested loop
`n ≤ 10^5`	`O(n log n)`	Sort, binary search, segment tree
`n ≤ 10^6`	`O(n)`	Linear scan, hash, two pointers
`n ≤ 10^9`	`O(log n)` atau `O(1)`	Binary search, formula

Mekanisme: Menghitung Operasi dari Kompleksitas #

Langkah analisis soal baru:

Baca constraint n dari soal.
Tentukan kompleksitas maksimal dari tabel di atas.
Hitung jumlah operasi: ops ≈ n × (kompleksitas per elemen).
Bandingkan dengan budget: bila ops > 10^8, algoritma kemungkinan TLE.
Pilih algoritma dari kelompok yang sesuai kompleksitas.

Contoh: soal “cari pasangan a[i] + a[j] = T” dengan n = 10^5:

Kompleksitas maks: O(n log n).
n log n = 10^5 × 17 ≈ 1.7 × 10^6 operasi → jauh di bawah budget.
Pilih: sort + two pointers (atau hash set O(n) rata-rata).

Untuk n = 10^9, O(n) sudah 10^9 operasi → TLE. Harus O(log n) (binary search) atau O(1) (formula matematis).

Kode: Tiga Algoritma untuk Two Sum #

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>

// Untuk n <= 5000: O(n^2) brute force — paling sederhana.
bool two_sum_brute(const std::vector<int>& a, int T) {
    int n = (int)a.size();
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            if (a[i] + a[j] == T) return true;
    return false;
}

// Untuk n <= 10^6: O(n log n) sort + two pointers.
bool two_sum_sort(std::vector<int> a, int T) {
    std::sort(a.begin(), a.end());
    int lo = 0, hi = (int)a.size() - 1;
    while (lo < hi) {
        int sum = a[lo] + a[hi];
        if (sum == T) return true;
        else if (sum < T) ++lo;
        else --hi;
    }
    return false;
}

// Untuk n <= 10^5 dengan nilai a[i] kecil: O(n) hash set.
bool two_sum_hash(const std::vector<int>& a, int T) {
    std::unordered_set<int> seen;
    for (int x : a) {
        if (seen.count(T - x)) return true;
        seen.insert(x);
    }
    return false;
}

int main() {
    std::vector<int> a = {2, 7, 11, 15};
    int T = 9;

    std::cout << "=== Demo: Tiga Algoritma untuk Two Sum ===\n";
    std::cout << "Array: [2, 7, 11, 15], target T = 9\n\n";

    std::cout << "1) Brute force O(n^2):        " << (two_sum_brute(a, T) ? "YES" : "NO") << '\n';
    std::cout << "2) Sort + two ptr O(n log n): " << (two_sum_sort(a, T) ? "YES" : "NO") << '\n';
    std::cout << "3) Hash set       O(n):       " << (two_sum_hash(a, T) ? "YES" : "NO") << '\n';

    std::cout << "\n=== Tabel Pemilihan Algoritma dari Constraint ===\n";
    std::cout << "Constraint n      | Kompleksitas Maks | Teknik yang Tersedia\n";
    std::cout << "------------------|-------------------|------------------------------\n";
    std::cout << "n <= 10            | O(n!)             | Permutasi penuh\n";
    std::cout << "n <= 20            | O(2^n)            | Bitmask DP, subset enumeration\n";
    std::cout << "n <= 100           | O(n^3)            | Floyd-Warshall, brute triplet\n";
    std::cout << "n <= 1000          | O(n^2)            | DP klasik, nested loop\n";
    std::cout << "n <= 10^5          | O(n log n)        | Sort, binary search, segment tree\n";
    std::cout << "n <= 10^6          | O(n)              | Linear scan, hash, two ptr\n";
    std::cout << "n <= 10^9          | O(log n) atau O(1)| Binary search, formula\n";

    std::cout << "\n=== Rule of Thumb: Operasi per Detik ===\n";
    std::cout << "Judge modern: ~10^8 operasi sederhana per detik\n";
    std::cout << "Time limit 1 detik  -> max ~10^8 ops\n";
    std::cout << "Time limit 2 detik  -> max ~2 * 10^8 ops\n";
    std::cout << "Time limit 5 detik  -> max ~5 * 10^8 ops\n\n";

    std::cout << "Contoh perhitungan:\n";
    std::cout << "  n = 10^5, algoritma O(n^2) = 10^10 ops -> TLE (butuh ~100 detik)\n";
    std::cout << "  n = 10^5, algoritma O(n log n) ~ 1.7*10^6 ops -> OK (<1 detik)\n";
    std::cout << "  n = 10^6, algoritma O(n) = 10^6 ops -> OK (<1 detik)\n";
    return 0;
}

Output yang Dihasilkan:

text
=== Demo: Tiga Algoritma untuk Two Sum ===
Array: [2, 7, 11, 15], target T = 9

1) Brute force O(n^2):        YES
2) Sort + two ptr O(n log n): YES
3) Hash set       O(n):       YES

=== Tabel Pemilihan Algoritma dari Constraint ===
Constraint n      | Kompleksitas Maks | Teknik yang Tersedia
------------------|-------------------|------------------------------
n <= 10            | O(n!)             | Permutasi penuh
n <= 20            | O(2^n)            | Bitmask DP, subset enumeration
n <= 100           | O(n^3)            | Floyd-Warshall, brute triplet
n <= 1000          | O(n^2)            | DP klasik, nested loop
n <= 10^5          | O(n log n)        | Sort, binary search, segment tree
n <= 10^6          | O(n)              | Linear scan, hash, two ptr
n <= 10^9          | O(log n) atau O(1)| Binary search, formula

=== Rule of Thumb: Operasi per Detik ===
Judge modern: ~10^8 operasi sederhana per detik
Time limit 1 detik  -> max ~10^8 ops
Time limit 2 detik  -> max ~2 * 10^8 ops
Time limit 5 detik  -> max ~5 * 10^8 ops

Contoh perhitungan:
  n = 10^5, algoritma O(n^2) = 10^10 ops -> TLE (butuh ~100 detik)
  n = 10^5, algoritma O(n log n) ~ 1.7*10^6 ops -> OK (<1 detik)
  n = 10^6, algoritma O(n) = 10^6 ops -> OK (<1 detik)

Bedah Kode Baris-per-Baris #

two_sum_brute — O(n^2): dua loop bersarang i dan j. Untuk setiap pasangan (i, j), cek a[i] + a[j] == T. Untuk n = 5000, total ~12.5 juta iterasi — masih cepat.
two_sum_sort — O(n log n): sort array lebih dulu, kemudian two pointers dari kedua ujung. Bila a[lo] + a[hi] < T, geser lo ke kanan (sum naik); bila > T, geser hi ke kiri (sum turun). Sort memakai O(n log n), two pointers O(n).
two_sum_hash — O(n) average: gunakan unordered_set sebagai hash set. Untuk setiap elemen x, cek apakah T - x sudah ada di set. Insert x ke setelah pencarian agar tidak pakai elemen sama dua kali. Hash lookup rata-rata O(1), worst case O(n) (hash collision).
std::sort(a.begin(), a.end()): introsort — hybrid quicksort + heapsort + insertion sort. Garansi O(n log n) worst case. Lebih cepat dari quicksort naif karena pivot selection random.
std::unordered_set<int> seen: hash set berbasis std::unordered_*. Rata-rata O(1) untuk insert dan count. Worst case O(n) bila banyak collision — untuk int, hash sangat baik sehingga hampir selalu O(1).

Konstanta: Bukan Hanya Big-O #

Big-O menyembunyikan konstanta. Algoritma O(n log n) bisa lebih lambat dari O(n^2) pada n kecil karena konstanta besar. Tabel berikut memberi perkiraan:

Algoritma	Konstanta	Aman untuk `n`
Linear scan	1	`n ≤ 10^8`
Sort (`std::sort`)	5	`n ≤ 10^7`
Binary search	log(n)	`n ≤ 10^18`
Hash set	10 (overhead hash)	`n ≤ 10^7`
`std::map` (red-black tree)	30	`n ≤ 10^6`
Segment tree	10 (rekursi + akses)	`n ≤ 10^6`
Segment tree + lazy	30	`n ≤ 10^5`

Strategi Pemilihan Algoritma Bertingkat #

flowchart TD A[Baca constraint n] --> B{n <= 20?} B -- Ya --> C[Brute force / bitmask DP] B -- Tidak --> D{n <= 1000?} D -- Ya --> E[O(n^2) — DP klasik / nested loop] D -- Tidak --> F{n <= 10^5?} F -- Ya --> G[O(n log n) — sort / binary search / seg tree] F -- Tidak --> H{n <= 10^6?} H -- Ya --> I[O(n) — linear / hash / two ptr] H -- Tidak --> J[O(log n) — binary search on answer / formula]

Ringkasan #

Constraint n menentukan kompleksitas maksimal: n ≤ 10 → O(n!), n ≤ 20 → O(2^n), …, n ≤ 10^9 → O(log n).
Judge modern menjalankan ~10^8 operasi per detik — angka ini adalah budget time limit.
Untuk soal yang sama (mis. Two Sum), tiga implementasi berbeda dapat dipilih sesuai constraint: brute force O(n^2), sort + two pointers O(n log n), hash set O(n).
Konstanta berpengaruh — std::map lebih lambat dari std::unordered_map, std::sort lebih cepat dari manual quicksort.
Pemilihan algoritma adalah tradeoff kecepatan vs memori vs kompleksitas kode — pertimbangkan ketiganya.