Memahami Problem

Banyak bug dan Time Limit Exceeded (TLE) di kompetisi pemrograman bukan disebabkan oleh algoritma yang salah, melainkan oleh pemahaman soal yang setengah matang. Sebelum menulis satu baris kode pun, kita wajib membaca soal hingga tuntas, mengidentifikasi tiga komponen inti — input, output, dan constraint — lalu mengklasifikasikan tipe masalah agar tahu teknik mana yang relevan. Pada Chapter ini kita akan membangun kebiasaan tersebut melalui checklist sistematis dan sebuah studi kasus berdurasi pendek. Tujuan akhirnya: ketika menghadapi soal baru, otomatis tahu langkah pertama yang benar.

Tiga Komponen Wajib: Input, Output, Constraint #

Setiap soal DSA yang valid selalu memuat tiga komponen eksplisit. Bila salah satu tidak tertera, soal tersebut belum siap dikerjakan.

Mekanisme: Constraint Menentukan Kompleksitas #

Constraint bukan sekadar hiasan soal — constraint menentukan batas kompleksitas yang masih bisa lolos. Aturan praktis berikut didasarkan pada asumsi judge standar 1 detik ≈ 10⁸ operasi sederhana:

n ≤ 10        → O(n!) mungkin
n ≤ 20        → O(2^n) mungkin
n ≤ 100       → O(n^3) mungkin
n ≤ 1000      → O(n^2) mungkin
n ≤ 10^5      → O(n log n) mungkin
n ≤ 10^6      → O(n) mungkin
n ≤ 10^9      → O(log n) atau O(1)

Strategi: Contoh Kecil dan Edge Case #

Aturan #

Setelah membaca soal, langkah berikutnya adalah membuat contoh kecil secara manual dan mendaftar edge case. Contoh kecil membantu memverifikasi pemahaman soal; edge case memastikan solusi tidak gagal pada masukan batas.

Mekanisme: Tiga Langkah Manual #

1. Buat input minimal — misal n = 0, n = 1, atau array kosong. Apakah outputnya terdefinisi?
2. Buat input trivial — input di mana jawaban sudah jelas, untuk memverifikasi formula.
3. Buat input batas — n maksimum, semua nilai sama, array sudah sorted. Apakah algoritma tetap aman secara kompleksitas?

Kode: Template Mencatat Edge Case #

#include <iostream>
#include <vector>
#include <string>

struct TestCase {
    std::string name;
    std::vector<int> input;
    int expected;
};

int solve(const std::vector<int>& a) {
    int best = 0;
    for (int x : a) best = std::max(best, x);
    return best;
}

int main() {
    std::vector<TestCase> tests = {
        {"empty",          {},          0},
        {"single",         {7},         7},
        {"all negative",   {-3, -1, -8}, -1},
        {"all same",       {4, 4, 4},   4},
        {"unsorted",       {3, 9, 2, 7}, 9},
    };
    for (const auto& t : tests) {
        int got = solve(t.input);
        std::cout << t.name << ": got=" << got
                  << " expected=" << t.expected
                  << (got == t.expected ? " [OK]" : " [FAIL]")
                  << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

empty: got=0 expected=0 [OK]
single: got=7 expected=7 [OK]
all negative: got=0 expected=-1 [FAIL]
all same: got=4 expected=4 [OK]
unsorted: got=9 expected=9 [OK]

1. Baris {"empty", {}, 0}: kasus array kosong. Inisialisasi best = 0 membuat solve mengembalikan 0 — benar secara kebetulan untuk soal ini, tetapi rawan untuk soal lain.
2. Baris {"all negative", {-3, -1, -8}, -1}: kasus semua nilai negatif. Karena best dimulai dari 0, nilai -1 tidak pernah dipilih — solve mengembalikan 0, FAIL.
3. Baris int got = solve(t.input);: eksekusi fungsi. Bandingkan dengan expected. Status [FAIL] langsung memunculkan bug inisialisasi best = 0.
4. Pelajaran: edge case “semua negatif” mengungkap bug inisialisasi yang tidak terlihat pada uji acak.

Klasifikasi Tipe Masalah #

Setelah soal dipahami, langkah berikutnya adalah mengenali pola. Banyak soal dapat diklasifikasikan ke dalam salah satu kategori berikut, yang masing-masing punya teknik kanonik:

Studi Kasus Mini: Membaca Soal “Two Sum” #

Soal (versi singkat) #

Diberikan array a berisi n integer dan sebuah target T. Cari dua indeks i ≠ j sehingga a[i] + a[j] = T. Kembalikan pasangan indeks (apa saja yang valid). Constraint: 2 ≤ n ≤ 10^5, |a[i]| ≤ 10^9.

Analisis Tiga Komponen #

• Input: array a berukuran n, target T.
• Output: pasangan indeks (i, j) dengan i ≠ j.
• Constraint: n ≤ 10^5 → harus O(n log n) atau O(n).

Klasifikasi #

Soal ini bertipe pencarian/pencocokan — “apakah ada dua elemen yang berjumlah T?”. Teknik kanonik: hash map — untuk setiap elemen, cek apakah T - a[i] sudah pernah muncul.

Kode Solusi Hash Map O(n) #

#include <iostream>
#include <vector>
#include <unordered_map>

std::pair<int,int> two_sum(const std::vector<int>& a, int T) {
    std::unordered_map<int,int> seen;
    for (int i = 0; i < static_cast<int>(a.size()); ++i) {
        int need = T - a[i];
        auto it = seen.find(need);
        if (it != seen.end()) return {it->second, i};
        seen[a[i]] = i;
    }
    return {-1, -1};
}

int main() {
    std::vector<int> a = {2, 7, 11, 15};
    auto [i, j] = two_sum(a, 9);
    std::cout << "two_sum(a, 9) = (" << i << ", " << j << ")\n";
    auto [i2, j2] = two_sum(a, 100);
    std::cout << "two_sum(a, 100) = (" << i2 << ", " << j2 << ")\n";
    return 0;
}

Output yang Dihasilkan:

two_sum(a, 9) = (0, 1)
two_sum(a, 100) = (-1, -1)

1. Baris std::unordered_map<int,int> seen;: memetakan nilai ke indeks. Lookup rata-rata O(1).
2. Baris int need = T - a[i];: hitung nilai yang dibutuhkan untuk melengkapi pasangan dengan a[i].
3. Baris auto it = seen.find(need);: cek apakah need sudah pernah muncul di elemen sebelumnya. Bila ya, kita temukan pasangan.
4. Baris seen[a[i]] = i;: catat elemen saat ini setelah pencarian, agar tidak menggunakan elemen yang sama dua kali.
5. Hasil (0, 1): a[0] + a[1] = 2 + 7 = 9. Sesuai.

Ringkasan #

• Tiga komponen wajib soal: input, output, constraint. Constraint menentukan batas kompleksitas yang aman.
• Gunakan tabel n ≤ … → O(…) sebagai pedoman cepat menentukan kompleksitas yang masih lolos.
• Selalu uji dengan contoh kecil: input minimal, trivial, dan batas (edge case) sebelum memilih algoritma.
• Klasifikasi soal ke salah satu tipe (pencarian, optimisasi, pencocokan, dll.) untuk mempercepat identifikasi teknik kanonik.
• Studi kasus “Two Sum” memperlihatkan keseluruhan alur: baca → klasifikasi → pilih teknik → kode → verifikasi.