Batasan Waktu dan Memori

Setiap judge CP memberlakukan dua batas: time limit (durasi eksekusi maksimal) dan memory limit (memori maksimal yang boleh dipakai). Melebihi salah satu batas menghasilkan TLE (Time Limit Exceeded) atau MLE (Memory Limit Exceeded) — keduanya sama salahnya dengan Wrong Answer. Pada Chapter ini kita akan mengonversi constraint input menjadi estimasi waktu dan memori, membandingkan batasan standar antar judge, dan mempraktikkan teknik menghemat memori. Tujuan akhirnya: sebelum submit, kita dapat memperkirakan apakah solusi akan TLE/MLE hanya dari constraint n.

Batasan Standar antar Judge #

Judge	Time Limit	Memory Limit	Catatan
Codeforces	1–2 detik	256 MB	Paling ketat memori
AtCoder	2 detik	1024 MB	Memori longgar, banyak ruang untuk eksperimen
ICPC	1–10 detik	256–1024 MB	Bervariasi per regional
Google Code Jam (lalu)	15–60 detik	1 GB	Longgar — fokus pada algoritma
IOI	0.5–2 detik	256 MB	Sama ketatnya dengan Codeforces

Mekanisme: Operasi per Detik #

Judge modern berbasis CPU desktop/server dengan clock ~3 GHz. Setelah overhead OS dan interpreter, kita dapat memperkirakan throughput:

Jenis Operasi	Operasi per Detik	Contoh
Sederhana (int `+`, `*`, comparison)	~10^8	Loop linear scan
Kompleks (modulo, hash, sqrt)	~10^7	Hash lookup, modulo
Sangat kompleks (rekursi + cache miss)	~10^6	Tree traversal dalam
Floating point (double)	~10^8 (modern CPU)	Operasi FP, trigonometri

Berdasarkan ini, time limit 1 detik memberi budget ~10^8 operasi sederhana. Time limit 2 detik → ~2×10^8.

Estimasi Memori Berbagai Struktur #

Tabel berikut mengestimasi memori untuk struktur umum (asumsi 64-bit pointer):

Struktur	Memori per Elemen	n = 10^6	n = 10^7
`int` array	4 byte	4 MB	40 MB
`long long` array	8 byte	8 MB	80 MB
`bool` array (`std::vector<bool>`)	1 byte (atau 1 bit optimized)	1 MB / 125 KB	10 MB / 1.25 MB
`std::string` sepanjang `n`	1 byte/char + ~32 byte overhead	~1 MB	~10 MB
`std::vector<int>`	4 byte + 24 byte overhead	4 MB	40 MB
`std::pair<int,int>` array	8 byte	8 MB	80 MB
`std::map<int,int>` node	~64 byte (red-black tree)	64 MB	640 MB
`std::unordered_map<int,int>`	~32 byte (hash table + bucket)	32 MB	320 MB
`vector<vector<int>>` (n×n)	n² × 4 + n × 24 byte	4 GB (n=10^6)	over-limit

Kode: Estimasi Waktu dan Memori #

cpp
#include <iostream>
#include <vector>
#include <cstdint>

