Một vài vấn đề trong lập trình thi đấu cho người bắt đầu


Một vài vấn đề trong lập trình thi đấu cho người mới bắt đầu

Bài viết này có mục đích truyền đạt những thứ cơ bản cho những ai muốn bắt đầu trong bộ môn lập trình thi đấu, hoặc chỉ đơn thuần là học thuật toán để nâng cao bản thân.
Trên mạng đã có rất nhiều trang viết về điều này rồi, trong trường hợp bạn chưa có chút kiến thức cơ bản nào, bài viết này là để dành cho bạn.

Ngôn ngữ lập trình

Các ngôn ngữ khả dụng (tùy vào sự lựa chọn của bạn):
  • C/C++, lưu ý C++ có nhiều phiên bản, nếu bạn chưa biết được công dụng của từng phiên bản thì hãy bắt đầu với C++ 11. C có tốc độ nhanh nhất, C++ thì chậm hơn chút
  • Java, chậm hơn C++ 3 lần (với C++ 20 thì là 6 lần)
  • Python (gần đây), tỏ ra khá hữu dụng khi xử lí số nguyên lớn.

Online Judges

Nếu bạn không hiểu định nghĩa này, hãy hiểu nôm na nó là nơi để bạn tập luyện (dù không hoàn toàn là thế). Có thể kể đến một vài OJ như sau:
  • Codeforces: tất nhiên rồi, nền tảng lớn nhất thế giới
  • VNOJ: nền tảng lớn và đầy đủ nhất VN hiện nay, ngoài VNOJ ra còn LQDOJ, NTUcoder,...
  • Kattis: nơi lưu trữ đề bài của các cuộc thi lớn cấp độ khu vực trở lên, thích hợp hơn với người đã có kinh nghiệm
  • Atcoder: như Codeforces, cũng là một nền tảng lớn, tuy nhiên khác với Codeforces nặng về tư duy tham lam, Atcoder nặng về toán học thuần túy.
  • Hackerrank: giao diện bắt mắt, dễ dùng, tuy nhiên không khuyến khích làm contest trên Hackerrank
  • Hackerearth, Codechef, Leetcode: những lựa chọn khác.

Online programming contests:

Giám khảo cho bạn đề bài, bạn giải nó và submit lên, máy chấm sẽ chạy bài của bạn và xác nhận xem bạn có hoàn thành yêu cầu hay không. Một vài lỗi chính mà mọi người thường gặp:

WA (Wrong answer)

  • In thừa output, đọc thiếu input. BTC giao thế nào thì đọc in như thế, tuyệt đối không thêm vài dòng như "Nhập số n:", "Đáp án là: ", vô ích.
  • Sai format đề bài đưa ra, ví dụ: bạn quên lấy 4 chữ số sau dấu phẩy, hoặc quên lấy modulo cho $10^9 + 7$
  • Trong bài có lỗi không đáng có, thừa hoặc thiếu một dấu + có thể cũng là vấn đề.
  • Chưa xử lí bộ nhớ cấp phát, khi khai báo mảng nhớ đưa toàn bộ mảng về 0 trước khi tính toán.
  • Hoặc đơn giản, trường hợp phổ biến nhất: bạn làm sai

RTE (Runtime error)

  • Chia cho 0.
  • Tràn số (đôi khi nó sẽ hiện là WA).
  • Tràn bộ nhớ (khi tác vụ lặp lại quá nhiều lần và không có điểm dừng, nên phân biệt được với MLE). 
  • Code sai chính tả (ví dụ: truy xuất std::set.begin() và std::set.rbegin() ).
Đây là một code tràn bộ nhớ dưới dạng RTE:

#include <bits/stdc++.h>
using namespace std;
int factorial(int n)
{
	return n * factorial(n - 1);
}
int main()
{
	int a = factorial(10);
	cout << a << '\n';
}
Hàm đệ quy này gọi không có điểm dừng, để khắc phục thì ta thêm điểm dừng tại $n = 0$ cho nó:

#include <bits/stdc++.h>
using namespace std;
int factorial(int n)
{
	if (n == 0) return 1;
	return n * factorial(n - 1);
}
int main()
{
	int a = factorial(10);
	cout << a << '\n';
}
  • Truy cập bộ nhớ chưa được cấp phát, hoặc đơn giản là yêu cầu cấp phát bộ nhớ quá lớn ($10^8$).

CE (Compiler error)

  • Code của bạn sai chính tả, hoặc -
  • Code của bạn yêu cầu một hàm không tồn tại (có thể là bạn chưa viết nó, hoặc phiên bản bạn đang dùng không hỗ trợ nó).

TLE (Time Limit Exceed)

  • Đệ quy vô tội vạ không có điểm dừng (khi truy nhập bộ nhớ tĩnh, cần phân biệt với RTE).
  • Vòng lặp vô hạn
  • Code của bạn chưa được tối ưu, bạn ngồi phân vân không biết nó qua được không, và nó không qua thật.
  • Bạn chưa thật sự chuẩn bị phương án tốt nhất cho (những) test khó nhất.
  • Code sai chính tả (again, đây là lí do có thể dẫn tới tất cả các trường hợp).

MLE (Memory Limit Exceed)

  • Tràn bộ nhớ (khi cấp phát quá nhiều, cần phân biệt với tràn bộ nhớ của RTE).
  • Yêu cầu cấp phát mảng khi không thực sự cần thiết, dẫn đến những rủi ro không đáng có.

OLE (Output Limit Exceed)

  • Output quá dài, máy chấm từ chối đọc. Có thể là lỗi biên dịch quá nhiều, hoặc output vô hạn.

ILE (Idleness Limit Exceed)

  • Chủ yếu xảy ra khi làm bài tập dạng Interactor, khi bạn quên flush output và máy chấm không nhận được thông tin gì cả.

JE (Judgement Error)

  • Lỗi máy chấm, có thể nộp lại hoặc chờ BTC chấm lại (lỗi hiếm gặp).

Debug

Sau khi phát hiện bài giải của mình bị sai, giờ là lúc để ngồi debug. Cố gắng viết code của bản thân phân mảnh và dễ hiểu nhất có thể, tránh các code kiểu:

#include <bits/stdc++.h>
using namespace std;
#define all(cont) begin(cont), end(cont)
using ll = long long;
template<class T>void read(T &x){
  char ch;x=0;int f=1;while (isspace(ch=getchar()));
  if(ch=='-')ch=getchar(),f=-1;do x=x*10+(ch-'0');while(isdigit(ch=getchar()));x *= f;
}
template<class T,class ...A> void read(T &x,A&... args){read(x);read(args...);}
const int N=200005;vector<int> G[N];int len[N];vector<int> chain;
void DFS(int u,int fa=0){
  int son=0;len[u]=1;
  for(int v:G[u]){if (v==fa)continue;DFS(v, u);len[u]=max(len[u],len[v]+1);if(!son||len[v]>len[son])son=v;}
  for(int v:G[u])if(v!=fa&&v!=son)chain.push_back(len[v]);
}
int main() {
#ifdef LOCAL
  freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
  int n,k;read(n,k);for(int i=1;i<n;++i) {int u,v;read(u,v);G[u].push_back(v);G[v].push_back(u);}
  DFS(1);chain.push_back(len[1]);sort(all(chain), greater<int>());ll ans=-ll(n-n/2)*(n/2);int fre = n;
  for(int i=1;i<=k;++i) {if (i<=(int)chain.size())fre-=chain[i-1];int b= min(n/2,fre);ans=max(ans,ll(i-b)*(n-i-b));}
  printf("%lld\n", ans);return 0;
}
Làm ơn hãy viết code dễ hiểu nhất có thể, ít nhất là cho bạn, please.
Một vài phương pháp debug thường được sử dụng:
  • Nếu code của bạn không in ra đúng output, hoặc in ra quá nhiều, hoặc không chạy (RTE), hãy cố gắng chèn các dòng in vào giữa code để in ra những biến bạn cho là có thể bị lỗi. Comment lại một phần code cũng là 1 cách debug.
  • Code của bạn đã vượt qua test mẫu nhưng vẫn WA, có 2 khả năng: code của bạn sai hoàn toàn, nó chỉ là trùng output với code mẫu trong một vài test mà thôi, hoặc là code của bạn cơ bản là đúng, nhưng bạn chưa xét hết các trường hợp mấu chốt. Việc cần làm lúc này là: nháp, nháp và nháp. Nếu bạn nhận ra code của mình rơi vào TH1, đừng ngần ngại đi tìm lời giải mới. Còn nếu nó rơi vào TH2, viết 1 máy sinh test (hoặc sinh tay), sau đó viết 1 chương trình brute force có tỉ lệ in ra đáp án đúng là $100%$ (tuy nhiên chắc chắn TLE khi nộp), chạy 2 chương trình trong 10, 20, 50, hay 100 test khác nhau, cho đến khi nhận ra vấn đề.
  • Nếu bạn thật sự không thể làm gì, khi contest kết thúc, thử đọc hướng dẫn giải và code của người khác. Lưu ý chỉ đọc hướng dẫn của những bài toàn hơi khó 1 chút, vì nếu đọc lời giải của bài nào khó quá thì có đọc mãi bạn cũng không thể hiểu, còn đọc của bài dễ quá thì vô ích.
  • Giới hạn bộ nhớ thông thường là 256MB, đồng nghĩa với việc bạn không thể khai báo một mảng 2 chiều $10^4 \times 10^4$ hoặc những thứ có bộ nhớ tương đương, hãy đọc các tài liệu để hiểu thêm về vấn đề này.
  • Độ phức tạp của thuật toán: viết tắt là $O(f(n))$. Nói nôm na thì nó là số bước code của bạn cần phải chạy để đưa ra đáp án. Đặt $f(n)$ là hàm tính số bước cần chạy của chương trình, với trường hợp $f(n) = n^2$, ví dụ như:

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cout << i * j << '\n';
		}
	}
}
Thì độ phức tạp của thuật toán là $O(n^2)$, do chương trình chạy mất $n^2$ bước.
Tương tự, sau đây là một chương trình chạy trong $O(n)$:

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cout << i << '\n';
	}
}
Đôi khi độ phức tạp có thể bị nhầm lẫn, hãy cẩn thận với nó.
Ngoài ra chúng ta còn các độ phức tạp dưới dạng $log(n)$ và $\sqrt{n}$,...
  • Tràn số: một vấn đề thường thấy, hãy xác định kĩ mục đích trước khi gọi biến. Xem thêm tại bảng sau:

Data Type                              Range                      Macro for min value           Macro for max value
char                                -128 to +127                        CHAR_MIN                      CHAR_MAX
short char                          -128 to +127                       SCHAR_MIN                     SCHAR_MAX
unsigned char                         0  to 255                             0                        UCHAR_MAX
 
short int                         -32768 to +32767                      SHRT_MIN                      SHRT_MAX
unsigned short int                    0  to  65535                          0                        USHRT_MAX 
int                          -2147483648 to +2147483647                  INT_MIN                       INT_MAX
unsigned int                          0  to  4294967295                     0                         UINT_MAX
long int            -9223372036854775808 to +9223372036854775807        LONG_MIN                      LONG_MAX
unsigned long int                     0  to  18446744073709551615           0                        ULONG_MAX 
long long int       -9223372036854775808 to +9223372036854775807       LLONG_MIN                     LLONG_MAX
unsigned long long int                0  to  18446744073709551615           0                       ULLONG_MAX
 
float                        1.17549e-38 to  3.40282e+38                 FLT_MIN                       FLT_MAX
float(negative)             -1.17549e-38 to -3.40282e+38                -FLT_MIN                      -FLT_MAX
double                      2.22507e-308 to  1.79769e+308                DBL_MIN                       DBL_MAX
double(negative)           -2.22507e-308 to -1.79769e+308               -DBL_MIN                      -DBL_MAX
  • Ngoài ra còn một vài vấn đề như so sánh số thực, thừa output ở cuối file, v/v

Chúc bạn thành công.

Nhận xét

Đăng nhận xét