Một số lỗi thường gặp trong lập trình

Bài viết này tổng hợp một số lỗi thường gặp trong lập trình thi đấu mà chắc hẳn bạn đã gặp phải ít nhất một lần và phải tốn hàng giờ để tìm ra nguyên nhân hoặc không hiểu lý do thật sự đằng sau là gì.

Bài viết được dịch từ blog trên codeforces của tác giả YouKn0wWho. Bài viết đầy đủ của tác giả có thể tìm thấy tại blog này.

Các code ví dụ trong bài viết này được viết bằng C++, ngôn ngữ được sử dụng phổ biến nhất trong CP.

Giờ thì hãy cùng đi vào bài viết nhé.

Một số lỗi thường gặp

`🔍 Lỗi thường gặp 1`

Hãy xem đoạn code dưới đây:

Code

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

int main() {
  int a = 1000'000'000, b = 1000'000'000;
  long long product = a * b;
  cout << product << '\n';
  return 0;
}

Kết quả mong muốn là ~10^{18}~. Nhưng khi chạy đoạn code trên thì bạn lại nhận được một kết quả khác?
Lý do

Kể cả khi bạn đã khai báo biến product là long long, nhưng có vẻ như vẫn bị tràn số? Thực tế, đầu tiên trình biên dịch sẽ nhân a với b sau đó mới gán kết quả của phép nhân cho biến product mà cả a và b đều mang kiểu int do đó kết quả sẽ mang kiểu int, gây tràn số đối với kết quả ~10^{18}~.
Cách khắc phục

Typecast - Ép kiểu!
Code
#include <bits/stdc++.h> using namespace std; int main() { int a = 1000'000'000, b = 1000'000'000; long long product = (long long) a * b; cout << product << '\n'; return 0; }

`🔍 Lỗi thường gặp 2`

Hãy xem đoạn code dưới đây:

Code

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

int get_size(vector<int> a) {
  return (int) a.size();
}
int main() {
  int n = 1000000;
  vector<int> a(n, 0);
  long long sum = 0;
  for (int i = 1; i <= n; i++) {
    sum += get_size(a);
  }
  cout << sum << '\n';
  return 0;
}

Hãy chạy thử đoạn code này ở máy của bạn. Ở đây ta chỉ duyệt từ ~1~ đến ~n~ nên độ phức tạp mong muốn là ~\mathcal{O}(n)~. Nhưng dường như không phải như vậy?
Lý do
- Thật ra đoạn code trên có độ phức tạp ~\mathcal{O}(n^2)~.
- Lý do là vì ta đang truyền vector theo kiểu tham trị - có nghĩa là mỗi lần ta gọi hàm get_size thì một bản sao của a sẽ được tạo ra sau đó truyền vào hàm get_size.
Cách khắc phục

Truyền theo kiểu tham chiếu - ta chỉ truyền địa chỉ của vector vào hàm
Code
#include <bits/stdc++.h> using namespace std; int get_size(vector<int> &a) { return (int) a.size(); } int main() { int n = 1000000; vector<int> a(n, 0); long long sum = 0; for (int i = 1; i <= n; i++) { sum += get_size(a); } cout << sum << '\n'; return 0; }
Xem thêm: Difference Between Call by Value and Call by Reference.

Edit: Nếu bạn không muốn nội dung của mảng a bị thay đổi khi truyền tham chiếu thì có thể thêm từ khóa const: const vector<int> &a.

🔍 `Lỗi thường gặp 3`

Hãy xem đoạn code dưới đây:

Code

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

const int N = 100000;
int main() {
  int test_cases = 100000;
  while (test_cases--) {
    int n; cin >> n;
    vector<int> a(N, 0);
    int sum = 0;
    for (int i = 0; i < n; i++) {
      sum += a[i];
    }
    cout << sum << '\n';
  }
  // dữ liệu đảm bảo tổng các giá trị n <= 100000
  return 0;
}

