Tìm hiểu về Subtask trong thi đấu tin học trẻ

1. Subtask là gì?
2. Test là gì?
3. Vì sao đề bài cần chia Subtask?
4. Cách đọc giới hạn Subtask
   • Subtask 1
   • Subtask 2
5. Đạt một test có nghĩa là gì?
6. Khi nào được xem là đạt một Subtask?
7. Hệ thống chấm bài có tự động cho biết Subtask nào đạt không?
   • Trường hợp 1: Hệ thống hiển thị từng Subtask
   • Trường hợp 2: Hệ thống chỉ hiển thị tổng điểm
8. Subtask có đồng nghĩa với phần trăm test không?
9. Subtask liên quan thế nào đến thuật toán?
10. Chiến lược làm bài khi đi thi
11. Những điều cần ghi nhớ
12. Cách chấm bài lập trình: LQDOJ, VNOI, CODEFORCES
13. Link các trang web luyện lập trình

1. Subtask là gì?

Subtask là một nhóm nhỏ các bộ dữ liệu kiểm tra (test) trong một bài toán lập trình.

Khi ra đề, ban tổ chức có thể chia các test thành nhiều nhóm khác nhau. Mỗi nhóm có những giới hạn dữ liệu riêng và có thể được quy định số điểm tương ứng.

Mục đích của việc chia Subtask là đánh giá khả năng giải bài toán của thí sinh ở nhiều mức độ khác nhau.

Ví dụ, một bài toán có tổng cộng 100 điểm được chia thành hai Subtask:

• Subtask 1 chiếm 70% số điểm.
• Subtask 2 chiếm 30% số điểm.

Nếu thí sinh giải đúng tất cả test của Subtask 1 nhưng không giải được Subtask 2, thí sinh có thể nhận được 70 điểm, tùy theo quy định chấm điểm của đề thi.

2. Test là gì?

Test là một bộ dữ liệu dùng để kiểm tra chương trình.

Mỗi test thường bao gồm dữ liệu đầu vào và kết quả đầu ra tương ứng.

Ví dụ, bài toán tính tổng hai số có dữ liệu vào:

3 5

Kết quả đúng:

8

Nếu chương trình nhận dữ liệu 3 và 5 rồi in ra 8, chương trình vượt qua test này.

Nếu chương trình in ra 7, chương trình không vượt qua test này.

Một bài thi có thể có hàng chục hoặc hàng trăm test. Các test này được hệ thống chấm tự động sử dụng để đánh giá chương trình.

3. Vì sao đề bài cần chia Subtask?

Không phải thuật toán nào cũng giải được mọi bộ dữ liệu trong giới hạn thời gian cho phép.

Một thuật toán có thể chạy tốt với số nhỏ nhưng chạy quá chậm khi số liệu tăng lên rất lớn.

Vì vậy, ban tổ chức có thể chia bài toán thành nhiều nhóm:

• Nhóm dữ liệu nhỏ: phù hợp với thuật toán đơn giản.
• Nhóm dữ liệu lớn hơn: cần thuật toán hiệu quả hơn.
• Nhóm dữ liệu lớn nhất: có thể yêu cầu thuật toán tối ưu.

Cách chia này giúp thí sinh có cơ hội đạt điểm ngay cả khi chưa tìm được lời giải tối ưu cho toàn bộ bài toán.

4. Cách đọc giới hạn Subtask

Xét bài toán Tổng ước: Cho ba số nguyên dương a, b, c, yêu cầu tìm giá trị lớn nhất trong tổng các ước dương của ba số.

Đề bài ghi:

• Subtask 1: có 70% test với a, b, c ≤ 10⁶.
• Subtask 2: có 30% test với a, b, c ≤ 10¹².

Subtask 1

Có 70% số test thuộc nhóm mà cả ba số a, b, c đều không vượt quá 1.000.000.

Ta có:

10⁶ = 1.000.000.

Ví dụ, bộ dữ liệu sau đáp ứng giới hạn của Subtask 1:

100 5000 1000000

Subtask 2

Có 30% số test thuộc nhóm mà cả ba số a, b, c đều không vượt quá 1.000.000.000.000.

Ta có:

10¹² = 1.000.000.000.000.

Ví dụ, bộ dữ liệu sau đáp ứng giới hạn của Subtask 2:

1000000000 50000000000 1000000000000

