---
title: Các lỗi phổ biến trong competitive programming và cách để không bao giờ gặp lại
description: Bài viết này đề cập đến một số lỗi phổ biến trong competitve programming mà chắc hẳn các bạn đã gặp phải ít nhất một lần mà không hiểu chuyện gì đang xảy ra.
tags: cp-common-mistakes
date: 8/19/2023
---
# Các lỗi phổ biến trong competitive programming và cách để tránh
## Lời dẫn
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](https://codeforces.com/) của tác giả [ YouKn0wWho](https://codeforces.com/profile/YouKn0wWho). Bài viết đầy đủ của tác giả có thể tìm thấy tại [blog này](https://codeforces.com/blog/entry/111217).
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](https://usaco.guide/general/intro-cp).
Giờ thì hãy cùng đi vào bài viết nhé.
## Các lỗi thường gặp
### 🔍 `Lỗi thường gặp 1`
- Hãy xem đoạn code dưới đây:
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
- 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?
<details>
<summary>Lý do</summary>
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}$.
<details>
<summary>Cách khắc phục</summary>
[Typecast](https://www.programiz.com/cpp-programming/type-conversion) - Ép kiểu!
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
</details>
</details>
### 🔍 `Lỗi thường gặp 2`
- Hãy xem đoạn code dưới đây:
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
- 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?
<details>
<summary>Lý do</summary>
- 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`.
<details>
<summary>Cách khắc phục</summary>
Truyền theo kiểu tham chiếu - ta chỉ truyền địa chỉ của `vector` vào hàm
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
Xem thêm: [Difference Between Call by Value and Call by Reference](https://www.geeksforgeeks.org/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`.
</details>
</details>
### 🔍 `Lỗi thường gặp 3`
- Hãy xem đoạn code dưới đây:
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
- 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?
<details>
<summary>Trả lời</summary>
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.
<details>
<summary>Cách khắc phục</summary>
Khai báo vector với kích thước đủ dùng trong mỗi lần lặp.
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
</details>
</details>
### 🔍 `Lỗi thường gặp 4`
- Hãy tìm lỗi trong đoạn code dưới đây?
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
- Đầ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`
<details>
<summary>Lý do</summary>
- Hàm `memset` thực ra được dùng cho kiểu `char` hoặc `1 byte`. Xem thêm: [Memset in C++](https://www.geeksforgeeks.org/memset-in-cpp/).
- 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](https://codeforces.com/blog/entry/18163?#comment-230615) để 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.
</details>
### 🔍 `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.
<details>
<summary>Lý do</summary>
Xem thêm: [std::endl vs \n in C++](https://www.geeksforgeeks.org/endl-vs-n-in-cpp/)
</details>
### 🔍 `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.
<details>
<summary>Lý do</summary>
- Đừ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.
</details>
### 🔍 `Lỗi thường gặp 7`
- Hãy chạy thử đoạn code dưới đây:
<details>
<summary>Code</summary>
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v;
cout << v.size() - 1 << '\n';;
return 0;
}
```
</details>
- Kết quả mong muốn là $-1$. Nhưng khi chạy lại cho ra kết quả `18446744073709551615`!
<details>
<summary>Lý do</summary>
Xem thêm [tại đây](https://codeforces.com/blog/entry/44795), `v.size()` sẽ trả về kết quả mang kiểu dữ liệu `size_type`.
<details>
<summary>Cách khắc phục</summary>
Ép kiểu dữ liệu!
<details>
<summary>Code</summary>
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v;
cout << (int) v.size() - 1 << '\n';;
return 0;
}
```
</details>
</details>
<br>
Đó là lý do mà đoạn code dưới đây sẽ chạy gần như vô tận
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
</details>
### 🔍 `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++](https://codeforces.com/blog/entry/65543).
### 🔍 `Lỗi thường gặp 9`
- Hãy xem đoạn code dưới đây:
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
- Đầu ra mong muốn:
<details>
<summary>output</summary>
```
1
11
2
12
3
13
```
</details>
- 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ụ:
<details>
<summary>output</summary>
```
1
2
3
11
12
13
```
</details>
- Về cơ bản, `cout` và `printf` dường như đang hoạt động độc lập với nhau.
<details>
<summary>Lý do</summary>
Đó 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](https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio).
<details>
<summary>Cách khắc phục</summary>
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)`.
</details>
</details>
### 🔍 `Lỗi thường gặp 10`
- Hãy xem đoạn code dưới đây:
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
- 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`!.
<details>
<summary>Lý do</summary>
- Độ ư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](https://en.cppreference.com/w/cpp/language/operator_precedence).
<details>
<summary>Cách khắc phục</summary>
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ử.
<details>
<summary>Code</summary>
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int a = 1, b = 3;
int result = a + (b & 3);
cout << result << '\n';
return 0;
}
```
</details>
</details>
<br>
- 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 `<<`.
</details>
### 🔍 `Lỗi thường gặp 11`
- Hãy xem tính đúng đắn của đoạn code dưới đây
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
- Nếu không đúng thì vấn đề nằm ở đâu?
<details>
<summary>Lời giải</summary>
- Ở đâ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`.
</details>
### 🔍 `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.
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
- 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.
<details>
<summary>Lý do</summary>
- 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](https://codeforces.com/blog/entry/62393).
</details>
### 🔍 `Lỗi thường gặp 13`
- Hãy thử xóa một phần tử trong `multiset`
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
- 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ử.
<details>
<summary>Lý do</summary>
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](https://cplusplus.com/reference/set/multiset/erase/).
<details>
<summary>Cách khắc phục</summary>
```cpp
#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;
}
```
</details>
</details>
### 🔍 `Lỗi thường gặp 14`
- Hãy chạy thử đoạn code dưới đây:
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
- Hãy thử đoán xem output có phải là `5` hay không?
<details>
<summary>Giải thích</summary>
- 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ớ).
<details>
<summary>Cách khắc phục</summary>
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ử `[]`
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
</details>
</details>
### 🔍 `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:
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
- 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$?
<details>
<summary>Lý do</summary>
- 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](https://codeforces.com/blog/entry/64546). Tương tự với `upper_bound`.
<details>
<summary>Cách khắc phục</summary>
Dùng `set.lower_bound(value)` với độ phức tạp là $\mathcal{O}(\log n)$
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
</details>
</details>
### 🔍 `Lỗi thường gặp 16`
- Hãy xem đoạn code dưới đây:
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
- Hãy thử đoán độ phức tạp của đoạn code trên
<details>
<summary>Lời giải</summary>
- 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)$).
<details>
<summary>Cách khắc phục</summary>
Dùng `s += 'a'` để không phải truy cập toàn bộ chuỗi mỗi lần gán
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
</details>
</details>
### 🔍 `Lỗi thường gặp 17`
- Hãy xem đoạn code đơn giản dưới đây:
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
- Nhiệm vụ của bạn là tìm bug trong đoạn code trên
<details>
<summary>Bug</summary>
- 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.
<details>
<summary>Test ví dụ</summary>
```
2
1
1
2
1 3
```
</details>
<details>
<summary>Cách khắc phục</summary>
Đọ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.
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
</details>
</details>
### 🔍 `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:
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
- Hãy thử tìm bug trong đoạn code trên
<details>
<summary>Bug</summary>
- 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.
<details>
<summary>Test ví dụ</summary>
```
2
1
1
1
2
```
</details>
<details>
<summary>Cách khắc phục</summary>
Reset lại mảng `cnt` sau mỗi testcase
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
</details>
</details>
### 🔍 `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.
<details>
<summary>Ví dụ</summary>
```cpp
#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;
}
```
</details>
- Hãy cùng đi tìm bug nào
<details>
<summary>Bug</summary>
```cpp
#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;
}
```
</details>
### 🔍 `Lỗi thường gặp 20`
- Hãy xem đoạn code dưới đây:
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
- Khi chạy đoạn code trên in ra $2112827392$ thay vì $3 \cdot 10^{12}$?
<details>
<summary>Lý do</summary>
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](https://en.cppreference.com/w/cpp/algorithm/accumulate).
<details>
<summary>Cách khắc phục</summary>
Truyền giá trị khởi tạo mang kiểu `long long` `(0LL)`
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
<details>
<summary>Với double</summary>
```cpp
#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;
}
```
</details>
</details>
</details>
### 🔍 `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 hơn để tính căn bậc hai của một số nguyên:
<details>
<summary>Code</summary>
```cpp
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';
```
</details>
- *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$.
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
### 🔍 `Lỗi thường gặp 22`
- Hãy xem đoạn code dưới đây:
<details>
<summary>Code</summary>
```cpp
#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;
}
```
</details>
- Hãy thử đoán độ phức tạp của đoạn code trên
<details>
<summary>Lời giải</summary>
- Độ 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](https://stackoverflow.com/a/65394587).
- 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](https://codeforces.com/blog/entry/61587).
- 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](https://codeforces.com/blog/entry/70237).
- 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++?](https://stackoverflow.com/questions/16248221/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](https://codeforces.com/blog/entry/4898). 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](https://codeforces.com/blog/entry/60442). 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](https://codeforces.com/blog/entry/111217)
Sign in with Wallet
Connect another wallet