Cách hạn chế lỗi Wrong Answer khi nộp bài trên các web chấm code
Đây là kinh nghiệm mình chia sẻ với một bạn học viên, cảm thấy sẽ có giá trị với nhiều bạn nên mình copy tin nhắn làm luôn thành bài đăng này để nhiều bạn được tham khảo. Hi vọng giúp ích được cho các bạn. Chúc các bạn học tốt và gặt hái nhiều thành công 😇
Vấn đề: hệ thống không cho xem test sai
Khi em làm bài nộp lên hệ thống mà nó báo sai, em phải kiểm tra lại bài làm để tìm chỗ sai mà sửa. Vấn đề sẽ rất đơn giản nếu hệ thống cho em biết cụ thể trường hợp nào bị sai: em chỉ cần chạy tay theo logic code của mình với đúng dữ liệu đó là nhìn ra ngay chỗ sai. Có trường hợp sai cụ thể thì dò tìm và sửa lỗi quá đơn giản, em đồng ý không?
Tuy nhiên thực tế, với các hệ thống lớn cũng như khi đang trong buổi thi, thường nó không cho mình biết trường hợp sai là gì mà bắt mình phải tự tìm ra. Đó là một điều khó khăn cho chúng ta.
Giải pháp: dùng vét cạn làm "trọng tài"
Có một giải pháp để khi làm xong bài nào, em có thể tự kiểm tra xem bài của mình còn trường hợp nào sai không. Nếu còn, nó sẽ chỉ ra trường hợp sai cụ thể để em sửa, rồi kiểm tra lại cho đến khi không còn trường hợp nào sai nữa thì mới nộp lên hệ thống.
Cụ thể các bước như sau:
- Đứng trước bài tập, đầu tiên làm theo cách vét cạn, gom vào một hàm nhận tham số đầu vào và trả ra kết quả đề yêu cầu.
- Suy nghĩ cách tối ưu đảm bảo không bị quá thời gian, cũng gom vào một hàm cùng tham số đầu vào và kết quả đầu ra.
- Trong
main, viết một vòng lặp vô tận. Mỗi lần lặp, sinh dữ liệu ngẫu nhiên trong phạm vi giới hạn đề bài rồi truyền vào cả 2 hàm. - So sánh kết quả của 2 hàm. Giống nhau thì tiếp tục lặp. Khác nhau thì in ra chữ
FALSEkèm dữ liệu khiến bị sai, rồibreakthoát vòng lặp. - Chạy chương trình rồi "rung đùi ngồi chờ". Màn hình hiện
FALSEthì kiểm tra lại bài với đúng trường hợp đó. Chạy gần 5 phút mà không thấyFALSEthì có thể tạm yên tâm nộp bài.
Ví dụ: đếm số lượng ước của N
Bài toán: đếm số lượng ước số của một số $N$ với giới hạn $1 \le N \le 10^9$.
Vét cạn
Cho vòng lặp chạy từ 1 đến $N$, giá trị nào $N$ chia hết thì tăng biến đếm. Sau cùng biến đếm là kết quả.
Tối ưu
Mỗi ước $a$ đi kèm một ước $b = N / a$, và $a$ lớn nhất chỉ tới $\sqrt{N}$. Nên chỉ cần chạy $i$ từ 1 đến $\sqrt{N}$, mỗi $i$ chia hết $N$ thì cộng 2. Riêng khi $N$ là số chính phương thì $a = b = \sqrt{N}$, ước này chỉ được tính 1 lần.
Đây là mình nói ngắn gọn, bạn nào chưa hiểu về thuật toán này và muốn tìm hiểu sâu hơn thì xem cách số 3 tại bài viết này, mình có nói rõ nha.
Em thử xem đoạn code này và chạy thử trên máy để thấy rõ cách nó vận hành:
#include <bits/stdc++.h>
using namespace std;
// O(N)
int Solve1(int n){
int cnt = 0;
for(int i = 1; i <= n; ++i){
if(n % i == 0){
cnt++;
}
}
return cnt;
}
// O(sqrt(N))
int Solve2(int n){
int i;
int cnt = 0;
for(i = 1; i * i <= n; ++i){
if(n % i == 0){
cnt += 2;
}
}
if((i - 1) * (i - 1) == n){
cnt--;
}
return cnt;
}
int main(){
srand(time(0));
while(1){
int n = 1 + rand() % 1000000000;
cout << "n = " << n << " ";
int res1 = Solve1(n);
int res2 = Solve2(n);
if(res1 == res2){
cout << "TRUE\n";
}
else{
cout << "FALSE n = " << n << endl;
cout << "res1 = " << res1 << endl;
cout << "res2 = " << res2;
break;
}
}
return 0;
}Thử nghiệm: cố tình làm sai để xem nó bắt lỗi
Ở hàm Solve2, em thử xóa đi câu if ở cuối hàm, tức là if((i - 1) * (i - 1) == n), giả sử em quên xét trường hợp số chính phương. Chạy lại, đến một lúc dữ liệu random gặp đúng trường hợp đó là nó báo lỗi cho em thấy:
n = 400 FALSE n = 400
res1 = 15
res2 = 16
Nhìn vào là thấy ngay: $400 = 20 \times 20$ là số chính phương, ước 20 bị đếm 2 lần nên Solve2 ra 16 thay vì 15.
int n = 1 + rand() % 1000; (đúng như mẹo thu nhỏ khoảng random ở trên). Lý do: trong khoảng tới $10^9$, số chính phương rất hiếm (chỉ khoảng 31 nghìn số trong 1 tỷ số), mà hàm vét cạn $O(N)$ mỗi lần lại phải chạy tới hàng trăm triệu vòng, nên có thể phải chờ rất nhiều giờ mới gặp được trường hợp sai. Thu nhỏ còn 1 đến 1000 thì gần như chạy lên là thấy FALSE ngay.rand(): trên Windows (Dev-C++, Code::Blocks…), rand() chỉ trả về tối đa 32767, nên rand() % 1000000000 thực ra không bao giờ sinh được số lớn hơn 32767. Muốn random số lớn trên mọi máy thì dùng bộ sinh mt19937:
mt19937 rng(time(0));
int n = 1 + rng() % 1000000000;Đừng so sánh thủ công
Trong quá trình truyền đạt cách này với một số học viên, có bạn phản hồi là đã làm theo cách này trước khi mình nói rồi, nhưng thường là tạo thành 2 chương trình riêng, chủ động nhập dữ liệu cho từng chương trình, xem kết quả rồi so sánh bằng mắt, thử tầm chục lần.
Với mình thì đã làm theo cách này rồi thì nên làm tới luôn: cho dữ liệu tự động sinh ngẫu nhiên và vòng lặp chạy vô tận, kiểm tra qua hàng nghìn, hàng triệu bộ dữ liệu khác nhau. Như vậy độ chính xác cao hơn rất nhiều so với chỉ kiểm tra tầm chục lần. Mình cũng khỏe hơn nhiều: cứ treo máy đó, trong lúc đó qua suy nghĩ làm bài tiếp theo nếu đang thi nhiều bài, tầm 5–10 phút sau quay lại thấy vẫn ổn thì nộp bài là yên tâm.
P/s: Tin nhắn gốc của mình với bạn học viên cũng là được nhắn qua điện thoại, cũng như những tin nhắn mình nói thêm trong bài đăng này cũng đều được mình soạn trên ghi chú điện thoại hết, anh em sợ chưa hehe, hết lòng vì anh em nhé 😋
Nhận xét
Đăng nhận xét