Lập trình thi đấu

Petr Mitrichev (trái) và Gennady Korotkevich (phải), hai lập trình viên thi đấu nổi tiếng trong một cuộc thi.

Lập trình thi đấu (tiếng Anh: competitive programming) là một môn thể thao trí tuệ trong đó những người tham gia sẽ cố gắng lập trình theo các yêu cầu được cung cấp. Các cuộc thi thường được tổ chức qua Internet hoặc mạng cục bộ. Những người tham gia được gọi là lập trình viên thi đấu (sport programmers). Lập trình thi đấu được công nhận và bảo trợ bởi nhiều công ty phần mềm và Internet đa quốc gia, chẳng hạn như Google[1][2] và Facebook.[3]

Trong một cuộc thi lập trình, bên tổ chức thường đưa ra một tập hợp các vấn đề logic hoặc toán học, còn được gọi là câu đố hoặc thử thách cho các thí sinh (số lượng thí sinh có thể là vài chục người hoặc thậm chí hàng trăm đến hàng ngàn). Thí sinh được yêu cầu viết các chương trình máy tính có khả năng giải quyết các vấn đề này. Việc đánh giá chủ yếu dựa trên số vấn đề đã giải quyết và thời gian đã bỏ ra để hoàn thành lời giải, nhưng cũng có thể bao gồm các yếu tố khác (chất lượng của kết quả đầu ra, thời gian thực thi, sử dụng bộ nhớ, kích thước chương trình, v.v.).

Lịch sử

Một trong những cuộc thi lâu đời nhất được biết đến là International Collegiate Programming Contest (ICPC) bắt đầu từ những năm 1970[4] và đã mở rộng tới 88 quốc gia trong phiên bản năm 2011.

Từ năm 1990 đến 1994, Owen Astrachan, Vivek Khera và David Kotz đã tổ chức một trong những cuộc thi lập trình phân tán dựa trên Internet đầu tiên, lấy cảm hứng từ ICPC.[5]

Sự quan tâm đến lập trình thi đấu đã phát triển mạnh kể từ năm 2000 với hàng chục nghìn người tham gia (xem Các cuộc thi nổi bật), điều này liên quan chặt chẽ đến sự phát triển của Internet, giúp tổ chức cuộc thi quốc tế trực tuyến và loại bỏ các giới hạn địa lý.

Tổng quan

Mục tiêu của lập trình thi đấu là viết mã nguồn chương trình máy tính để giải quyết các vấn đề được đưa ra. Đa số các vấn đề xuất hiện trong các cuộc thi lập trình liên quan đến toán học hoặc logic. Các vấn đề thường thuộc một trong những loại sau: tổ hợp, lý thuyết số, lý thuyết đồ thị, lý thuyết trò chơi sử dụng thuật toán, hình học tính toán, phân tích chuỗi và cấu trúc dữ liệu. Các vấn đề liên quan đến lập trình ràng buộc và trí tuệ nhân tạo cũng phổ biến trong một số cuộc thi.

Bất kể loại vấn đề, quá trình giải quyết một vấn đề có thể chia thành hai bước chính: xây dựng một thuật toán hiệu quả và triển khai thuật toán bằng một ngôn ngữ lập trình phù hợp (các ngôn ngữ lập trình được phép dùng khác nhau giữa các cuộc thi). Đây là hai kỹ năng thường được kiểm tra nhiều nhất trong các cuộc thi lập trình.

Ở hầu hết cuộc thi, việc đánh giá được thực hiện tự động bởi các máy chủ của bên tổ chức, thường được gọi là trình chấm hay hệ thống chấm bài (judge). Các lời giải được nộp bởi thí sinh sẽ được chạy trên trình chấm với một tập hợp các test case (thường là bí mật). Thông thường, trình chấm sẽ đánh giá theo nguyên tắc "đúng hoặc sai hoàn toàn", có nghĩa rằng một lời giải được chấp nhận ("Accepted") chỉ khi nó đạt kết quả tốt trên tất cả test case được chạy bởi trình chấm, và nếu không sẽ bị từ chối. Tuy nhiên, một số cuộc thi có thể cho phép việc chấm điểm theo phần, dựa trên số lượng test case đúng, chất lượng của kết quả, hoặc một số tiêu chí khác đã được chỉ định. Một số cuộc thi khác chỉ yêu cầu thí sinh nộp kết quả tương ứng với dữ liệu đầu vào đã được cung cấp, trong trường hợp này trình chấm chỉ cần phân tích kết quả được nộp.