Chú ý rằng dữ liệu đảm bảo tổng các giá trị n <= 100000. Vậy có tổng cộng bao nhiêu thao tác đoạn code trên thực hiện trong trường hợp xấu nhất?

Trả lời

Trong trường hợp xấu nhất là khoảng ~10^{10}~ vì ta khai báo vector với kích thước ~10^5~ mỗi lần lặp.

Cách khắc phục

Khai báo vector với kích thước đủ dùng trong mỗi lần lặp.

Code

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

const int N = 100000;
int main() {
  int test_cases = 100000;
  while (test_cases--) {
    int n; cin >> n;
    vector<int> a(n, 0);
    int sum = 0;
    for (int i = 0; i < n; i++) {
      sum += a[i];
    }
    cout << sum << '\n';
  }
  // dữ liệu đảm bảo tổng các giá trị n <= 100000
  return 0;
}

🔍 `Lỗi thường gặp 4`

Hãy tìm lỗi trong đoạn code dưới đây?

Code

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

int main() {
  int n = 5;
  int a[n];
  memset(a, 1, sizeof a);
  for (int i = 0; i < n; i++) {
    cout << a[i] << ' ';
  }
  cout << '\n';
  return 0;
}

Đầu ra mong muốn của đoạn code trên là 1 1 1 1 1. Nhưng khi chạy thì đoạn code trên lại cho ra kết quả 16843009 16843009 16843009 16843009 16843009
Lý do
- Hàm memset thực ra được dùng cho kiểu char hoặc 1 byte. Xem thêm: Memset in C++.
- Có thể bạn đã từng gặp dòng code memset(a, -1, sizeof a) hoặc memset(a, 0, sizeof a). Thật ra là vì nó chỉ tình cờ đúng với trường hợp giá trị là ~0~ và ~-1~. Xem thêm tại comment này để hiểu lý do.
- Dùng memset để set giá trị các phần tử trong mảng thành ~0~ hoặc ~-1~ sẽ nhanh hơn việc lặp qua mảng và set từng phần tử. Nhưng hãy cẩn thận khi sử dụng hàm này với những giá trị khác.

🔍 `Lỗi thường gặp 5`

Đừng dùng endl!. Nếu code của bạn cần in một số lượng lớn các dòng thì việc sử dụng endl sẽ chậm hơn '\n' rất nhiều.

Lý do

Xem thêm: std::endl vs \n in C++

🔍 `Lỗi thường gặp 6`

Đừng dùng hàm pow() cho việc tính toán trên các số nguyên.
Lý do
- Đừng dùng hàm pow() trừ khi bạn bắt buộc phải dùng bởi vì đôi khi sai số của kết quả đầu ra là khá lớn. Ví dụ, dễ thấy kết quả của ~\log_2(1 << 30)~ sẽ là ~30~. Nhưng đôi khi kết quả lại là ~29.9999999999999~ và khi được chuyển thành kiểu int, kết quả trả về là 29.
- Tương tự, hàm pow() nhận các đối số có kiểu double, ví dụ đối với pow(5, 2) thì kết quả mong muốn là ~5^2 = 25.00~. Nhưng đôi khi kết quả lại là ~24.9999999999999~ và khi chuyển thành kiểu int, kết quả cuối cùng là ~24~. Bạn có thể dùng round(pow(a, n)) trong trường hợp này để tránh việc sai số hoặc có thể duyệt trâu khi n không quá lớn.

🔍 `Lỗi thường gặp 7`

Hãy chạy thử đoạn code dưới đây:

Code

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

int main() {
  vector<int> v;
  cout << v.size() - 1 << '\n';;
  return 0;
}

Kết quả mong muốn là ~-1~. Nhưng khi chạy lại cho ra kết quả 18446744073709551615!

Lý do

Xem thêm tại đây, v.size() sẽ trả về kết quả mang kiểu dữ liệu size_type.

Cách khắc phục

Ép kiểu dữ liệu!

Code

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

int main() {
  vector<int> v;
  cout << (int) v.size() - 1 << '\n';;
  return 0;
}

