Đề dẫn
Nhân kỷ niệm 36 năm (1989-2024) Việt Nam tham gia Olympic Tin học Quốc tế, hôm nay xin phép diễn đàn có một vài dòng về International Olympiad in Informatics, viết tắt là IOI.
Bài post này có cấu trúc như sau. Sau phần đề dẫn là phần giới thiệu sơ lược về IOI. Tiếp theo là một vài con số tương quan quốc tế & khu vực. Phần cuối tôi xin bàn luận đến việc “máy đi thi IOI” – nghĩa là máy đang tiệm cận đến việc giải các vấn đề thuật toán lập trình IOI trong khung thời gian mà ban tổ chức giải quy định.
Sơ lược về IOI
Olympic Tin học Quốc tế (IOI) là một cuộc thi lập trình thi đấu hàng năm và là một trong những kỳ thi Olympic Khoa học Quốc tế dành cho học sinh trung học. IOI đầu tiên được tổ chức vào năm 1989 tại Pravetz, Bulgaria.
Cuộc thi kéo dài hai ngày, trong đó thí sinh phải giải sáu bài toán thuật toán phức tạp bằng cách viết chương trình máy tính bằng ngôn ngữ C++. Tất cả tài liệu về bài thi đều được công bố trên trang web của cuộc thi mỗi năm ngay sau khi kỳ thi kết thúc.
Cấu trúc của kỳ thi
Vào mỗi ngày thi trong hai ngày thi đấu, thí sinh thường được giao ba bài toán và phải giải trong vòng năm giờ. Mỗi thí sinh làm bài một cách độc lập, không được nhận bất kỳ sự trợ giúp nào từ bên ngoài, cụ thể là không được liên lạc với các thí sinh khác, không được sử dụng sách, truy cập web, v.v. Thí sinh thường được phép mang theo bàn phím và chuột có dây.
Thông thường, để giải quyết một bài toán, thí sinh phải viết một chương trình máy tính (bằng ngôn ngữ C++) và nộp bài trước khi hết thời gian thi 5 giờ đồng hồ. Chương trình sẽ được chấm điểm dựa trên bộ dữ liệu kiểm tra bí mật. Kể từ IOI 2010, các bài toán được chia thành các tiểu bài (sub-task) có độ khó tăng dần, và điểm chỉ được tính khi tất cả các bài kiểm tra của một tiểu bài đều cho kết quả đúng, trong giới hạn thời gian và bộ nhớ quy định.
Trong một số trường hợp, chương trình của thí sinh phải tương tác với một thư viện máy tính bí mật, cho phép các bài toán mà dữ liệu đầu vào không cố định mà phụ thuộc vào tương tác của chương trình – ví dụ như các bài toán dạng trò chơi (hay còn gọi là bài toán tương tác). Một loại bài toán khác có dữ liệu đầu vào được công khai, trong đó thí sinh phải nộp một tệp đầu ra thay vì nộp chương trình. Việc tạo tệp đầu ra có thể được thực hiện bằng cách viết chương trình (có thể tận dụng các đặc điểm đặc biệt của dữ liệu đầu vào), làm thủ công hoặc kết hợp cả hai cách.
Tổng điểm từ hai ngày thi và tất cả các bài toán được cộng lại riêng cho từng thí sinh. Huy chương được trao dựa trên tổng điểm của thí sinh.
50% thí sinh có điểm cao nhất sẽ được trao huy chương, với tỷ lệ huy chương vàng : huy chương bạc : huy chương đồng : không có huy chương xấp xỉ 1:2:3:6 (tức là khoảng 1/12 số thí sinh sẽ nhận được huy chương vàng).
Tương quan quốc tế và khu vực
Việt Nam
Việt Nam đạt thứ hạng cao nhất (xếp thứ nhất trên 68 đoàn) vào năm 1999: 3 HCV, 1 HCB. Lần đầu, vào năm 1989, Việt Nam xếp thứ 10 trên 13 đoàn: 1 HCĐ. Năm 2024, Việt Nam xếp thứ 5 trên 93 đoàn: 2 HCV, 1 HCB, 1 HCĐ. Tổng thể, Việt Nam xếp thứ 13 trên 112 đoàn: 21 HCV, 51 HCB, 54 HCĐ
Các nước ASEAN
Trong các nước ASEAN, Singapore đăng cai tổ chức 2 lần vào các năm 2020, 2021. Thái Lan đăng cai 1 lần vào năm 2011. Indonesia đăng cai 1 lần vào năm 2022.
Các nước còn lại: Lào, Căm-pu-chia, Myanmar, Timor Leste chưa tham gia IOI.
“Máy” thi IOI
Trong một lần nhàn đàm trước (bài post ngày 27-3-2022), tôi đề cập đến việc máy đi thi lập trình. Máy mà đi thi lập trình thì “đúng nghề” rồi, đúng không ạ? Tuy nhiên, cho đến thời điểm bài viết này, các mô hình LLM chỉ tập trung “dự thi” lập trình trên trên Codeforces. Theo tìm hiểu của tôi, chỉ duy nhất gần đây (tháng 2/2025) OpenAI đăng bài báo “Competitive Programming with Large Reasoning Models” là có đề cập đến việc mô hình “dự thi” IOI 2024. Vì vậy, tôi xin chia sẻ vài ý chính của họ với anh/chị về cách họ tiếp cận để giải các bài lập trình của IOI 2024 (được tổ chức tại Ai Cập từ ngày 1 đến 8 tháng 9 năm 2024).
- Ý tưởng chính là họ áp dụng RL (Reinforcement Learning) nhằm tăng cường khả năng “lập luận” (reasoning) của LLM. Phương thức này có tên gọi là “Test-time strategy” (Chiến lược kiểm thử). Chúng ta có thể hiểu nôm na thế này: LLM tạo hàng nghìn, hàng triệu lời giải theo đề bài đã cho. Sau đó nó lọc ra các lời giải tốt nhất (chạy đúng hoặc chạy gần đúng) và nộp các ứng viên tốt nhất cho Ban giám khảo. Ví dụ, IOI cho phép thí sinh có thể nộp 50 ứng viên (xem phần Phụ lục) cho mỗi tiểu bài. Theo quy định của giải thì điểm của mỗi tiểu bài = Max (điểm của tất cả các ứng viên cho tiểu bài đó). Điểm của một bài bằng tổng điểm của các tiểu bài. Đây là lợi thế của máy so với người vì máy có thể tạo sinh (generate) hàng nghìn, hàng triệu lời giải trong “nháy mắt”.
- OpenAI thiết lập một mô hình riêng có tên gọi là “o1-ioi” chỉ dùng để thi IOI 2024. Kết quả là o1-ioi đạt được 156 điểm, thuộc phân vị (percentile) là 49% (tức là tốt hơn 49% thí sinh dự thi). Với kết quả này o1-ioi không được huy chương.
- OpenAI sau đó áp dụng phương thức tương tự đối với mô hình mới nhất của họ là o3 (chưa công khai) và “thi ảo” – nghĩa là như thi thật nhưng thời gian thi là sau tháng 9/2024. Kết quả là o3 đạt 395.64 điểm, vượt qua ngưỡng huy chương vàng là 360 điểm.
Suy ngẫm chậm
- Việc LLM có khả năng “suy luận” là không cần phải bàn cãi. Có thể kể ra vài LLM như vậy: Grok-3 (xAI), DeepSeek-R1 (DeepSeek), Gemini 2.0 Flash Thinking (Google DeepMind), o3 (OpenAI), Claude Sonnet 3.5 (Anthropic), Mistral & Mixtral (Mistral AI), LLaMA 2 (Meta).
- Họ sử dụng nhiều kỹ thuật để LLM có khả năng suy luận, chẳng hạn như:
◦ Chain-of-Thought (CoT) Reasoning: Suy luận từng bước.
◦ Tree-of-Thought (ToT) Reasoning: Xem xét nhiều khả năng trước khi đưa ra giải đáp.
◦ Self-Consistency: Thực hiện nhiều lần và chọn kết quả có “số phiếu cao nhất”. - Tuy nhiên, lập luận trong thi lập trình lại có logic hơi khác vì kết quả của lập luận là ẩn số, không biết trước. Vì vậy, OpenAI chọn giải pháp test-time strategy kết hợp với RL (Reinforcement Learning).
- Người ta kỳ vọng rằng, LLM đang dần trở thành lập trình viên hàng đầu, có thể đoạt huy chương tại bất cứ cuộc thi nào tương tự như IOI.
Phụ lục
Hệ thống chấm điểm
Việc chấm điểm và đánh giá được thực hiện trên hệ thống chấm điểm, hệ thống này cung cấp một môi trường thực thi tương tự như nhau cho mọi bài nộp. Các máy trạm làm việc có quyền truy cập mạng vào hệ thống chấm điểm.
Các máy trạm chấm điểm sẽ được trang bị phần cứng tương đương như máy trạm của thí sinh. Tuy nhiên, do sự khác biệt trong cấu hình phần mềm, không thể đảm bảo rằng môi trường thực thi trên máy trạm của thí sinh và máy trạm chấm điểm sẽ hoàn toàn giống nhau.
Bài toán
Mỗi thí sinh sẽ nhận được phiên bản tiếng Anh chính thức của các bài toán trong một phong bì vào mỗi ngày thi. Trưởng đoàn có thể dịch đề bài cho thí sinh, và bản dịch sẽ được đặt trong phong bì cùng với phiên bản tiếng Anh. Mỗi thí sinh cũng sẽ có quyền truy cập trực tuyến vào phiên bản tiếng Anh chính thức của đề bài và tất cả các bản dịch dưới dạng điện tử (PDF).
Mỗi bài toán có thể là bài lập trình (đáp án là mã nguồn) hoặc bài chỉ yêu cầu đầu ra (đáp án là tập hợp các tệp đầu ra). Mỗi bài toán được chia thành một số tiểu bài (sub-task), mỗi tiểu bài có một phần điểm nhất định trong tổng số điểm.
Đối với mỗi bài lập trình, giới hạn thời gian và bộ nhớ được quy định rõ ràng. Nhìn chung, các giới hạn này khá thoải mái (ví dụ: gấp đôi so với phương án giải quyết được mong đợi). Giới hạn bộ nhớ bao gồm toàn bộ bộ nhớ sử dụng, bao gồm kích thước mã thực thi, bộ nhớ ngăn xếp, bộ nhớ cấp phát động, v.v.
Đối với mỗi bài toán, thí sinh có thể tải xuống một tệp zip từ hệ thống chấm điểm. Đối với các bài lập trình, tệp này chứa các tệp giao diện, một chương trình chấm mẫu và một đoạn mã nguồn minh họa cách sử dụng giao diện của bài toán nhưng không giải được bài toán. Chương trình chấm mẫu có sẵn trên máy trạm thí sinh không giống với chương trình chấm chính thức được sử dụng bởi hệ thống chấm điểm.
Bài làm và nộp bài
Thí sinh nộp bài giải cho các bài toán bằng cách sử dụng hệ thống chấm điểm. Trừ khi có quy định khác, các hạn chế sau được áp dụng cho việc nộp bài:
Đối với mỗi bài lập trình:
- Mỗi bài nộp phải được viết bằng ngôn ngữ C++ và kích thước không vượt quá 50 KiB. Quá trình biên dịch trên máy chủ chấm điểm phải hoàn thành trong tối đa 10 giây và sử dụng không quá 512 MiB bộ nhớ.
- Bài nộp không được thực hiện các thao tác nhập/xuất trực tiếp; thay vào đó, dữ liệu chỉ được trao đổi thông qua các giao diện được chỉ định trong đề bài. Cụ thể, truy cập trực tiếp vào bất kỳ tệp nào, bao gồm cả đầu vào chuẩn (standard input) hoặc đầu ra chuẩn (standard output), đều bị cấm (tuy nhiên, có thể ghi dữ liệu vào đầu ra lỗi chuẩn – standard error).
Đối với mỗi bài chỉ yêu cầu đầu ra:
- Mỗi bài nộp là một tập hợp các tệp đầu ra.
Quy định về nộp bài:
- Thí sinh có thể nộp bài giải cho mỗi bài toán tối đa một lần mỗi phút. Hạn chế này không áp dụng trong 15 phút cuối cùng của vòng thi.
- Mỗi thí sinh có thể nộp tối đa 50 lần cho mỗi bài toán.
- Việc sử dụng đa luồng (multi-threading) được cho phép. Tuy nhiên, thời gian chạy của bài nộp sẽ được tính bằng tổng thời gian chạy của tất cả các luồng. Ví dụ: nếu có hai luồng chạy trong 5 giây mỗi luồng (chương trình kết thúc sau 5 giây thực tế), thì thời gian chạy của bài nộp sẽ được tính là 10 giây.
Ban kỹ thuật có thể cung cấp các phương thức thay thế để thí sinh nộp bài chấm điểm.
Chấm điểm
Điểm cho mỗi bài tập sẽ được tính như sau:
- Mỗi tiểu bài gồm một số lượng các trường hợp kiểm tra. Trừ khi có quy định khác, trong mỗi bài tập lập trình, bài nộp sẽ được thực thi một lần cho mỗi trường hợp kiểm tra.
- Đối với mỗi bài nộp, điểm cho mỗi trường hợp kiểm tra sẽ được tính dựa trên việc thực thi chương trình và/hoặc kết quả đầu ra.
- Việc thực thi chương trình trên mỗi trường hợp kiểm tra phải tuân theo giới hạn về thời gian và bộ nhớ, được quy định trong hệ thống chấm điểm. Nếu chương trình vượt quá những giới hạn này, nó sẽ nhận 0 điểm cho trường hợp kiểm tra đó.
- Đối với mỗi bài nộp, điểm cho mỗi tiểu bài là điểm thấp nhất trong các trường hợp kiểm tra của tiểu bài đó, trừ khi có quy định khác trong đề bài.
- Điểm cuối cùng cho mỗi tiểu bài là điểm cao nhất cho tiểu bài đó trong tất cả các bài nộp.
- Điểm cuối cùng cho mỗi bài tập là tổng điểm của các tiểu bài của nó. Tổng điểm này được làm tròn đến 2 chữ số thập phân gần nhất.
Ví dụ, xem xét một thí sinh đã nộp hai bài giải cho một bài tập có hai tiểu bài. Nếu bài giải đầu tiên đạt 30 điểm cho tiểu bài thứ nhất và 10 điểm cho tiểu bài thứ hai, và bài giải thứ hai đạt 0 điểm cho tiểu bài thứ nhất và 40 điểm cho tiểu bài thứ hai, thì điểm cuối cùng cho bài tập này sẽ là 70.
Điểm tối đa cho mỗi bài tập là 100 điểm.
Le Van Loi