Các hệ thống chấm bài trực tuyến (online judge) là môi trường mà ở đó diễn ra quá trình kiểm tra. Các hệ thống chấm bài trực tuyến có danh sách xếp hạng cho thấy người dùng có số lượng lời giải được chấp nhận nhiều nhất và/hoặc thời gian thực thi ngắn nhất cho một vấn đề cụ thể.[6]

Các cuộc thi nổi bật

Cuộc thi thuật toán

Tên cuộc thi[7] Bên tổ chức Người tham gia Mô tả Số lượng người tham gia Website
Google Code Jam (GCJ) Google mở Cuộc thi hằng năm được tổ chức và tài trợ bởi Google từ năm 2003 cho đến khi bị hủy vào năm 2023.[8] 32,702 (2022)[9] https://codingcompetitions.withgoogle.com/codejam Lưu trữ 2022-06-24 tại Wayback Machine
International Collegiate Programming Contest (ICPC)[10] ICPC Foundation sinh viên đại học Cuộc thi đồng đội dành cho sinh viên đại học, cuộc thi bao gồm nhiều vòng khu vực cuối cùng là vòng chung kết thế giới được tổ chức hằng năm. Mỗi đội bao gồm ba sinh viên đến từ cùng một trường đại học và họ chỉ được phép sử dụng một máy tính. 50,000+ (2022)[11] https://icpc.global/
Olympic Tin học Quốc tế (IOI) IOI học sinh trung học Cuộc thi quốc tế dành cho học sinh trung học. Tổ chức hằng năm kể từ 1989. Mỗi quốc gia có thể có tối đa 4 thí sinh. 349 từ 88 quốc gia (2022)[12] https://ioinformatics.org/
Meta Hacker Cup (trước đây là Facebook Hacker Cup) Meta Platforms mở Cuộc thi hằng năm được tổ chức từ 2011. Cuộc thi này được tổ chức và tài trợ bởi Meta (trước đây là Facebook). 27,604 (2022)[13] https://www.facebook.com/codingcompetitions/hacker-cup
Topcoder Open (TCO) Topcoder mở Cuộc thi thuật toán hằng năm được tổ chức từ 2001 cho đến khi bị hủy vào năm 2023.[14] https://www.topcoder.com/community/member-programs/topcoder-open/

Phần lớn cuộc thi ở trên thường được tổ chức thành nhiều vòng. Các cuộc thi thường khởi đầu bằng và kết thúc ở vòng chung kết tại chỗ. Những thí sinh dẫn đầu tại IOI và ICPC sẽ nhận được huy chương vàng, bạc và đồng. Trong các cuộc thi khác, giải thưởng tiền mặt được trao cho những người hoàn thành có thứ hạng cao nhất. Các cuộc thi cũng thu hút sự quan tâm của các nhà tuyển dụng từ nhiều công ty phần mềm và Internet, những công ty này thường chiêu mộ các thí sinh bằng những lời mời làm việc tiềm năng.

Trí tuệ nhân tạo và học máy

[15]

  • Kaggle – cuộc thi về khoa học dữ liệu và học máy.
  • CodeCup – cuộc thi AI về board game được tổ chức hàng năm kể từ năm 2003. Quy luật của trò chơi được công bố vào tháng 9 và giải đấu cuối cùng được tổ chức vào tháng 2.[16][17][18]
  • Google AI Challenge – cuộc thi dành cho sinh viên diễn ra từ năm 2009 đến 2011.
  • Halite[19] – Một thử thách lập trình AI được tài trợ bởi Two Sigma, Cornell Tech,[20] and Google.[21]
  • Russian AI Cup – cuộc thi lập trình trí tuệ nhân tạo mở.
  • CodinGame – tổ chức các cuộc thi lập trình bot theo mùa.

Cuộc thi tập trung vào công nghệ nguồn mở

  • Danh sách có thể không đầy đủ