Đó là lý do mà đoạn code dưới đây sẽ chạy gần như vô tận

Code

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

int main() {
  vector<int> v;
  for (int i = 0; i < v.size() - 1; i++) {
    // do something
  }
  return 0;
}

🔍 `Lỗi thường gặp 8`

Dùng cerr là một lựa chọn tốt để debug code của bạn vì nó không ảnh hưởng đến dòng xuất chuẩn (standard output). Nhưng hãy nhớ comment hoặc xóa các dòng cerr trước khi nộp code của bạn lên các hệ thống OJ vì có thể sẽ bị TLE.
Xem thêm: Debugging in C++.

🔍 `Lỗi thường gặp 9`

Hãy xem đoạn code dưới đây:

Code

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

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  for (int i = 1; i <= 3; i++) {
    cout << i << '\n';
    printf("%d\n", i + 10);
  }
  return 0;
}

Đầu ra mong muốn:
output
```
1
11
2
12
3
13
```
Nhưng thực tế kết quả lại không như mong muốn. Tùy vào máy mà sẽ cho kết quả khác nhau. Một kết quả đầu ra ví dụ:
output
```
1
2
3
11
12
13
```
Về cơ bản, cout và printf dường như đang hoạt động độc lập với nhau.

Lý do

Đó là do sự đồng bộ hóa đã bị vô hiệu hóa khi sử dụng dòng ios_base::sync_with_stdio(0). Tìm hiểu thêm: std::ios_base::sync_with_stdio.

Cách khắc phục

Không nên pha trộn các luồng xuất giữa C-style và C++-style sau khi đã dùng ios_base::sync_with_stdio(0).

🔍 `Lỗi thường gặp 10`

Hãy xem đoạn code dưới đây:

Code

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

int main() {
  int a = 1, b = 3;
  // chúng ta muốn tính b & 3, sau đó cộng với a
  int result = a + b & 3;
  cout << result << '\n';
  return 0;
}

Kết quả đầu ra mong muốn là 4, nhưng đoạn code trên lại cho ra kết quả là 0!.
Lý do
- Độ ưu tiên của toán tử + cao hơn toán tử &. Vì vậy toán tử + sẽ được thực hiện trước, do đó a + b = 4 sẽ được thực hiện đầu tiên, sau đó mới đến toán tử &, nên 4 & 3 sẽ được thực thi sau cùng và cho kết quả là 0.
- Xem thêm độ ưu tiên của các toán tử trong C++: C++ Operator Precedence.
  Cách khắc phục
  
  Dùng cặp ngoặc tròn trong các trường hợp bạn không chắc chắn về độ ưu tiên của các toán tử.
  Code
  
  #include <bits/stdc++.h> using namespace std; int main() { int a = 1, b = 3; int result = a + (b & 3); cout << result << '\n'; return 0; }
- Một trường hợp tương tự khác khá kinh điển đó là 1 << n - 1 không phải ~2^n - 1~ mà là ~2^{n - 1}~ vì toán tử - có độ ưu tiên cao hơn <<.

🔍 `Lỗi thường gặp 11`

Hãy xem tính đúng đắn của đoạn code dưới đây

Code

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

const int INF = (int) 1e6;
int main() {
  int minimum = INF;
  for (int i = 1; i <= 10; i++) {
    int x;
    cin >> x; // giá trị của x có thể lên đến 10000
    minimum = min(minimum, x * x);
  }
  cout << minimum << '\n';
  return 0;
}

Nếu không đúng thì vấn đề nằm ở đâu?
Lời giải
- Ở đây giá trị ~x~ có thể lên đến ~10^4~ do đó giá trị của ~x * x~ có thể lên đến ~10^8~. Nhưng trong đoạn code trên biến minimum được khởi tạo giá trị ~10^6~ là không đủ lớn.
- Do đó luôn chắc chắn rằng code của bạn khởi tạo giá trị các biến là đủ lớn (hoặc đủ nhỏ).
Edit: thông thường tác giả dùng giá trị 0x3f3f3f3f cho kiểu int hoặc 0x3f3f3f3f3f3f3f3f cho kiểu long long. Các giá trị này thường là đủ lớn đối với giới hạn đề bài (~10^9~ đối với int hoặc ~10^{18}~ đối với long long) và không tràn số khi cộng INF + INF.

