Những lỗi sai thường gặp trong lập trình thi đấu và cách khắc phục

---

✍️ Author: 2School Guideline

📋 Content:

• Những lỗi sai thường gặp trong lập trình thi đấu và cách khắc phục
• Giới thiệu chung
• Lỗi 1: Quên đọc/ghi file
• Lỗi 2: Đọc/ghi sai tên file, dịch lỗi
• Lỗi 3: Tràn mảng
• Lỗi 4: Tràn số
  • Ví dụ 1:
  • Ví dụ 2:
  • Ví dụ 3:
• Lỗi 5: Sử dụng endl của C++
• Lỗi 6: Truyền CTDL vào hàm
• Lỗi 7: Reset mảng bằng memset
• Lỗi 8: Một vài hàm có sẵn trong C++
  • Hàm pow()
  • Hàm sqrt()
• Lỗi 9: Sử dụng sai phiên bản của C++
  • Trường hợp 1: Sử dụng phiên bản thấp hơn
  • Trường hợp 2: Sử dụng phiên bản cao hơn
• Tổng kết
• Tài liệu tham khảo

---

Giới thiệu chung

Gần tới kì thi HSGTP 9 rồi, cũng như chỉ còn vài tháng nữa kì thi tuyển sinh sẽ đến gần. Vậy nên hôm nay chúng ta sẽ cùng điểm qua một vài lỗi cơ bản trong lập trình thi đấu mà mọi người thường hay mắc phải nhé.

Lỗi 1: Quên đọc/ghi file

Lỗi này nghe có vẻ buồn cười cơ mà không ít các trường hợp xấu số và hấp tấp dẫn đến cài rất nhiều xong nguyên bài được 0đ.

Lỗi 2: Đọc/ghi sai tên file, dịch lỗi

Có thể có nhiều bạn sẽ nghĩ nó vô cùng ngớ ngẩn, tuy nhiên đã không ít các trường hợp xảy ra và kết quả vô cùng nuối tiếc. Vì thuật sai vẫn có trường hợp đúng 1 vài test còn nếu đọc ghi file sai, bạn sẽ mất hết điểm bài đó. Thế nên đừng coi thường điều này.

Nguyên nhân có thể đến từ việc code quá nhanh khiến cho bạn việc sai chính tả mà không để ý.

Mẫu nhập xuất file chính xác:

freopen("text.inp", "r", stdin);
freopen("text.out", "w", stdout);
// lưu ý cần đổi [text] theo tên của bài trong đề

$$
Vậy nên cách khắc phục là hãy compile lại code có đọc file sau khi làm bài xong. Đặc biệt là với những bạn thường xuyên chạy test bằng terminal. Sau đó bạn không nên thay đổi bất cứ điều gì trong file. Cuối cùng, hãy dành 1 vài phút trước khi hết giờ làm bài để chạy lại tất cả các file lần cuối cùng để chắc chắn rằng mọi thứ đều ổn.

*Hình ảnh những nạn nhân xấu số

• Lưu ý: bạn cần ghi đúng tên bài cả 3 file .cpp, .inp, .out khi chạy thử vì nếu ghi sai bạn có thể chạy thử bình thường và nhận kết quả đúng nhưng khi chấm bài bạn sẽ không có điểm nào.

Lỗi 3: Tràn mảng

Hãy cùng xem đoạn code bên dưới

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

const int N = 1e5;

int a[N];

int main() {
    int n; cin >> n; // n <= 10^5
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cout << a[i] << " ";
    
    return 0;
}

Trong đoạn code trên khi

$n={10}^5$ thì hiện tượng tràn mảng sẽ xảy ra, lí do bởi vì ta khai báo

$N={10}^5$, mà vị trí trong C++ được bắt đầu là

$0$, vậy nên kết thúc là

$99999$. Tuy nhiên đoạn code trên đã truy cập vào vị trí

$100000$.

Để khắc phục điều này, chúng ta hãy để ý kĩ giới hạn của đề bài và khai báo dư ra một vài phần tử để không bị trường hợp tràn mảng.

const int N = 1e5 + 5;

Ngoài ra, chúng ta không nên truy cập mảng từ

$0$ vì đôi khi ta sẽ vô tình truy cập vào

$a[i-1]$ mà không biết rằng

$i=0$ sẽ dẫn đến truy cập vào

$a[-1]$ (sẽ gây ra lỗi), tốt nhất nên truy cập từ vị trí

$1$ để tránh các trường hợp đáng tiếc xảy ra.

Lỗi 4: Tràn số

Ví dụ 1:

Hãy cùng xem đoạn code bên dưới

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

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

Kết quả mà bạn mong muốn là