Tên cuộc thi Nhà tài trợ chính Mô tả Bắt đầu từ Thời gian thường diễn ra Vòng đăng ký tiếp theo Trạng thái
Multi-Agent Programming Contest Đại học Công nghệ Clausthal phối hợp với các hội thảo về lập trình hướng tác tử Cuộc thi lập trình quốc tế hằng năm có mục đích khuyến kích nghiên cứu trong lĩnh vực phát triển và lập trình hệ thống đa tác tử. 2005 Tháng 9 9/2011 Hoạt động
Google Summer of Code Google Inc. Một chương trình hằng năm mà Google trả thù lao cho hàng trăm sinh viên nếu họ đã hoàn thành một phần mềm miễn phí / dự án mã nguồn mở theo yêu cầu trong suốt mùa hè. 2005 Tháng 3-tháng 8 23/3-3/4 Hoạt động
Google Highly Open Participation Contest Google Inc. Cuộc thi được Google tổ chức từ năm 2007-2008 dành cho học sinh trung học. Cuộc thi này được thiết kế để khuyến khích học sinh trung học tham gia vào các dự án mã nguồn mở. 2007 Tháng 11-tháng 2 Không rõ Không rõ

Nền tảng trực tuyến

Cộng đồng lập trình trên khắp thế giới đã xây dựng và duy trì nhiều nguồn tài nguyên trên internet phục vụ cho lập trình thi đấu. Họ cung cấp các cuộc thi độc lập với giải thưởng nhỏ hoặc không. Ngoài ra, các bài toán đã được lưu trữ trước đây cũng là nguồn tài liệu phổ biến để đào tạo về lập trình thi đấu. Một số tổ chức thường xuyên mở các cuộc thi lập trình, bao gồm:

Tên Mô tả Website
Advent of Code Cuộc thi lập trình hằng năm diễn ra trong thời gian Mùa Vọng, với một cặp bài toán mới được công bố mỗi ngày, đến hết Ngày Giáng Sinh. Bài toán thứ hai của mỗi ngày sẽ bị khóa cho đến khi phần đầu tiên được hoàn thành, và thường là bài tiếp theo logic. Cuộc thi có cả bảng xếp hạng công khai và riêng tư cho mỗi năm, trong đó việc xếp hạng dựa trên việc ai là người giải quyết bài toán đầu tiên. adventofcode.org
beecrowd Nền tảng lập trình thi đấu lớn nhất có trụ sở tại châu Mỹ Latin. Có hơn 2300 thử thách lập trình bằng 3 ngôn ngữ khác nhau (tiếng Anh, tiếng Bồ Đào Nha và tiếng Tây Ban Nha), được phân loại thành 9 thể loại và 10 độ khó khác nhau. Nền tảng này thường xuyên tổ chức các cuộc thi được tài trợ bởi các tập đoàn và bởi chính họ. Trước đây, nó được biết đến dưới tên URI Online Judge. www.beecrowd.com.br
CodeChef[22][23] Do Unacademy duy trì, nền tảng này tổ chức cuộc thi kéo dài 3 ngày và một số cuộc thi ngắn hàng tháng (một cuộc thi tương tự IOI tên là Lunchtime và một cuộc thi giống ICPC tên là Cook-Off), đồng thời cung cấp một nền tảng để tổ chức các cuộc cuộc thi miễn phí cho các cơ sở giáo dục. Hai người chiến thắng dẫn đầu của cuộc thi dài sẽ nhận giải thưởng tiền mặt trong khi 10 người dẫn đầu toàn cầu sẽ được nhận áo thun. www.codechef.com
CodeCup Cuộc thi quốc tế hằng năm về lập trình AI board game được tổ chức bởi Olympic Tin học Hà Lan từ năm 2003.[17][18] codecup.nl
Codeforces[24][22] Nguồn tài nguyên của Nga, do Đại học ITMO duy trì, thường xuyên tổ chức các cuộc thi ngắn (lên đến hai lần mỗi tuần). Điểm đặc biệt: tất cả các lời giải đều là mã nguồn mở, khả năng kiểm tra tính đúng đắn cho lời giải của thí sinh khác trong "hacking phase", cuộc thi ảo, luyện tập, v.v. codeforces.com
CodinGame Nhiều câu đố (độ khó tăng dần), code golf. Tổ chức các cuộc thi trực tuyến thường xuyên (thử thách AI, bài toán tối ưu hóa). www.codingame.com
HackerEarth[22] Công ty có trụ sở tại Bangalore, Ấn Độ, tạo môi trường cho cuộc thi trực tuyến với mục tiêu cung cấp giải pháp đánh giá cho các nhà tuyển dụng. www.hackerearth.com
HackerRank HackerRank cung cấp các bài toán lập trình trong các lĩnh vực khác nhau của ngành Khoa học Máy tính. Họ cũng tổ chức Codesprints hằng năm giúp kết nối các lập trình viên và startup tại Thung lũng Silicon. hackerrank.com
Project Euler[23] Bộ sưu tập lớn về các vấn đề tính toán toán học (tức là không liên quan trực tiếp đến lập trình nhưng thường đòi hỏi kỹ năng lập trình để giải quyết). projecteuler.net
Topcoder[24][22] Nguồn tài nguyên và tên công ty có trụ sở tại Hoa Kỳ, tổ chức các cuộc thi và cung cấp các vấn đề công nghiệp như một loại công việc làm thêm; tổ chức hàng chục cuộc thi ngắn và một số cuộc thi dài ("marathons") mỗi năm. Điểm đặc biệt - người tham gia có cơ hội kiểm tra tính đúng đắn cho lời giải của các thí sinh khác sau giai đoạn lập trình và trước sự kiểm thử tự động cuối cùng (gọi là "challenge phase"). www.topcoder.com
UVa Online Judge[24][22] Chứa hơn 4.500 bài toán để luyện tập. Tổ chức các cuộc thi trực tuyến thường xuyên. Được mở vào năm 1995, đây là một trong những website lâu đời nhất trong lĩnh vực này. onlinejudge.org
SPOJ[22] Hệ thống chấm bài trực tuyến của Ba Lan cung cấp nhiều bài toán để luyện tập và làm nền tảng cho các tổ chức khác mở cuộc thi lập trình của họ. www.spoj.com
Open Kattis Phiên bản công cộng của hệ thống quản lý cuộc thi Kattis, với một kho lưu trữ chứa hơn 2600 bài toán.[24] Kattis được phát triển để hỗ trợ các khóa học khoa học máy tính, nhưng cũng được sử dụng để tổ chức các cuộc thi có tiếng như vòng chung kết ICPC.[25] open.kattis.com
AtCoder Có trụ sở tại Nhật Bản, AtCoder mở các cuộc thi lập trình trực tuyến hàng tuần. Các cuộc thi được tổ chức bằng cả tiếng Nhật và tiếng Anh.

Tính đến năm 2020, đây là một trong những nền tảng phổ biến nhất trong thể loại này.[26]

atcoder.jp
Timus Có các bài toán từ các cuộc thi trong vùng Ural. acm.timus.ru
VJudge Có các bài toán từ nhiều hệ thống chấm bài trực tuyến. vjudge.net
Baekjoon OJ Hệ thống chấm bài trực tuyến của Hàn Quốc. acmicpc.net
LeetCode LeetCode có hơn 2.300 câu hỏi bao gồm nhiều khái niệm về lập trình khác nhau, tổ chức các cuộc thi mỗi tuần và mỗi hai tuần. Các nhiệm vụ lập trình được cung cấp bằng tiếng Anh và tiếng Trung. leetcode.com
Luogu Luogu là hệ thống chấm bài trực tuyến ở Trung Quốc. Cuộc thi này có các vấn đề từ Olympic Tin học Trung Quốc tổ chức bởi CCF, cũng như các cuộc thi do người dùng tổ chức. luogu.com.cn

Lợi ích và chỉ trích

Tham gia vào các cuộc thi lập trình có thể tăng sự hứng thú của sinh viên đối với việc nghiên cứu ngành khoa học máy tính. Những kỹ năng mà họ thu được thông qua các cuộc thi lập trình giống như ICPC cũng cải thiện cơ hội nghề nghiệp, bởi vì chúng giúp vượt qua các "cuộc phỏng vấn về kỹ thuật", thường đòi hỏi ứng viên giải quyết các vấn đề lập trình và thuật toán phức tạp ngay tại chỗ.[24][27]