🔍 `Lỗi thường gặp 12`

Đoạn code dưới đây tính số lần xuất hiện lớn nhất trong mảng.

Code

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

unordered_map<int, int> mp;
int main() {
  int n = 300000;
  for (int i = 1; i <= n; i++) {
    int x; cin >> x;
    mp[x]++;
  }
  int max_occurrence = 0;
  for (auto [val, cnt] : mp) {
    max_occurrence = max(max_occurrence, cnt);
  }
  cout << max_occurrence << '\n';
  return 0;
}

Có thể thấy đoạn code này chạy khá nhanh, nhưng với một số input đặc biệt sẽ bị TLE.
Lý do
- Lý do là vì chúng ta sử dụng unordered_map! Trong trường hợp xấu nhất đoạn code trên có độ phức tạp ~\mathcal{O}(n^2)~, bởi vì unordered_map là một hash map nên có thể tốn hơn ~\mathcal{O}(1)~ thao tác để thêm hoặc truy cập phần tử trong trường hợp input không được sinh ngẫu nhiên.
- Tham khảo thêm: Blowing up unordered_map, and how to stop getting hacked on it.

🔍 `Lỗi thường gặp 13`

Hãy thử xóa một phần tử trong multiset

Code

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

int main() {
  multiset<int> se({1, 1, 2, 2, 2, 3, 4, 5, 5});
  // xóa một phần tử 2 ra khỏi multiset
  se.erase(2);
  // in các phần tử sau khi xóa để kiểm tra
  for (auto val : se) {
    cout << val << ' ';
  }
  cout << '\n';
  return 0;
}

Khi chạy đoạn code trên thì output nhận được là 1 1 3 4 5 5 thay vì 1 1 2 2 3 4 5 5. Có vẻ như ta đã vô tình xóa tất cả các phần tử 2 trong multiset thay vì một phần tử.
Lý do

Lý do là vì nếu truyền một phần tử vào hàm erase() của multiset thì tất cả các phần tử này trong multiset sẽ bị xóa. Ngược lại nếu bạn truyền một iterator thì chỉ phần tử được trỏ đến mới bị xóa. Xem thêm: std::multiset::erase.
Cách khắc phục
```
#include <bits/stdc++.h>
using namespace std;

int main() {
  multiset<int> se({1, 1, 2, 2, 2, 3, 4, 5, 5});
  // hàm find() sẽ trả về iterator trỏ đến vị trí xuất hiện đầu tiên của phần tử 2
  se.erase(se.find(2));
  for (auto val: se) {
    cout << val << ' ';
  }
  cout << '\n';
  // 1 1 2 2 3 4 5 5 
  return 0;
}
```

🔍 `Lỗi thường gặp 14`

Hãy chạy thử đoạn code dưới đây:

Code

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

int main() {
  map<int, int> mp;
  // thêm các số từ 1 đến 5 vào map
  for (int i = 1; i <= 5; i++) {
    mp[i]++;
  }
  int cnt = 0;
  // kiểm tra xem có bao nhiêu số từ 1 đến 10 tồn tại trong map 
  for (int i = 1; i <= 10; i++) {
    if (mp[i]) {
      ++cnt;
    }
  }
  // in kích thước của map
  cout << (int) mp.size() << '\n';
  return 0;
}

Hãy thử đoán xem output có phải là 5 hay không?

Giải thích

Thật ra output của đoạn code trên sẽ là 10.

Lý do là vì câu lệnh if (mp[i]) sẽ thêm các phần tử i vào map nếu phần tử i chưa có trong map. Lỗi này đôi khi có thể dẫn đến MLE (tràn bộ nhớ).

Cách khắc phục

Dùng hàm find() hoặc count() để kiểm tả một phần tử có trong map hay không trước khi dùng toán tử []

