Common Mistakes

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

// === Mistake 1: Integer overflow pada akumulator ===
int sum_int_bug(const std::vector<int>& a) {
    int s = 0;
    for (int x : a) s += x;  // overflow bila |sum| > 2^31
    return s;
}
long long sum_ll_ok(const std::vector<int>& a) {
    long long s = 0;
    for (int x : a) s += x;
    return s;
}

// === Mistake 2: Off-by-one pada loop ===
int count_loop_bug(const std::vector<int>& a, int threshold) {
    int cnt = 0;
    // BUG: i <= size() -> akses a[n] yang OOB
    for (size_t i = 0; i <= a.size(); ++i) {
        if (i < a.size() && a[i] < threshold) cnt++;
    }
    return cnt;
}
int count_loop_ok(const std::vector<int>& a, int threshold) {
    int cnt = 0;
    for (size_t i = 0; i < a.size(); ++i) {
        if (a[i] < threshold) cnt++;
    }
    return cnt;
}

// === Mistake 3: Uninitialized variable ===
int uninit_bug() {
    int x;            // UB bila dibaca
    return x + 1;     // bisa apa saja
}
int uninit_ok() {
    int x = 0;
    return x + 1;
}

// === Mistake 4: Array OOB causing RE ===
int array_oob_ok() {
    int a[5] = {1, 2, 3, 4, 5};
    int sum = 0;
    for (int i = 0; i < 5; ++i) sum += a[i];  // i < 5 (aman)
    return sum;
}

// === Mistake 5: TLE dari O(n^2) ===
void tle_bug(std::vector<int>& a) {
    // Bubble sort O(n^2) — TLE bila n=10^5 (100 detik)
    int n = (int)a.size();
    for (int i = 0; i < n - 1; ++i)
        for (int j = 0; j < n - i - 1; ++j)
            if (a[j] > a[j+1]) std::swap(a[j], a[j+1]);
}
void tle_ok(std::vector<int>& a) {
    std::sort(a.begin(), a.end());  // O(n log n)
}

int main() {
    std::cout << "=== Lima Common Mistakes di CP ===\n\n";

    std::cout << "1) Integer overflow pada akumulator\n";
    std::vector<int> big(100000, 100000);  // sum = 10^10
    std::cout << "   sum_int_bug(big) = " << sum_int_bug(big) << " (SALAH, overflow)\n";
    std::cout << "   sum_ll_ok(big)  = " << sum_ll_ok(big) << " (BENAR)\n\n";

    std::cout << "2) Off-by-one pada loop\n";
    std::vector<int> v = {5, 3, 8, 1, 9};
    std::cout << "   count_loop_bug(v, 5) = " << count_loop_bug(v, 5) << "\n";
    std::cout << "   count_loop_ok(v, 5)  = " << count_loop_ok(v, 5) << " (BENAR)\n\n";

    std::cout << "3) Uninitialized variable\n";
    std::cout << "   uninit_bug() = " << uninit_bug() << " (UB — nilai tak terduga)\n";
    std::cout << "   uninit_ok()  = " << uninit_ok() << " (selalu 1 — aman)\n\n";

    std::cout << "4) Array out-of-bounds (RE)\n";
    std::cout << "   array_oob_ok() = " << array_oob_ok() << " (BENAR)\n\n";

    std::cout << "5) TLE dari O(n^2) pada n=10^5\n";
    std::vector<int> small = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    std::vector<int> copy1 = small, copy2 = small;
    tle_bug(copy1);
    tle_ok(copy2);
    std::cout << "   tle_bug (bubble O(n^2)): hasil = ";
    for (int x : copy1) std::cout << x << ' ';
    std::cout << '\n';
    std::cout << "   tle_ok  (std::sort O(n log n)): hasil = ";
    for (int x : copy2) std::cout << x << ' ';
    std::cout << "\n   Catatan: untuk n=10^5, bubble sort TLE ~100 detik.\n\n";

    std::cout << "=== Tabel Ringkasan Mistake ===\n";
    std::cout << "Mistake                | Verdict Tipikal | Cara Hindari\n";
    std::cout << "-----------------------|-----------------|-----------------------------\n";
    std::cout << "Integer overflow       | WA / UB         | Pakai long long untuk sum\n";
    std::cout << "Off-by-one             | WA              | Pakai i < n, bukan i <= n\n";
    std::cout << "Uninitialized variable | WA / UB         | Selalu inisialisasi eksplisit\n";
    std::cout << "Array OOB              | RE (segfault)   | Validasi indeks sebelum akses\n";
    std::cout << "TLE dari O(n^2)        | TLE             | Pakai O(n log n) atau lebih baik\n";
    std::cout << "MLE dari struktur besar| MLE             | Hitung memori sebelum deklarasi\n";
    std::cout << "Wrong output format    | WA / PE         | Hati-hati newline & separator\n";
    std::cout << "Stack overflow rekursi | RE              | Pakai iteratif untuk n besar\n";
    return 0;
}

=== Lima Common Mistakes di CP ===

1) Integer overflow pada akumulator
   sum_int_bug(big) = 1410065408 (SALAH, overflow)
   sum_ll_ok(big)  = 10000000000 (BENAR)

2) Off-by-one pada loop
   count_loop_bug(v, 5) = 2
   count_loop_ok(v, 5)  = 2 (BENAR)

3) Uninitialized variable
   uninit_bug() = 1 (UB — nilai tak terduga)
   uninit_ok()  = 1 (selalu 1 — aman)

4) Array out-of-bounds (RE)
   array_oob_ok() = 15 (BENAR)

5) TLE dari O(n^2) pada n=10^5
   tle_bug (bubble O(n^2)): hasil = 1 2 3 4 5 6 7 8 9 
   tle_ok  (std::sort O(n log n)): hasil = 1 2 3 4 5 6 7 8 9 
   Catatan: untuk n=10^5, bubble sort TLE ~100 detik.

=== Tabel Ringkasan Mistake ===
Mistake                | Verdict Tipikal | Cara Hindari
-----------------------|-----------------|-----------------------------
Integer overflow       | WA / UB         | Pakai long long untuk sum
Off-by-one             | WA              | Pakai i < n, bukan i <= n
Uninitialized variable | WA / UB         | Selalu inisialisasi eksplisit
Array OOB              | RE (segfault)   | Validasi indeks sebelum akses
TLE dari O(n^2)        | TLE             | Pakai O(n log n) atau lebih baik
MLE dari struktur besar| MLE             | Hitung memori sebelum deklarasi
Wrong output format    | WA / PE         | Hati-hati newline & separator
Stack overflow rekursi | RE              | Pakai iteratif untuk n besar