Lưu ý: Hai nhóm trên mô tả giới hạn dữ liệu. Nếu đề không nói rõ các nhóm loại trừ nhau hay cách chấm cụ thể, không nên tự suy ra rằng mọi test của Subtask 2 đều phải lớn hơn giới hạn Subtask 1.

5. Đạt một test có nghĩa là gì?

Một test được xem là đạt khi chương trình đáp ứng yêu cầu của hệ thống chấm, bao gồm:

• Đọc dữ liệu đúng định dạng.
• Tính toán đúng.
• Xuất kết quả đúng định dạng.
• Chạy trong giới hạn thời gian và bộ nhớ cho phép.

Nếu chương trình trả về kết quả sai, gặp lỗi khi chạy hoặc chạy quá thời gian, test đó có thể không được tính là đạt.

Các trạng thái thường gặp trên hệ thống chấm bài:

• Accepted (AC): Chương trình được chấp nhận, thông thường là vượt qua toàn bộ test được chấm.
• Wrong Answer (WA): Kết quả sai ở ít nhất một test.
• Time Limit Exceeded (TLE): Chương trình chạy quá thời gian.
• Runtime Error (RE): Chương trình gặp lỗi khi chạy.
• Compilation Error (CE): Chương trình không biên dịch thành công.

Tên trạng thái và mức độ chi tiết hiển thị có thể khác nhau giữa các hệ thống chấm.

6. Khi nào được xem là đạt một Subtask?

Thông thường, nếu quy định chấm yêu cầu vượt qua toàn bộ test trong một Subtask thì thí sinh phải làm đúng tất cả test thuộc nhóm đó mới nhận được điểm của nhóm.

Ví dụ, một Subtask có 10 test:

• Đạt 10/10 test: vượt qua toàn bộ nhóm.
• Đạt 9/10 test: chưa vượt qua toàn bộ nhóm.
• Đạt 5/10 test: chưa vượt qua toàn bộ nhóm.

Tuy nhiên, một số hệ thống hoặc kỳ thi có thể áp dụng cách tính điểm khác. Vì vậy, cần đọc quy định chấm điểm cụ thể.

7. Hệ thống chấm bài có tự động cho biết Subtask nào đạt không?

Sau khi nộp bài, hệ thống sẽ chạy chương trình với các bộ dữ liệu kiểm tra và trả về kết quả.

Trường hợp 1: Hệ thống hiển thị từng Subtask

Hệ thống có thể hiển thị số điểm hoặc trạng thái của từng nhóm.

Ví dụ minh họa:

• Subtask 1: 70/70 điểm.
• Subtask 2: 0/30 điểm.
• Tổng điểm: 70/100.

Kết quả này cho biết chương trình đạt nhóm thứ nhất nhưng không nhận được điểm nhóm thứ hai.

Trường hợp 2: Hệ thống chỉ hiển thị tổng điểm

Một số hệ thống chỉ hiển thị tổng điểm hoặc trạng thái của bài nộp. Trong trường hợp này, thí sinh có thể không biết chính xác mình trượt test nào hoặc trượt Subtask nào.

Do đó, không phải kỳ thi nào cũng cho phép thí sinh xem đầy đủ test và kết quả chi tiết.

8. Subtask có đồng nghĩa với phần trăm test không?

Không. Cần phân biệt hai khái niệm:

• Phần trăm test: Tỷ lệ số lượng bộ dữ liệu kiểm tra thuộc một nhóm.
• Phần trăm điểm: Tỷ lệ số điểm mà nhóm đó đóng góp vào tổng điểm bài toán.

Ví dụ, đề ghi 70% test không tự động có nghĩa là 70% điểm.

Trong bài Tổng ước đang xét, cách ghi 70% test và 30% test cho biết tỷ lệ test thuộc các nhóm. Muốn khẳng định mỗi nhóm được bao nhiêu điểm, cần xem thêm quy định chấm điểm của đề hoặc kỳ thi.

Trong nhiều đề thi lập trình, tỷ lệ test được dùng tương ứng với tỷ lệ điểm, nhưng không nên mặc định điều đó đúng với mọi đề.

9. Subtask liên quan thế nào đến thuật toán?

Giới hạn dữ liệu ảnh hưởng trực tiếp đến việc lựa chọn thuật toán.

Ví dụ, với bài Tổng ước:

Cách 1: Duyệt tất cả các số từ 1 đến n để tìm ước.

Cách này có thể chấp nhận được với một số dữ liệu nhỏ, nhưng sẽ quá chậm khi n lên đến 10¹².