Code

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

int main() {
  map<int, int> mp;
  // thêm các số từ 1 đến 5 vào map
  for (int i = 1; i <= 5; i++) {
    mp[i]++;
  }
  int cnt = 0;
  // kiểm tra có bao nhiêu số từ 1 đến 10 tồn tại trong map 
  for (int i = 1; i <= 10; i++) {
    if (mp.find(i) != mp.end()) {
      ++cnt;
    }
    // hoặc dùng if (mp.count(i)) {}
  }
  // in kích thước của map
  cout << (int) mp.size() << '\n';
  return 0;
}

🔍 `Lỗi thường gặp 15`

Đoạn code dưới đây tính tổng các số tự nhiên dùng set:

Code

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

int main() {
  int n = 100000;
  set<int> se;
  for (int i = 1; i <= n; i++) {
    se.insert(i);
  }
  // tính tổng các số tự nhiên từ 1 đến n
  long long sum = 0;
  for (int i = 1; i <= n; i++) {
    // tìm iterator trỏ đến phần tử nhỏ nhất mà >= i
    // trong trường hợp này chính là i
    auto it = lower_bound(se.begin(), se.end(), i);
    sum += *it; // *it = i
  }
  cout << sum << '\n';
  return 0;
}

Dễ thấy đoạn code này có độ phức tạp là ~\mathcal{O}(n \times \log n)~ nhưng lại không thể chạy trong giới hạn ~1~ giây với ~n = 10^5~?
Lý do
- Thật ra độ phức tạp của đoạn code trên là ~\mathcal{O}(n^2)~.
- Nhưng hàm lower_bound là ~\mathcal{O}(\log n)~ thì tại sao lại là ~\mathcal{O}(n^2)~?
- Thật ra hai hàm std::lower_bound và std::set::lower_bound là hai hàm hoàn toàn khác nhau. Xem thêm tại đây. Tương tự với upper_bound.
  Cách khắc phục
  
  Dùng set.lower_bound(value) với độ phức tạp là ~\mathcal{O}(\log n)~
  Code
  
  #include <bits/stdc++.h> using namespace std; int main() { int n = 100000; set<int> se; for (int i = 1; i <= n; i++) { se.insert(i); } // tính tổng các số tự nhiên từ 1 đến n long long sum = 0; for (int i = 1; i <= n; i++) { // tìm iterator trỏ đến phần tử nhỏ nhất mà >= i // trong trường hợp này chính là i auto it = se.lower_bound(i); sum += *it; // *it = i } cout << sum << '\n'; return 0; }

🔍 `Lỗi thường gặp 16`

Hãy xem đoạn code dưới đây:

Code

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

int main() {
  int n = 1000000;
  string s = "";
  for (int i = 0; i < n; i++) {
    s = s + 'a'; // nối thêm `a` vào chuỗi
  }
  cout << s << '\n';
  return 0;
}

Hãy thử đoán độ phức tạp của đoạn code trên
Lời giải
- Mặc dù chỉ duyệt n lần nhưng độ phức tạp của đoạn code trên là ~\mathcal{O}(n^2)~.
- Lý do là vì khi gán s = s + 'a' thì ở vế bên phải truy cập toàn bộ chuỗi s (với kích thước ~\mathcal{O}(n)~).
  Cách khắc phục
  
  Dùng cú pháp s += 'a' để không phải truy cập toàn bộ chuỗi mỗi lần gán
  Code
  
  #include <bits/stdc++.h> using namespace std; int main() { int n = 1000000; string s = ""; for (int i = 0; i < n; i++) { s += 'a'; // nối thêm `a` vào chuỗi } cout << s << '\n'; return 0; }

🔍 `Lỗi thường gặp 17`

Hãy xem đoạn code đơn giản dưới đây:

Code

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