Tuy vậy cũng có những sự chỉ trích về lập trình thi đấu, đặc biệt từ các nhà phát triển phần mềm chuyên nghiệp.[28] Một điều chỉ trích phổ biến là nhiều cuộc thi lập trình tốc độ nhanh dạy cho các thí sinh các thói quen lập trình và phong cách code không tốt (như sử dụng các macro một cách không cần thiết, thiếu tính trừu tượng của OOP và comment, sử dụng tên biến ngắn, v.v.).[29][28] Ngoài ra, vì chỉ cung cấp các câu đố thuật toán nhỏ với lời giải tương đối ngắn, các cuộc thi lập trình như ICPC và IOI có thể không dạy mọi người những kỹ năng tốt trong ngành kỹ thuật phần mềm, vì các dự án phần mềm trong thực tế thường có hàng nghìn dòng mã và được phát triển bởi các nhóm lớn trong thời gian dài.[28] Peter Norvig đã đề cập rằng dựa trên dữ liệu có sẵn, việc giành chiến thắng trong các cuộc thi lập trình có mối tương quan tiêu cực với hiệu suất của một lập trình viên trong công việc của họ tại Google (mặc dù các người chiến thắng trong các cuộc thi có cơ hội cao được tuyển dụng).[30] Sau đó, Norvig tuyên bố rằng tương quan này chỉ được quan sát trên một tập dữ liệu nhỏ, nhưng không thể xác minh sau khi xem xét một tập dữ liệu lớn hơn.[31] 

Một quan điểm khác là thay vì "lãng phí" thời gian để thi đấu quá nhiều, giải các bài toán đã có lời giải, các lập trình viên có tiếng nên đầu tư thời gian của họ vào việc giải quyết các vấn đề trong thực tế.[28]

Đọc tiếp

  • Halim, S., Halim, F. (2013). Competitive Programming 3: The New Lower Bound of Programming Contests. Lulu.
  • Laaksonen, A. (2017). Guide to Competitive Programming (các chủ đề dành cho sinh viên đại học trong ngành khoa học máy tính). Cham: Springer International Publishing.
  • Xu, X. (2020) The development, prosperity and decline of Olympic in Informatics. Xuất bản trực tuyến.
  • Kostka, B. (2021). Sports programming in practice. Đại học Wrocław.

Xem thêm