Cách 2: Chỉ duyệt i từ 1 đến căn bậc hai của n.

Nếu i là ước của n thì n/i cũng là một ước. Nhờ vậy, ta có thể tìm các ước theo từng cặp mà không cần duyệt đến n.

Với n ≤ 10¹², căn bậc hai của n bằng 10⁶. Như vậy, mỗi số chỉ cần xét tối đa khoảng một triệu giá trị i.

Đây là cách làm hiệu quả hơn nhiều so với duyệt đến một nghìn tỷ.

10. Chiến lược làm bài khi đi thi

1. Đọc kỹ yêu cầu và xác định kết quả cần tìm.
2. Đọc giới hạn dữ liệu của toàn bài và từng Subtask.
3. Xem xét thuật toán đơn giản có đủ nhanh cho dữ liệu nhỏ hay không.
4. Tìm cách tối ưu thuật toán để xử lý nhóm dữ liệu lớn.
5. Nếu chưa tìm được lời giải hoàn chỉnh, có thể xây dựng lời giải cho nhóm dữ liệu nhỏ trước, miễn là lời giải tuân thủ các điều kiện và quy định của bài thi.
6. Kiểm tra các trường hợp đặc biệt, kiểu dữ liệu, thời gian chạy và định dạng đầu vào, đầu ra.
7. Nộp bài và xem kết quả chấm để biết chương trình được bao nhiêu điểm.

11. Những điều cần ghi nhớ

1. Test là bộ dữ liệu dùng để kiểm tra chương trình.
2. Subtask là nhóm các test có giới hạn hoặc điều kiện chấm nhất định.
3. Đạt một test không đồng nghĩa với đạt cả Subtask.
4. Muốn đạt toàn bộ một Subtask, thông thường phải vượt qua tất cả test của nhóm đó.
5. Tỷ lệ test không nhất thiết bằng tỷ lệ điểm.
6. Hệ thống chấm có thể hiển thị điểm theo Subtask hoặc chỉ hiển thị tổng điểm.
7. Đọc giới hạn Subtask giúp thí sinh lựa chọn thuật toán phù hợp.
8. Mục tiêu cuối cùng là xây dựng thuật toán đúng và đủ nhanh để xử lý tất cả dữ liệu hợp lệ của đề bài.

12. Cách chấm bài lập trình: LQDOJ, VNOI, CODEFORCES

- Giới thiệu

LQDOJ: Là nền tảng chấm bài lập trình trực tuyến, giúp học sinh luyện tập thuật toán bằng các ngôn ngữ như C++, Python.

VNOI: Là cộng đồng Tin học Việt Nam, cung cấp tài liệu, bài tập và các hoạt động hỗ trợ học sinh luyện thi lập trình. Cách chấm bài phụ thuộc vào hệ thống hoặc kỳ thi cụ thể.

Codeforces: Là nền tảng luyện tập và thi đấu lập trình quốc tế. Hệ thống tự động chấm bài và có cơ chế xếp hạng người tham gia thi đấu.

- Hệ thống chấm bài hoạt động như thế nào?

Khi học sinh nộp chương trình, hệ thống thường thực hiện các bước sau:

• Bước 1: Nhận mã nguồn do học sinh nộp.
• Bước 2: Biên dịch chương trình. Nếu biên dịch thất bại, bài có thể bị báo lỗi CE.
• Bước 3: Chạy chương trình với các bộ dữ liệu kiểm tra, gọi là test.
• Bước 4: So sánh kết quả của chương trình với kết quả chuẩn.
• Bước 5: Kiểm tra giới hạn thời gian và bộ nhớ.
• Bước 6: Trả về trạng thái hoặc điểm số của bài làm.

- Các trạng thái chấm bài thường gặp

- Test là gì?

Test là một bộ dữ liệu được dùng để kiểm tra chương trình.

Ví dụ, đề bài yêu cầu tính tổng hai số nguyên a và b.

Input:
3 5

Output:
8

Hệ thống có thể sử dụng nhiều test khác nhau:

Nếu chương trình chỉ đúng với test 1 nhưng sai với test 2, 3 hoặc 4 thì bài có thể bị WA hoặc không đạt toàn bộ điểm, tùy cách chấm.

- Test ẩn là gì?

Test ẩn là những bộ dữ liệu kiểm tra mà học sinh không được cung cấp đầy đủ khi nộp bài.