int main() {
  int test_cases;
  cin >> test_cases;
  // nhập vào một mảng n phần tử
  // in ra YES nếu kích thước mảng là 1 ngược lại in ra NO
  while (test_cases--) {
    int n; // kích thươc mảng
    cin >> n;
    if (n == 1) {
      cout << "YES\n";
      continue;
    }
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    cout << "NO\n";
  }
  return 0;
}

Nhiệm vụ của bạn là tìm bug trong đoạn code trên

Bug

Trong trường hợp ~n = 1~ thì đoạn code in ra YES và tiếp tục vòng lặp mới ngay cả khi chưa nhập phần tử của mảng. Điều này dẫn đến việc sẽ bị WA trong một số trường hợp.

Test ví dụ

Cách khắc phục

Đọc hết toàn bộ dữ liệu của một testcase trước khi bạn muốn continue khi kiểm tra các trường hợp cơ bản.

Code

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

int main() {
  int test_cases;
  cin >> test_cases;
  // nhập vào một mảng n phần tử
  // in ra YES nếu kích thước mảng là 1 ngược lại in ra NO
  while (test_cases--) {
    int n; // kích thươc mảng
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    if (n == 1) {
      cout << "YES\n";
      continue;
    }
    cout << "NO\n";
  }
  return 0;
}

🔍 `Lỗi thường gặp 18`

Đoạn code dưới đây đếm số phần tử phân biệt trong mảng:

Code

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

const int MAX_ELEMENT = (int) 1e5;
int cnt[MAX_ELEMENT + 1];

int main() {
  int test_cases;
  cin >> test_cases;
  while (test_cases--) {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
      int x;
      cin >> x;
      cnt[x]++;
    }
    int unique_elements = 0;
    for (int i = 0; i <= MAX_ELEMENT; i++) {
      if (cnt[i] > 0) {
        unique_elements++;
      }
    }
    cout << unique_elements << '\n';
  }
  return 0;
}

Hãy thử tìm bug trong đoạn code trên

Bug

Trong bài này có nhiều testcase nhưng đoạn code trên lại không reset lại mảng cnt. Do đó dữ liệu của các testcase trước vẫn còn lưu trong mảng cnt dẫn đến WA.

Test ví dụ

Cách khắc phục

Reset lại mảng cnt sau mỗi testcase

Code

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

const int MAX_ELEMENT = (int) 1e5;
int cnt[MAX_ELEMENT + 1];

int main() {
  int test_cases;
  cin >> test_cases;
  while (test_cases--) {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
      int x;
      cin >> x;
      cnt[x]++;
    }
    int unique_elements = 0;
    for (int i = 0; i <= MAX_ELEMENT; i++) {
      if (cnt[i] > 0) {
        unique_elements++;
      }
    }
    cout << unique_elements << '\n';

    // reset lại mảng cnt
    for (int i = 0; i <= MAX_ELEMENT; i++) {
      cnt[i] = 0;
    }
  }
  return 0;
}

🔍 `Lỗi thường gặp 19`

Có khá nhiều lỗi dễ mắc phải khi tính toán liên quan đến phép toán module.

Ví dụ

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

const int mod = 1e9 + 7;
int main() {
  int a = 1e9, b = 1e9, c = 1e9;
  int sum = (a + b + c) % mod;
  cout << sum << '\n';
  int product = a * b % mod;
  cout << product << '\n';
  int random = 1LL * a * (b * c % mod) % mod;
  cout << random << '\n';
  a = 1e8;
  int sub = (a - b) % mod; 
  cout << sub << '\n';
  return 0;
}

Hãy cùng đi tìm bug nào

Bug

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