Tham khảo

  1. ^ “Google Code Jam”. google.com. Bản gốc lưu trữ ngày 31 tháng 5 năm 2023. Truy cập ngày 20 tháng 2 năm 2016.
  2. ^ “TCO12 Sponsor: Google - TCO 12”. topcoder.com. Bản gốc lưu trữ ngày 16 tháng 2 năm 2012.
  3. ^ “Facebook Hacker Cup”. Facebook. Truy cập ngày 20 tháng 2 năm 2016.
  4. ^ Li, Yujia; Choi, David; Chung, Junyoung; Kushman, Nate; Schrittwieser, Julian; Leblond, Rémi; Eccles, Tom; Keeling, James; Gimeno, Felix; Lago, Agustin Dal; Hubert, Thomas (9 tháng 12 năm 2022). “Competition-Level Code Generation with AlphaCode”. Science. 378 (6624): 1092–1097. doi:10.1126/science.abq1158. ISSN 0036-8075.
  5. ^ Khera, Vivek; Astrachan, Owen; Kotz, David (1993). “The internet programming contest” (PDF). ACM SIGCSE Bulletin. 25 (1): 48–52. doi:10.1145/169073.169105. ISSN 0097-8418.
  6. ^ Programming Challenges (Skiena & Revilla) ISBN 0387001638, ISBN 978-0387001630
  7. ^ Kostka, Bartosz (2021). Sports Programming in Practice (PDF). University of Wrocław.
  8. ^ “Celebrate Google's Coding Competitions with a final round of programming fun”. Google Developers Blog. Google. Bản gốc lưu trữ ngày 15 tháng 5 năm 2023. Truy cập ngày 28 tháng 2 năm 2023.
  9. ^ “Code Jam - Google's Coding Competitions”. Coding Competitions (bằng tiếng Anh). Bản gốc lưu trữ ngày 27 tháng 6 năm 2023. Truy cập ngày 26 tháng 2 năm 2023.
  10. ^ “ICPC”. icpc.global (bằng tiếng Anh). Truy cập ngày 26 tháng 2 năm 2023.
  11. ^ “ICPC”. icpc.global (bằng tiếng Anh). Truy cập ngày 26 tháng 2 năm 2023.
  12. ^ “Olympiads”. stats.ioinformatics.org. Truy cập ngày 26 tháng 2 năm 2023.
  13. ^ “Meta Hacker Cup - 2022 - Qualification Round”. www.facebook.com. Truy cập ngày 26 tháng 2 năm 2023.
  14. ^ “FAQ - Topcoder Community Town Hall with Doug Hanson, Topcoder CEO”. Topcoder (bằng tiếng Anh). Truy cập ngày 28 tháng 2 năm 2023.
  15. ^ “14 Active AI Game Competitions to Check Out in 2022 (Ongoing & Upcoming)”. www.gocoder.one.
  16. ^ “CodeCup”. www.codecup.nl.
  17. ^ a b Lasse Hakulinen. Survey on Informatics Competitions: Developing Tasks – Olympiads in Informatics, 2011, Vol. 5, 12–25.
  18. ^ a b Wevers, Lesley (2014). “Monte-Carlo Tree Search for Poly-Y” (PDF). University of Twente. Bản gốc (PDF) lưu trữ ngày 13 tháng 4 năm 2017. Truy cập ngày 16 tháng 9 năm 2018.
  19. ^ “Halite Artificial Intelligence Programming Challenge”. www.halite.io.
  20. ^ “Two Sigma Announces Public Launch of Halite”. tech.cornell.edu. 2 tháng 11 năm 2016.
  21. ^ “Halite helps students and developers compete to build better AI on Google Cloud Platform”. Bản gốc lưu trữ ngày 31 tháng 1 năm 2023. Truy cập ngày 28 tháng 10 năm 2023.
  22. ^ a b c d e f Luigi, William Di; Farina, Gabriele; Laura, Luigi; Nanni, Umberto; Temperini, Marco; Versari, Luca (2016). “oii-web: an Interactive Online Programming oii-web: an Interactive Online Programming Contest Training System” (PDF). Olympiads in Informatics. 10: 207–222. doi:10.15388/ioi.2016.13.
  23. ^ a b Combéfis, Sébastien; Wautelet, Jérémy (2014). “Programming Trainings and Informatics Teaching Through Online Contests” (PDF). Olympiads in Informatics. 8: 21–34.
  24. ^ a b c d e Bloomfield, Aaron; Sotomayor, Borja. “A Programming Contest Strategy Guide” (PDF). SIGCSE '16: Proceedings of the 47th ACM Technical Symposium on Computing Science Education.
  25. ^ Enström, E.; Kreitz, G.; Niemelä, F.; Söderman, P.; Kann, V. (2011). “Five years with Kattis – using an automated assessment system in teaching” (PDF). IEEE Frontiers in Education Conference.
  26. ^ Mirzayanov, Mike; Pavlova, Oksana; Mavrin, Pavel; Melnikov, Roman; Plotnikov, Andrew; Parfenov, Vladimir; Stankevich, Andrew (2020). “Codeforces as an Educational Platform for Learning Programming in Digitalization” (PDF). Olympiads in Informatics. 14. ISSN 1822-7732.
  27. ^ Jackson, Dean (1 tháng 12 năm 2013). “The Google Technical Interview. How to Get Your Dream Job” (PDF). XRDS: Crossroads, the ACM Magazine for Students. 20 (2): 12–14. doi:10.1145/2539270.
  28. ^ a b c d Smith, Duncan (2 tháng 12 năm 2015). “The Competitive Programming Debate”.
  29. ^ Halim, Steven. “CS3233 - Competitive Programming”. NUS School of Computing.
  30. ^ “Winning at programming competitions is a negative factor for being good on the job”. YouTube. 5 tháng 4 năm 2015.
  31. ^ “HN discussion on correlation between job performance and competitive programming”. tháng 12 năm 2020.

Liên kết ngoài

Dự án nguồn mở để tổ chức các cuộc thi