Mục đích của test ẩn là kiểm tra xem chương trình có giải quyết đúng bài toán trong nhiều trường hợp khác nhau hay không.

Ví dụ, chương trình tính tổng hai số có thể chạy đúng với các số nhỏ nhưng sai khi gặp số rất lớn do tràn kiểu dữ liệu int.

Vì vậy, học sinh không thể chỉ dựa vào một vài ví dụ trong đề để kết luận rằng chương trình đã đúng hoàn toàn.

- Subtask là gì?

Subtask là một nhóm test có chung những điều kiện hoặc giới hạn dữ liệu nhất định. Đề bài có thể chia thành nhiều Subtask với số điểm khác nhau.

Ví dụ, một bài có N là số nguyên dương và được chia thành ba Subtask:

Các điều kiện trên là ví dụ minh họa. Điều kiện thực tế phải theo đề bài.

- Làm sao biết mình đạt Subtask nào?

Học sinh cần xem kết quả chấm bài mà hệ thống trả về.

Ví dụ, giả sử kết quả chấm theo từng Subtask như sau:

Trong ví dụ này, học sinh đạt 60 điểm trên tổng số 100 điểm.

Lưu ý: Đây là ví dụ về cách tính điểm theo Subtask, không phải quy tắc bắt buộc của tất cả hệ thống. Một số đề chấm điểm theo từng test hoặc sử dụng cách tính điểm riêng.

- Có phải cứ chạy đúng ví dụ là đạt điểm không?

Không.

Ví dụ trong đề chỉ là một số trường hợp minh họa. Hệ thống có thể kiểm tra thêm nhiều dữ liệu khác, bao gồm dữ liệu lớn, dữ liệu nhỏ nhất, dữ liệu đặc biệt và những trường hợp dễ làm chương trình sai.

Muốn đạt điểm cao, học sinh cần:

• Hiểu đúng yêu cầu của đề bài.
• Viết chương trình cho kết quả chính xác.
• Kiểm tra các trường hợp đặc biệt.
• Sử dụng thuật toán phù hợp với giới hạn dữ liệu.
• Đảm bảo chương trình không vượt quá thời gian và bộ nhớ cho phép.

- So sánh LQDOJ, VNOI và Codeforces

- Kết luận

Khi luyện thi lập trình, học sinh cần hiểu rõ sáu khái niệm quan trọng:

1. Test: Bộ dữ liệu dùng để kiểm tra chương trình.
2. Test ẩn: Dữ liệu kiểm tra không được công khai đầy đủ.
3. AC: Bài được chấp nhận theo yêu cầu chấm.
4. WA: Chương trình có kết quả sai.
5. TLE: Chương trình chạy quá thời gian.
6. Subtask: Nhóm test có điều kiện hoặc giới hạn dữ liệu nhất định, có thể được tính điểm riêng.

Hiểu được cách chấm bài giúp học sinh biết vì sao chương trình bị sai, vì sao chưa đạt điểm tối đa và cần cải thiện thuật toán như thế nào.

13. Link các trang web luyện lập trình

- LQDOJ - Le Quy Don Online Judge

Trang web luyện tập và chấm bài lập trình trực tuyến.

• Trang chủ: https://www.lqdoj.edu.vn/
• Bài tập: https://www.lqdoj.edu.vn/problems/

- VNOI - Cộng đồng Tin học Việt Nam

Cung cấp tài liệu, kiến thức thuật toán và tài nguyên luyện thi Tin học.

• Trang chủ: https://vnoi.info/
• Hệ thống chấm bài VNOI OJ: https://oj.vnoi.info/

- Codeforces

Nền tảng luyện tập và thi đấu lập trình quốc tế, có hệ thống chấm bài tự động và xếp hạng người tham gia.

• Trang chủ: https://codeforces.com/
• Danh sách bài tập: https://codeforces.com/problemset
• Các cuộc thi: https://codeforces.com/contests
• Bảng xếp hạng: https://codeforces.com/ratings

- Hướng dẫn lựa chọn

1. LQDOJ: Bắt đầu luyện tập và làm quen với cách nộp bài, xem kết quả chấm.
2. VNOI OJ: Luyện tập thêm các bài toán thuật toán và Tin học.
3. Codeforces: Rèn luyện tư duy thuật toán và tham gia các cuộc thi lập trình.

Lưu ý: Một số trang có thể yêu cầu đăng ký tài khoản để nộp bài hoặc tham gia thi đấu.