Kỹ Thuật Random Giúp Xử Đẹp Bài Toán Trong Lập Trình Thi Đấu.

Trong giới lập trình thi đấu có rất nhiều các kĩ thuật giải bài khác nhau, khi mà các kĩ thuật chính được các cao thủ hay sử dụng như Quy Hoạch Động, Quay Lui, .. thì bên cạnh đó cũng có một vài kĩ thuật được gọi là tà môn. Hôm nay mình sẽ giới thiệu đến các bạn kĩ thuật mang hơi hướng tà môn mà mình đã gặp, đó là sử dụng Random. Kỹ thuật giúp bạn “xử đẹp” bài toán trong lập trình thi đấu.

Kỹ thuật thì cũng không đúng lắm cái này giống trick hơn. Trick này có tên: AC_WITH_RANDOM. Tên này là mình tự đặt nhé chứ cũng không biết gọi nó là gì. AC_WITH_RANDOM có thể hiểu đơn giản là sử dụng thuật toán kết hợp với các hàm random (rand(), random_shuffle, shuffle,….) để xử lí bài toán trong lập trình thi đấu.

Table of Contents

1. Điểm mạnh và điểm yếu

Trick này có điểm mạnh gì? Giả sử 1 bài toán có 3 cách giải, 1 cách giải ngây thơ (Wrong Answer/ Time Limit Exceed ☹ ) , 1 cách giải ngây thơ nhưng có cải tiến (Wrong Answer / Time Limit Exceed ☹ ) và cách giải chuẩn (Accepted). Bình thường nếu các bạn muốn làm đúng được bài đó ăn 100% điểm (Accepted) thì bạn phải ra được cách giải chuẩn. Tuy nhiên khi sử dụng trick này, các bạn có thể ăn được toàn vẹn bài mà chỉ với cách giải ngây thơ có cải tiến hay thậm chí là cách giải ngây thơ nhất. Nghe có vẻ hấp dẫn đúng không? Không cần vò đầu bứt tai nghĩ cách cải tiến mà vẫn ăn được bài toán.

Nhưng khoan, sao trick này hay thế mà lại không phổ biến rộng rãi nhỉ? Sao không được đứng chung mâm với các kĩ thuật nổi tiếng khác như Quy Hoạch Động, Backtracking,… Lí do rất đơn giản, đó là do điểm yếu của nó.

Chính từ cái tên của trick này cũng đã chứa điểm yếu của nó rồi, đó chính là random, random là như nào? Là xác suất, lúc thế này, lúc thế khác, chúng ta không kiểm soát được chính xác. Vì thế nên, việc bạn có “ăn” được bài toán đó (accepted) hay không còn phụ thuộc vào may rủi của bạn nữa. Đương nhiên bạn có thể code sao cho tỉ lệ được accepted lớn nhất có thể, tuy nhiên rất khó để đạt được 100%. Và cũng không phải bài nào cũng có thể áp dụng được trick này.

2. Cách nhận diện

Cách nhận diện bài toán mà có thể sử dụng trick này như thế nào ? Theo kinh nghiệm của mình thấy thì những dạng bài về việc phân chia mảng, chọn 1 tập con từ 1 tập cho trước thỏa mãn 1 điều kiện cho trước,…

3. Ví dụ

Nói lan man thế đủ rồi, có lẽ vào ví dụ chi tiết các bạn sẽ dễ hình dung hơn. Ví dụ mà mình lấy là 1 bài tập ví dụ trên trang SPOJ PTIT.

Có thể giản lược đề bài như sau: Cho 1 mảng a có n số (1 <= n <= 20), 1 <= ai <= 100. Cần chia n số thành thành 3 nhóm b1,b2,b3 sao cho nhóm có tổng lớn nhất là nhỏ nhất. Giả sử b1 <= b2 <= b3 thì các bạn phải chia sao cho b3 có tổng nhỏ nhất có thể.

Phân tích 1 chút, thực chất bài này chính là các bạn phải n số chia thành 3 nhóm sao cho tổng của các nhóm đều nhau nhất có thể.

Ý tưởng ngây thơ để giải quyết bài toán này có lẽ là sử dụng kĩ thuật tham lam, các bạn duyệt mảng, lần lượt thêm phần tử vào 1 trong 3 nhóm sao cho tổng 3 nhóm đều nhau nhất có thể, nhưng duyệt như thế nào để ra được kết quả tối ưu nhất đây?

Đây là lúc mà trick AC_WITH_RANDOM có thể được áp dụng. Nếu bạn không biết duyệt theo thứ tự nào, vậy thì hãy duyệt theo thứ tự random đi. Điểm mấu chốt của trick này ngoài thuật toán ngây thơ ban đầu đó là random và lặp, random rồi lại lặp, lặp chính là cách để các bạn tăng xác suất tiếp cận kết quả đúng nhất, lặp càng nhiều càng tốt. 😀 Nhưng lặp nhiều quá dính time limit exceed thì sao? Cách để lặp được nhiều nhất có thể nhưng vẫn đảm bảo dưới giới hạn thời gian cho phép đó chính là sử dụng đồng hồ trong C++.

Trên đây là 1 đoạn code bạn sẽ rất hay phải sử dụng nếu sử dụng trick mà mình đang giới thiệu, sử dụng đồng hồ của C++ để giới hạn thời gian thực thi code của bạn sẽ đảm bảo việc bạn không bao giờ bị dính trường hợp time limit cả. clock() và CLOCKS_PER_SEC bạn phải khai báo #include <time.h> ở đầu file.