${10}^{18}$, trong khi đó chương trình lại in ra 1 kết quả khá kì quặc trong khi bạn đã đặt product là long long?

Giải thích

Thực tế chương trình sẽ lấy a*b trước rồi sau đó mới gán cho biến product. Vậy nên khi một số int nhân với int sẽ gây ra hiện tượng tràn số.

Để khắc phục được điều này, bạn chỉ cần ép kiểu cho a hoặc b về long long là được.

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

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

Ví dụ 2:

Hãy cùng xem đoạn code bên dưới

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

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

Chúng ta nghĩ nó sẽ trả ra

$-1$, tuy nhiên nó lại trả ra một số kì quặc?

Giải thích

Lí do là vì v.size() đang ở kiểu dữ liệu dạng unsigned, hay có nghĩa là số không âm, vậy nên khi ta -1 thì nó sẽ bị tràn ra khỏi giới hạn của kiểu dữ liệu.

Cách khắc phục tương tự như ví dụ 1, ta sẽ ép kiểu v.size() qua kiểu dữ liệu int

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

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

Lỗi này dễ mắc phải khi ta duyệt for qua mảng mà không cần phần tử cuối thì ta -1 ở vị trí cuối cùng lại vô tình dẫn đến các tình huống không mong muốn.

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

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

Ví dụ 3:

Hãy cùng xem đoạn code bên dưới

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

int main() {
    int a, b; cin >> a >> b;
    int mod = (int)1e9 + 7;
    cout << (a - b) % mod;
    return 0;
}

Ở đoạn code trên đang có một lỗi chết người mà bạn có nguy cơ mắc phải? Vậy bạn có đoán được đó là lỗi nào không?

Giải thích

Đó chính là lỗi tràn số, nguyên nhân là khi

$a<b$ thì khi

$a-b$ sẽ ra một số âm. Trong C++, thì chúng ta không thể mod được cho một số âm. Vây nên khi mod âm trong C++ thì kết quả sẽ không thể đoán trước được.

Cách khắc phục là khi ta modulo cho một biểu thức có phép trừ thì hãy cộng mod vào cho tới khi dương rồi sau đó hãy modulo.

$$(a-b)\mathrm{\%}mod=(a-b+mod)\mathrm{\%}mod$$

Ngoài ra, khi sử dụng phép modulo chúng ta cũng cần phải cẩn thận modulo trước khi nhân và cộng để tránh các trường hợp

$a+b$ hoặc

$a\ast b$ vượt quá kiểu dữ liệu.

Lỗi 5: Sử dụng endl của C++

Trong lập trình thi đấu, sử dụng endl thực sự khiến chương trình của chúng ta chạy chậm đi.

Lí do là vì cout << endl tương đương với cout << "\n" << flush. Flush được dùng để đưa một output đang chứa trong bộ đệm ra ngay lập tức để đồng bộ với chương trình đang chạy. Tuy nhiên trong lập trình thi đấu thì việc chạy đồng bộ không cần thiết vì chúng ta sử dụng đọc xuất file. Việc sử dụng endl chỉ hữu dụng khi làm những bài có tag interactive chẳng hạn trên nền tảng codeforces.

Nếu bạn đã quen tay với việc sử dụng endl rồi, hãy sử dụng #define endl "\n" ở trên đầu đoạn code.

Lỗi 6: Truyền CTDL vào hàm

Hãy cùng xem đoạn code bên dưới

// Pass by value
int ssize(vector <int> a){
    return (int)a.size();
}

int n = 1e5;
vector <int> a(n);
for (int i = 1; i <= n; i++){
    cout << ssize(a) << endl;
}

Bạn có đoán được đoạn code này chạy trong bao lâu không?

Giải thích

Chắc hẳn có rất nhiều bạn đã nghĩ rằng đoạn code này chạy trong

$O(n)$. Thế nhưng thực tế đoạn code trên kia chạy

$O(n^2)$!!! Vì sao lại thế???

Đó là bởi vì khi ta truyền a vào làm tham số của hàm ssize(). Toàn bộ mảng a sẽ được copy lại, và sau đó a mới sẽ gọi size() mới và trả về kết quả. Vì thế hàm ssize() tốn độ phức tạp

$O(n)$.

Để hàm ssize() chạy trong

$O(1)$, ta sẽ sửa tham số truyền vào là một tham chiếu tới trực tiếp vector được truyền vào.

// Pass by reference
int ssize(vector <int> &a){
    return (int)a.size();
}

Lỗi 7: Reset mảng bằng memset