int main() {
    std::cout << "=== Batasan Waktu Standar Judge ===\n";
    std::cout << "Judge            | Time Limit | Memory Limit\n";
    std::cout << "-----------------|------------|--------------\n";
    std::cout << "Codeforces       | 1-2 detik  | 256 MB\n";
    std::cout << "AtCoder          | 2 detik    | 1024 MB\n";
    std::cout << "ICPC             | 1-10 detik | 256-1024 MB\n";
    std::cout << "Google Code Jam  | 15-60 detik| 1 GB\n";
    std::cout << "IOI              | 0.5-2 detik| 256 MB\n\n";

    std::cout << "=== Rule of Thumb Operasi per Detik ===\n";
    std::cout << "1 detik  ~ 10^8 operasi sederhana (int +, *, comparison)\n";
    std::cout << "1 detik  ~ 10^7 operasi kompleks (modulo, hash, sqrt)\n";
    std::cout << "1 detik  ~ 10^6 operasi sangat kompleks (rekursi + memory access)\n\n";

    std::cout << "=== Estimasi Memori Berbagai Struktur ===\n";
    std::cout << "Struktur                          | Memori untuk n=10^6\n";
    std::cout << "-----------------------------------|---------------------\n";
    std::cout << "int array[10^6]                   | 4 MB\n";
    std::cout << "int array[10^7]                   | 40 MB\n";
    std::cout << "long long array[10^6]             | 8 MB\n";
    std::cout << "long long array[10^7]             | 80 MB\n";
    std::cout << "vector<int> overhead ~            | +24 byte\n";
    std::cout << "std::string sepanjang 10^6 char   | 1 MB\n";
    std::cout << "std::map<int,int> n=10^5          | ~10 MB (red-black tree, ~80 B/node)\n";
    std::cout << "std::unordered_map<int,int> n=10^5| ~8 MB (hash table)\n";
    std::cout << "vector<vector<int>> n x n         | n^2 * 4 + n * 24 byte\n";
    std::cout << "adjacency list graph n=10^5, m=10^5| ~8 MB (vector<pair>)\n\n";

    // Hitung konkret
    std::cout << "=== Hitung Konkret ===\n";
    int n = 1'000'000;
    std::cout << "n = 10^6 elemen:\n";
    std::cout << "  int[n]        : " << (n * 4 / 1024 / 1024.0) << " MB\n";
    std::cout << "  long long[n]  : " << (n * 8 / 1024 / 1024.0) << " MB\n";

    n = 10'000'000;
    std::cout << "n = 10^7 elemen:\n";
    std::cout << "  int[n]        : " << (n * 4 / 1024 / 1024.0) << " MB\n";
    std::cout << "  long long[n]  : " << (n * 8 / 1024 / 1024.0) << " MB\n\n";

    std::cout << "=== Konsekuensi Praktis ===\n";
    std::cout << "- Array int 10^7 = 40 MB -> aman di 256 MB (Codeforces)\n";
    std::cout << "- Array int 5*10^7 = 200 MB -> berbahaya, mendekati limit\n";
    std::cout << "- Array int 10^8 = 400 MB -> MLE pasti di Codeforces, OK di AtCoder\n";
    std::cout << "- int[n][n] n=10^4 = 400 MB -> MLE\n";
    std::cout << "- int[n][n] n=10^3 = 4 MB -> aman\n\n";

    std::cout << "=== Tips Menghemat Memori ===\n";
    std::cout << "1. Pakai int bila nilai <= 2*10^9 (cukup), bukan long long\n";
    std::cout << "2. Pakai vector<vector<int>> bukan int[n][m] untuk variable size\n";
    std::cout << "3. Kompres koordinat: nilai besar -> rentang [0, n)\n";
    std::cout << "4. Reuse array: bersihkan dengan fill() bukan alokasi baru\n";
    std::cout << "5. Bitset untuk boolean array: 8x lebih hemat dari vector<char>\n";
    std::cout << "6. Hindari std::map jika std::unordered_map cukup (lebih ringan)\n";
    return 0;
}

Output yang Dihasilkan:

text
=== Batasan Waktu Standar Judge ===
Judge            | Time Limit | Memory Limit
-----------------|------------|--------------
Codeforces       | 1-2 detik  | 256 MB
AtCoder          | 2 detik    | 1024 MB
ICPC             | 1-10 detik | 256-1024 MB
Google Code Jam  | 15-60 detik| 1 GB
IOI              | 0.5-2 detik| 256 MB

=== Rule of Thumb Operasi per Detik ===
1 detik  ~ 10^8 operasi sederhana (int +, *, comparison)
1 detik  ~ 10^7 operasi kompleks (modulo, hash, sqrt)
1 detik  ~ 10^6 operasi sangat kompleks (rekursi + memory access)

=== Estimasi Memori Berbagai Struktur ===
Struktur                          | Memori untuk n=10^6
-----------------------------------|---------------------
int array[10^6]                   | 4 MB
int array[10^7]                   | 40 MB
long long array[10^6]             | 8 MB
long long array[10^7]             | 80 MB
vector<int> overhead ~            | +24 byte
std::string sepanjang 10^6 char   | 1 MB
std::map<int,int> n=10^5          | ~10 MB (red-black tree, ~80 B/node)
std::unordered_map<int,int> n=10^5| ~8 MB (hash table)
vector<vector<int>> n x n         | n^2 * 4 + n * 24 byte
adjacency list graph n=10^5, m=10^5| ~8 MB (vector<pair>)

=== Hitung Konkret ===
n = 10^6 elemen:
  int[n]        : 3.81445 MB
  long long[n]  : 7.62891 MB