Đây là solution của mình sử dụng trick random để giải bài toán trên: https://ideone.com/r7edRV

Giải thuật ở đây rất đơn giản, bạn sẽ thực hiện lặp 1 cơ số lần (sử dụng đoạn snippet code ở trên để giới hạn thời gian thực hiện lặp). Ta sẽ có 1 biến kết quả khởi tạo ban đầu là 1 số cực lớn (INT_MAX) với mỗi lần lặp ta xáo trộn mảng ban đầu lên rồi bắt đầu duyệt tham lam từ đầu đến cuối, ở phần tử thứ i ta xem trong 3 nhóm nhóm nào đang có tổng bé nhất thì cộng phần tử thứ i vào. Sau khi duyệt xong thì ta sẽ update biến kết quả.
Để có thể tăng tốc để lặp được nhiều lần hơn thì ta có thể có thêm nhận xét rằng nếu duyệt đến vị trí i mà nhóm có tổng nhỏ nhất trong 3 nhóm đã lớn hơn kết quả tính đến thời điểm hiện tại thì chẳng có lí do gì để duyệt tiếp cả nên ta có thể break sớm được vòng duyệt này.

Chỉ đơn giản là duyệt tham lam và lặp 1 cơ số lần nào đó và bạn đã có thể xử đẹp được bài toán này rồi.

4. Lưu ý

Tuy nhiên có 1 số lưu ý đó là:

Tỉ lệ đúng chỉ có mức độ, kích thước dữ liệu càng nhỏ tỉ lệ đúng càng cao (như trong bài trên chỉ có 20 phần tử là max, khá nhỏ), dữ liệu càng lớn, thời gian giới hạn càng nhỏ thì tỉ lệ đúng sẽ giảm xuống.
Ngoài việc random và lặp, giải thuật ban đầu của bạn phải đảm được việc là “chắc chắn đúng trong 1 trường hợp cụ thể nào đó”. Như trong trường hợp bài toán mình nêu ví dụ ở trên thì chắc chắn sẽ có 1 hoán vị nào đó của mảng trên mà duyệt trâu tham lam sẽ ra được kết quả tốt nhất mà bài toán yêu cầu.
Vì để lặp càng nhiều càng tốt nên thời gian chạy của code khá lâu (thường khi áp dụng thời gian chạy của giải thuật sẽ ~ time limit).

Nếu bạn gặp 1 bài toán mà thực sự bí không tìm ra được phương pháp giải chuẩn nhưng có thể tìm ra được giải thuật “tương đối chuẩn” thì trick trên cũng là 1 phương án tốt mà bạn có thể suy nghĩ tới. Dù vận may chiếm phần lớn nhưng không thể phủ nhận được việc cách thức tiếp cận bài toán tốt cũng có thể khiến trick trên trở thành 1 công cụ đăc lực cho bạn. Nhưng dẫu sao thì cách dựa vào đen đỏ như thế này cũng không được khuyến khích nhiều, nhất là trong các cuộc thi nơi mà ngoài tốc độ thì cần yêu cầu sự chính xác nữa. Hầu hết các cuộc thi lập trình thi đấu hiện tại đều có cơ chế phạt điểm thời gian nếu bạn submit sai, đây là 1 trong những điểm yếu chí mạng khác của trick random, khi mà bạn không thực sự kiểm soát được kết quả của đoạn code mình viết ra, và cũng không biết được sau bao nhiêu lần submit bạn sẽ có thể có được “ông thần may mắn” mỉm cười với mình.

5. Một số bài tập áp dụng

Một số bài toán khác có thể áp dụng được trick này các bạn có thể tham khảo. Các bạn có thể tìm trong các bài viết này. Các bạn để ý là có những bài toán rất khó như các bài D, E, F hay thậm chí G của Div 1 cũng thi thoảng phải sử dụng trick này. Cá biệt còn có một số trường hợp nếu không sử dụng trick random này thì chắc chắn không ra được. Mình nhớ bài đó cả Tourist lẫn Petr cũng xài random để AC sau 1 cơ số lần submit.

Problem: https://codeforces.com/contest/717/problem/H

Sol: https://codeforces.com/contest/364/submission/63377545

Problem: https://codeforces.com/problemset/problem/329/C

Sol: https://codeforces.com/contest/329/submission/63393727

Problem: https://codeforces.com/problemset/problem/364/D

Sol: https://codeforces.com/contest/364/submission/63377545

Problem: https://codeforces.com/problemset/problem/23/C

Sol: https://codeforces.com/contest/23/submission/63534413

Problem: https://codeforces.com/contest/375/problem/A

Sol: https://codeforces.com/contest/375/submission/63428321

https://vjudge.net/contest/323610 (pass: abcd)

https://vjudge.net/contest/323731 (pass: abcd)

Tạm kết

Trên đây mình đã giới thiệu cho các bạn về 1 trick theo mình thấy là khá hay ho trong lập trình thi đấu, tuy tà môn và dựa vào may rủi cao nhưng cũng không phải không có hiệu quả. Biết đâu một ngày nào đó bạn lcần đến nó thì sao. Mong nhận được phản hồi và đóng góp từ các bạn. Thân!