# Random và ứng dụng trong lập trình thi đấu
> Tác giả: Lý Đình Minh Mẫn - Trường Đại Học Khoa Học Tự Nhiên, TPHCM

## Lời nói đầu:

Các thuật toán ngẫu nhiên đã luôn là một vấn đề được nghiên cứu trong suốt thời kỳ phát triển của máy tính và các ngôn ngữ lập trình.
Trong lập trình thi đấu, việc tạo ra các số ngẫu nhiên được áp dụng rộng rãi để tạo nên các testcases để kiểm tra tính đúng đắn của một bài làm nhất định.
Trong bài viết này, mình sẽ đề cập đến các cách tạo số ngẫu nhiên trong ngôn ngữ `C++` (ngôn ngữ phổ biến trong lập trình thi đấu).

## Hàm `rand` trong `C++`:

Đây thực chất là một hàm được kế thừa từ `C`, sẽ trả về một số nguyên $\in [0$, RAND_MAX$]$. Trước khi gọi hàm, ta phải cung cấp `seed` bằng cách sử dụng hàm `srand`.
Tuy nhiên, việc sử dụng hàm này có rủi ro cao vì không có sự đảm bảo trong tính ngẫu nhiên đối với các giá trị được trả về.

## Cách sinh số ngẫu nhiên được khuyến nghị:

### Cách 1: sử dụng các lớp có sẵn:

Kể từ phiên bản `C++11`, tác giả đã khuyến khích chúng ta sử dụng lớp `uniform_int_distribution` để tạo ra số ngẫu nhiên $\in [a, b]$ với xác suất $P(i | a, b) = \frac{1}{b - a + 1}$. Cũng giống như `rand`, ta phải cung cấp `seed` cho chương trình bằng hàm `srand` hoặc lớp `mt19937`. Dưới đây là một đoạn code mẫu để sinh một số nguyên ngẫu nhiên $\in [1, 10]$:

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

int main() {
    // srand(time(NULL));
    mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> myRandom(1, 10);

    cout << myRandom(rd) << '\n';
}

### Cách 2: Kết hợp lớp có sẵn với các thao tác trên bit

Ngoài cách trên, chúng ta cũng có thể sinh số ngẫu nhiên bằng các thao tác trên bit, mang lại xác suất khác nhau cao hơn:

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

#define ll long long

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

ll Rand(int L, int R) {
	assert(L <= R);
	ll res = 0;
	for (int i = 0; i < 4; i++) {
		res = (res << 15) ^ (rd() & ((1 << 15) - 1));
	}

	return L + res % (R - L + 1);
}

int main() {
	cout << Rand(1, 100) << '\n';
}

Ý tưởng của cách sinh này là: chúng ta sẽ tạo ra một số $60-\text{bit}$ bằng cách chọn ngẫu nhiên $15-\text{bit}$ cho mỗi lượt. Khi đến lượt kế tiếp, ta shift các bit đã tạo được sang trái $15-\text{bit}$ và $\oplus$ chúng với $15-\text{bit}$ ngẫu nhiên kế tiếp.

Cuối cùng, để chắc chắn số sinh ra $\in [L, R]$, ta phải lấy modulo với $(R - L + 1)$ và đổi chặn dưới thành $L$ thay vì $0$.

## Ứng dụng trong lập trình thi đấu:

Trong quá trình làm bài, việc sử dụng các cách sinh số ngẫu nhiên sẽ hỗ trợ các bạn trong việc tìm ra bug trong code của mình để tiến hành sửa chữa. Ngoài ra, trong một vài kỳ thi như HSGQG (VOI), hay các kỳ thi online/offline khác, việc sinh test ngẫu nhiên cũng là một cách để chúng ta kiểm tra tính đúng đắn của thuật toán của mình với nhiều dữ liệu đầu vào khác nhau. Việc làm này thường đòi hỏi chúng ta kết hợp thêm với thuật toán trâu để kiểm tra dữ liệu đầu ra tương ứng.

Trong mục này, mình sẽ trình bày một template có thể được dùng để sinh test cũng như kiểm tra tính đúng đắn của chương trình.

Để thực hiện được việc này, bạn cần phải có code thuật chuẩn (thuật toán có độ phức tạp thấp, nhưng có thể có sai sót), và code thuật trâu (thuật toán có độ phức tạp cao hơn, nhưng đảm bảo tính đúng đắn). Ngoài ra, với một số bài có thể tồn tại nhiều kết quả đúng đối với các đầu vào tương ứng, các bạn cần phải kiểm tra file output bằng một chương trình khác (tạm gọi là `checker`).

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

#define ll long long

// Tên bài làm
const string NAME = "TEST";
// Số lượng test để kiểm tra
const int NTEST = 100;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

ll Rand(int L, int R) {
	assert(L <= R);
	ll res = 0;
	for (int i = 0; i < 4; i++) {
		res = (res << 15) ^ (rd() & ((1 << 15) - 1));
	}

	return L + res % (R - L + 1);
}

int main()
{
    for (int iTest = 1; iTest <= NTEST; iTest++) {
        ofstream inp((NAME + ".inp").c_str());
        // Code phần sinh test ở đây
        // Lưu ý: sử dụng stream "inp" thay vì cin/cout để ghi ra file
        inp.close();
        
        // Nếu dùng Linux thì "./" + Tên chương trình
        system((NAME + ".exe").c_str());
        system((NAME + "_trau.exe").c_str());
        
        // Nếu dùng linux thì thay fc bằng diff
        // Lệnh fc, diff dùng để kiểm tra sự giống nhau của 2 file (bỏ qua các ký tự xuống dòng)
        // Trả về 0 nếu nội dung 2 file giống nhau
        if (system(("fc " + NAME + ".out " + NAME + ".ans").c_str()) != 0) {
            cout << "Test " << iTest << ": WRONG!\n";
            return 0;
        }
        cout << "Test " << iTest << ": CORRECT!\n";
        
        // Đối với các bài có nhiều kết quả
        // cần kết hợp thêm checker để kiểm tra output:
        // system((NAME + "_checker.exe").c_str());
        // ifstream checker_inp("checker.out");
        // bool result;
        // checker_inp >> result;
        // checker_inp.close();
        
        // Giả sử checker in ra 1 nếu output hợp lệ,
        //                      0 nếu output không hợp lệ
        // if (!result) {
        //     cout << "Test " << iTest << ": WRONG!\n";
        // }
        // cout << "Test " << iTest << ": CORRECT!\n";
    }

    return 0;
}

> Note: code trên được tham khảo từ trang Wiki của VNOI ([link](https://vnoi.info/wiki/algo/skill/viet-trinh-cham.md))

## Lời kết:

Qua bài viết này, mình hy vọng các bạn độc giả có thể biết thêm một vài kiến thức về việc sinh số ngẫu nhiên trong `C++`, và các bạn học sinh đang luyện tập cho các kỳ thi tin học có thể tạo thói quen kiểm tra chương trình của mình trước khi nộp bài để tránh khỏi những sai sót đáng tiếc.

Chúc các bạn đạt được nhiều thành công trên con đường Tin học nói chung và trong các kỳ thi lập trình thi đấu nói riêng trong năm mới để góp phần phát triển nền Tin học nước nhà!