n = 10^7 elemen:
  int[n]        : 38.1465 MB
  long long[n]  : 76.2939 MB

=== Konsekuensi Praktis ===
- Array int 10^7 = 40 MB -> aman di 256 MB (Codeforces)
- Array int 5*10^7 = 200 MB -> berbahaya, mendekati limit
- Array int 10^8 = 400 MB -> MLE pasti di Codeforces, OK di AtCoder
- int[n][n] n=10^4 = 400 MB -> MLE
- int[n][n] n=10^3 = 4 MB -> aman

=== Tips Menghemat Memori ===
1. Pakai int bila nilai <= 2*10^9 (cukup), bukan long long
2. Pakai vector<vector<int>> bukan int[n][m] untuk variable size
3. Kompres koordinat: nilai besar -> rentang [0, n)
4. Reuse array: bersihkan dengan fill() bukan alokasi baru
5. Bitset untuk boolean array: 8x lebih hemat dari vector<char>
6. Hindari std::map jika std::unordered_map cukup (lebih ringan)

Bedah Kode Baris-per-Baris #

(n * 4 / 1024 / 1024.0): konversi byte → MB. Untuk n = 10^6, hasilnya 3.81 MB. Operator precedence: n * 4 dulu, kemudian / 1024 (jadi kilobyte), kemudian / 1024.0 (jadi MB). Pakai 1024.0 (double) untuk menghindari integer truncation.
int array[10^6] (4 MB): array int berukuran 10^6 memakan 4 MB — jauh di bawah batas 256 MB. Aman untuk mayoritas soal Codeforces.
int array[10^7] (40 MB): 10^7 elemen masih aman (40 MB / 256 MB = 16%). Tetapi 5×10^7 sudah 200 MB — mendekati batas.
int[n][n] (n=10^4): matriks n × n dengan n = 10^4 = 4 × 10^8 byte = 400 MB → MLE. Matriks 2D sangat rakus memori — batasi n ≤ 1000 untuk aman.
std::map<int,int> ~10 MB untuk n=10^5: setiap node red-black tree memakai ~80 byte (key, value, color, 3 pointer). Untuk n=10^5, total 8 MB + overhead.
std::unordered_map<int,int> ~8 MB untuk n=10^5: hash table memakai ~32 byte per elemen + bucket vector. Lebih ringan dari std::map tetapi masih lebih mahal dari vector<int>.

Konsekuensi Praktis untuk Soal CP #

Tabel ringkas aturan praktis:

Constraint `n`	Batas Waktu	Batas Memori	Struktur Aman
`n ≤ 10^3`	O(n²)	O(n²) = 4 KB	Matriks 2D OK
`n ≤ 10^4`	O(n²) ≈ 10^8 ops	O(n²) = 40 MB	Matriks 2D OK
`n ≤ 10^5`	O(n log n)	O(n) = 4 MB	Array linear
`n ≤ 10^6`	O(n log n)	O(n) = 4–8 MB	Array linear
`n ≤ 10^7`	O(n)	O(n) = 40 MB	Array int OK
`n ≤ 10^8`	O(n)	O(n) = 400 MB	MLE Codeforces, OK AtCoder

Teknik Menghemat Memori #

Teknik	Penghematan	Kapan Dipakai
`int` bukan `long long`	2x	Nilai `≤ 2×10^9`
Kompresi koordinat	`O(log n)` → `O(n)`	Nilai besar, hanya butuh urutan
`vector<bool>` atau `bitset<N>`	8x	Array boolean besar
Reuse array	n× → 1×	Multiple test case dengan struktur sama
Sliding window	O(n) → O(k)	Hanya butuh jendela terakhir
Adjacency list bukan matriks	O(V²) → O(V+E)	Graph sparse

Ringkasan #

Batas standar: Codeforces 1–2 detik / 256 MB, AtCoder 2 detik / 1024 MB.
Operasi per detik: ~10^8 sederhana, ~10^7 kompleks, ~10^6 sangat kompleks.
Memori per struktur: int[n] = 4 MB untuk 10^6, 40 MB untuk 10^7, 400 MB untuk 10^8.
Matriks n × n rakus memori — n = 10^4 sudah 400 MB → MLE.
std::map lebih berat dari std::unordered_map (~80 B/node vs ~32 B); std::vector paling ringan (4 B/int).
Teknik hemat memori: pakai int bukan long long bila cukup, kompresi koordinat, bitset untuk boolean, reuse array di multiple test case.