const int mod = 1e9 + 7;
int main() {
  // 0 <= a, b, c < mod
  int a = 1e9, b = 1e9, c = 1e9;

  int sum = (a + b + c) % mod; 
  // tràn số vì (a + b + c) > INT_MAX (2147483647)
  // cách tốt hơn: ((a + b) % mod + c) % mod
  cout << sum << '\n';

  int product = a * b % mod;
  // tràn số vì a * b > INT_MAX
  // cách tốt hơn: 1LL * a * b % mod
  cout << product << '\n';

  int random = 1LL * a * (b * c % mod) % mod; 
  // tràn số ở phần (b * c % mod)
  // cách đúng: 1LL * a * (1LL * b * c % mod) % mod
  // cách tốt hơn: 1LL * a * b % mod * c % mod
  cout << random << '\n';

  a = 1e8;
  int sub = (a - b) % mod; 
  // không tràn số nhưng khi a < b thì kết quả sẽ ra số âm
  // cách tốt hơn: (a - b + mod) % mod
  cout << sub << '\n';

  // Hãy đảm bảo sau mỗi phép toán
  // thì tất cả các biến mang giá trị trong đoạn [0, mod - 1]
  return 0;
}

🔍 `Lỗi thường gặp 20`

Hãy xem đoạn code dưới đây:

Code

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

int main() {
  long long val = (long long) 1e12;
  vector<long long> v({val, val, val});
  // tính tổng các phần tử
  long long sum = accumulate(v.begin(), v.end(), 0);
  cout << sum << '\n';
  return 0;
}

Khi chạy đoạn code trên in ra ~2112827392~ thay vì ~3 \cdot 10^{12}~?

Lý do

Giá trị khởi tạo trong hàm accumulate() (giá trị ~0~) mang kiểu int nên kết quả trả về là int gây tràn số. Xem thêm: std::accumulate.

Cách khắc phục

Truyền giá trị khởi tạo mang kiểu long long (0LL)

Code

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

int main() {
  long long val = (long long) 1e18;
  vector<long long> v({val, val, val});
  // tính tổng các phần tử
  long long sum = accumulate(v.begin(), v.end(), 0LL);
  cout << sum << '\n';
  return 0;
}

Với double

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

int main() {
  vector<double> v({1.23, 2.05, 3.003});
  // tính tổng các phần tử
  double sum = accumulate(v.begin(), v.end(), 0); // cách đúng: 0.0
  cout << sum << '\n';
  // kết quả in ra là 6 thay vì 6.283
  return 0;
}

🔍 `Lỗi thường gặp 21`

Dùng sqrt() và cbrt() cho các số nguyên một cách trực tiếp có thể gây ra các vấn đề về sai số và cho kết quả sai.

Một trong những cách tốt nhất để tính căn bậc hai của một số:

Code

long long x = (long long) 1e18 - 1;
long long k = sqrtl(x);
while (k * k < x) ++k;
while (k * k > x) --k;
cout << k << '\n';

Edit: Cho trước một số ~s~. Tìm giá trị ~n~ lớn nhất sao cho tổng ~n~ số nguyên đầu tiên không vượt quá ~s~.

Code

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

int main() {
  int s;
  cin >> s;
  // tìm giá trị n lớn nhất sao cho n * (n + 1) / 2 <= s
  // <=> n * (n + 1) <= 2 * s
  // lấy xấp xỉ n = sqrt(2 * s)
  int n = (int) sqrt(2 * s);
  while (n * (n + 1) < 2 * s) ++n;
  while (n * (n + 1) > 2 * s) --n;
  cout << n << '\n';
  return 0;
}

🔍 `Lỗi thường gặp 22`

Hãy xem đoạn code dưới đây:

Code

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

int main() {
  int n = 100000;
  multiset<int> se;
  // thêm n phần tử 1 vào multiset
  for (int i = 1; i <= n; i++) {
    se.insert(1);
  }
  long long tot = 0;
  // lặp n lần và đếm xem có bao nhiêu phần tử 1 trong multiset
  for (int i = 1; i <= n; i++) {
    tot += se.count(1);
  }
  cout << tot << '\n';
  return 0;
}

Hãy thử đoán độ phức tạp của đoạn code trên
Lời giải
- Độ phức tạp của đoạn code trên là ~\mathcal{O}(n^2)~.
- Hàm std::multiset::count có độ phức tạp là ~\mathcal{O}(\log N + K)~ với ~N~ và ~K~ lần lượt là kích thước và số lần xuất hiện của phần tử trong multiset. Trong trường hợp này phần tử ~1~ xuất hiện tổng cộng ~n~ lần. Do đó hãy cẩn thận khi dùng hàm std::multiset::count.
- Nếu muốn kiểm tra một phần tử có tồn tại trong multiset hay không thì ta có thể dùng hàm find thay vì hàm count.