Thông thường trong lập trình thi đấu, nhiều cp-ers rất hay có thói quen sử dụng memset để set giá trị ban đầu cho mảng, tuy nhiên lại không thực sự hiểu rõ về chúng. Hãy xem đoạn code bên dưới:

#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;
}

Ta mong muốn chương trình chạy ra 1 1 1 1. Tuy nhiên kết quả lại cho ra một dãy 16843009 16843009 16843009 16843009 16843009. Tại sao lại như vậy?

Giải thích

Lí do là vì hàm memset không hoạt động như chúng ta nghĩ là gán tất cả các phần tử trong mảng bằng một giá trị chúng ta muốn. Nó hoạt động bằng cách lấy

$8$ bit đầu từ phải qua trái của số và nhân nó lên

$4$ lần.

Lấy ví dụ trong đoạn code trên. Memset lấy số

$1$ ở dạng nhị phân là

$00000001$ và nhân

$4$ lần lên thành dãy nhị phân

$00000001000000010000000100000001$ hay ở số thập phân là

$16843009$ như kết quả trên. (Bạn có thể tự kiểm chứng thêm một vài test nữa).

Cách khắc phục là thay vì xài memset, chúng ta hãy for loop qua mảng một cách bình thường hoặc sử dụng fill để thay thế.

Ta chỉ có thể sử dụng hai giá trị là

$0$ và

$-1$ cho khi gán giá trị bằng hàm memset.

Lỗi 8: Một vài hàm có sẵn trong C++

Hàm pow()

Ta hãy cùng xét một vài ví dụ thực tế trong bài 1 đề TS 10 môn Tin TPHCM năm 2023 ở đây: LUYTHUA.

Bài này tuy đơn giản chỉ là "đề kêu gì làm nấy". Tuy nhiên đã không ít bạn mất điểm bài này vì sử dụng pow().

Thực tế hàm pow() là một hàm trả về số thực, vì thế đôi khi nó sẽ có một vài sai sót không mong muốn. Ví dụ như

$5^2=25.00$, nhưng đôi khi hàm pow(5, 2) sẽ trả về

$24.9999999999999$ và khi chuyển sang int, nó sẽ trả về

$24$.

Cách khắc phục cho điều này là chúng ta có thể sử dụng for trâu hoặc binary exponentiation để thay thế cho hàm pow().

Hàm sqrt()

Tương tự như hàm pow(), sqrt() đôi khi sẽ trả ra một vài kết quả không mong muốn.

Vậy nên chúng ta có thể khắc phục nó như sau

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';

Điều này cũng có thể áp dụng với cbrt().

Lỗi 9: Sử dụng sai phiên bản của C++

Đối với những ai sử dụng C++ trong các kì thi, thông thường ở thời điểm hiện tại, trình chấm themis sẽ chấm code ở phiên bản C++14. Tuy nhiên, có nhiều người trong phòng thi xài sai phiên bản (thấp hơn hoặc cao hơn) khiến việc code và chấm trở nên vô cùng nguy hiểm (có thể mất bài)

Trường hợp 1: Sử dụng phiên bản thấp hơn

• Thông thường ở các máy tính trong phòng thi sẽ mặc định ở C++98 (năm 1998), phiên bản này đã vô cùng cũ, vậy nên sẽ có nhiều hàm, cú pháp sẽ không thể sử dụng được nếu như làm trên phiên bản này. Đối với một người học ở tài liệu sử dụng C++ phiên bản cao hơn, việc cài đặt bằng phiên bản cũ rất khó khăn. Vì thế để chuyển sang phiên bản C++14, chúng ta có thể làm như sau:
  
  
  Sau khi ấn vào, một cái bảng sẽ hiện lên, bạn check vào ô C++14 là được
  
  

Trường hợp 2: Sử dụng phiên bản cao hơn

• Ở C++17 có rất nhiều các tiện ích

Tổng kết

Bên trên là tất cả những lỗi mà bọn mình nghĩ là sẽ gặp nhiều trong những cuộc thi lập trình thi đấu. Ngoài ra, còn rất nhiều lỗi mà bọn mình chưa liệt kê ở đây, nếu các bạn muốn đọc thêm cũng có thể ấn vào các đường link bên dưới tài liệu tham khảo để đọc. Tuy nhiên, với các chiến sĩ 2k9 sắp tới thì nhiêu đây là đủ để ra trận rồi.

Vậy nên 2SG xin chúc các bạn 2k9 sắp thi tuyển sinh có thật nhiều may mắn và đậu vào trường các bạn muốn nhé. 💗

Tài liệu tham khảo

[1] https://codeforces.com/blog/entry/111217
[2] https://wiki.vnoi.info/algo/skill/Kinh-nghiem-thi-VOI