Ⓐ. Đề dẫn.
Ⓑ. Sơ lược về IOI.
Ⓒ. Một vài con số tương quan quốc tế & khu vực.
Ⓓ. “Máy” thi IOI.
Ⓔ. Suy
ngẫm chậm.
Ⓕ. Phụ
lục
~
Để giúp anh/chị
quyết định có đọc tiếp hay không, tôi xin phép cung cấp các thông tin liên quan
đến bài post này như sau:
·
Chủ
đề: Thi lập trình, Machine
Learning
·
Tính
thời sự: tháng 2/2025
·
Thời
gian đọc: 10 phút, kể cả
thời gian uống cà phê (uống cà phê xong là đọc xong)
Ⓐ. Đề 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.
-
Toàn bộ thông
tin liên quan đến IOI tôi lấy từ các trang sau:
https://en.wikipedia.org/wiki/International_Olympiad_in_Informatics
https://www.ioi2024.eg/contest-rules
https://www.ioi2024.eg/competition-tasks
Competitive Programming with Large
Reasoning Models
Ⓑ. 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.
Mỗi quốc gia cử một
đội gồm tối đa bốn học sinh, cùng với một trưởng đoàn, một phó trưởng đoàn và
một số khách mời. Học sinh trong mỗi quốc gia được tuyển chọn vào đội tuyển
quốc gia thông qua các cuộc thi tin học cấp quốc gia. Tại IOI, học sinh thi đấu
theo hình thức cá nhân. Không có bảng xếp hạng đội tuyển chính thức.
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).
Ⓒ. Một vài con số tương quan quốc tế & khu vực.
Top 20 nước sắp xếp theo số HCV
Chú ý:
·
Tên nước viết theo tiếng Anh.
·
HCV: Huy chương vàng
·
HCB: Huy chương bạc
·
HCD: Huy chương đồng.
|
TT |
Nước |
Năm đăng cai |
HCV |
HCB |
HCĐ |
Tổng HC |
Năm tham gia |
|
1 |
China |
2000 |
102 |
28 |
12 |
142 |
1989 |
|
2 |
Russia |
2016 |
68 |
40 |
12 |
120 |
1992 |
|
3 |
United States of America |
2003 |
68 |
39 |
16 |
123 |
1992 |
|
4 |
Republic of Korea |
2002 |
49 |
50 |
28 |
127 |
1990 |
|
5 |
Poland |
2005 |
44 |
52 |
35 |
131 |
1989 |
|
6 |
Japan |
2018 |
37 |
30 |
10 |
77 |
1994 |
|
7 |
Romania |
|
34 |
60 |
37 |
131 |
1990 |
|
8 |
Iran |
2017 |
32 |
67 |
24 |
123 |
1992 |
|
9 |
Bulgaria |
1989, 2009 |
27 |
55 |
45 |
127 |
1989 |
|
10 |
Slovakia |
|
26 |
45 |
36 |
107 |
1993 |
|
11 |
Taiwan |
2014 |
25 |
62 |
30 |
117 |
1994 |
|
12 |
Canada |
2010 |
22 |
35 |
40 |
97 |
1996 |
|
13 |
Vietnam |
|
21 |
51 |
54 |
126 |
1989 |
|
14 |
Singapore |
2020, 2021 |
16 |
45 |
43 |
104 |
1992 |
|
15 |
Croatia |
2007 |
16 |
44 |
47 |
107 |
1993 |
|
16 |
Belarus |
|
16 |
42 |
44 |
102 |
1990 |
|
17 |
Czech Republic |
|
16 |
29 |
52 |
97 |
1993 |
|
18 |
Thailand |
2011 |
15 |
38 |
62 |
115 |
1991 |
|
19 |
Germany |
1992 |
15 |
32 |
51 |
98 |
1989 |
|
20 |
Hungary |
1996, 2023 |
14 |
38 |
50 |
102 |
1989 |
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 sắp xếp theo số HCV
|
TT |
Nước |
Năm đăng cai |
HCV |
HCB |
HCĐ |
Tổng số HC |
Năm tham gia |
|
1 |
Vietnam |
|
21 |
51 |
54 |
126 |
1989 |
|
2 |
Singapore |
2020, 2021 |
16 |
45 |
43 |
104 |
1992 |
|
3 |
Thailand |
2011 |
15 |
38 |
62 |
115 |
1991 |
|
4 |
Indonesia |
2022 |
5 |
36 |
44 |
85 |
1995 |
|
5 |
Malaysia |
|
1 |
6 |
14 |
21 |
2012 |
|
6 |
Philippines |
|
0 |
4 |
14 |
18 |
2015 |
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.
❰Bên
lề❱: Test-time strategy là gì?
Ý
tưởng này xuất phát từ AlphaCode của DeepMind (thuộc Google).
1. Tạo
(generate) một số lượng lớn các lời giải đa dạng
2. Lọc
(filter) dựa trên kiểm tra cú pháp (sai là loại luôn) và kiểm thử ở mức
đơn giản
3. Gom
nhóm (cluster) các lời giải tương tự lại với nhau
4. Sắp
xếp lại (re-rank) các lời giải từ tốt nhất đến kém nhất.
5. Nộp
(submit) k lời giải có triển vọng nhất (k lời giải đầu
tiên sau khi sắp xếp lại). Giá trị k trong trường hợp của Codeforces là
10, trong trường hợp của IOI là 50.
❰/Bên
lề❱
Ⓔ. 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ư:
o
Chain-of-Thought
(CoT) Reasoning: Suy luận
từng bước.
o
Tree-of-Thought
(ToT) Reasoning: Xem
xét nhiều khả năng trước khi đưa ra giải đáp.
o
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.
-
Trân trọng
& vui nhã
(_/)
( •_•)
/ >☕
LeVanLoi
Ⓕ. 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.