🔍 `Các lỗi khác`

Tránh việc dùng hàm insert hoặc erase (ví dụ set.erase, vector.insert) khi đang duyệt qua các phần tử dùng vòng lặp ví dụ như for (auto val : container). Bởi vì đối với các container động thì việc thêm và xóa có thể thay đổi cấu trúc của container. Do đó việc duyệt song song với việc thêm và xóa có thể dẫn đến một số hành vi không mong muốn.
Dùng setprecision cho việc in các số thực, nếu không có thể bị WA do lỗi sai số. Xem thêm tại đây.
Không nên dùng hàm rand() cho việc sinh số ngẫu nhiên. Ngoài ra giá trị lớn nhất có thể từ hàm rand() là RAND_MAX, ở một số hệ thống hoặc máy chấm thì RAND_MAX ~= 2^{15} - 1 = 32767~, khá nhỏ so với INT_MAX. Cách thay thế tốt hơn có thể xem tại bài viết này.
Chỉ khai báo các biến khi bạn cần dùng đến thay vì khai báo int a, b, c, d, e, f, x, y, z; và hằng hà các biến khác ở đầu code. Việc này giúp bạn tránh được các lỗi phát sinh khi sử dụng cùng một biến ở hai hoặc nhiều nơi khác nhau.
Hạn chế việc lạm dụng long long vì long long có thể chậm hơn đến ~2~ lần so với int. Do đó chỉ nên dùng long long khi cần thiết.
Trong trường hợp bạn muốn đếm số bit ~1~ của một số kiểu long long thì hãy dùng hàm __builtin_popcountll thay vì __builtin_popcount.
Trong C++, comparator nên trả về false khi các đối số là bằng nhau. Nếu không code của bạn có thể sẽ bị Runtime Error. Xem thêm bài viết này.
Hầu hết những trường hợp gặp lỗi Runtime Error là do khai báo mảng với kích thước không đủ lớn. Do đó hãy kiểm tra kỹ giới hạn của đề bài trước khi bắt tay vào code.
long long x = 1 << 40 vẫn sẽ bị tràn số vì 1 mang kiểu int nên kết quả sẽ mang kiểu int, mà ~2^{40}~ lớn hơn nhiều so với giới hạn của kiểu int. Giải pháp là 1LL << 40 (ép kiểu 1 thành long long) xem thêm: What is 1LL or 2LL in C and C++?.
Khi so sánh hai số thực, thay vì dùng if (a == b) thì hãy dùng if (abs(a - b) < EPS) với EPS = 1e-9 hoặc các giá trị đủ nhỏ khác để tránh bị sai số.
Nếu bạn muốn làm tròn lên (ceiling) kết quả của a / b trong đó a và b là các số nguyên dương, hãy dùng (a + b - 1) / b thay vì ceil(1.0 * a / b). Với làm tròn xuống (floor) thì chỉ cần a / b là đủ vì kết quả sẽ được tự động làm tròn xuống số nguyên gần nhất.
Trong trường hợp bạn muốn tính ~\lfloor \log_2 n\rfloor~ (tương đương việc tìm index của bit ~1~ lớn nhất trong ~n~) của một số nguyên dương ~n~, hãy dùng __lg(n).
Đừng dùng hash tràn số (mod ~2^{64}~), xem thêm Anti-hash test. Và trong một số contest, nếu chỉ hash với một cơ số nguyên tố và một số mod thì có thể bạn sẽ WA khi gặp anti-hash test. Xem thêm On the mathematics behind rolling hashes and anti-hash tests. Khi đó hãy dùng ít nhất hai cơ số nguyên tố và hai số mod.

Tham khảo

https://codeforces.com/blog/entry/111217