Con đường học lập trình thi đấu
Tác giả: Học viên Vàng Đức Hoàng – FCTC 0117
![What is Competitive Programming and How to Prepare for It? - GeeksforGeeks](https://media.geeksforgeeks.org/wp-content/cdn-uploads/20191004160106/How-to-Prepare-for-Competitive-Programming.png)
I. Lập trình thi đấu là gì, tại sao cần lập trình thi đấu?
Lập trình thi đấu là bộ môn khá phổ biến trên thế giới và hiện nay đang rất phát triển tại Việt Nam. Tùy vào yêu cầu và tính chất của các cuộc thi bạn tham dự mà có thể có nhiều format thi lập thi đấu khác nhau, nhưng nhìn chung lập trình thi đấu yêu cầu bạn phải giải quyết các bài toán được đưa ra theo các thuật toán logic tối ưu nhất có thể. Cũng chính vì vậy mà lập trình thi đấu được coi là một cách để rèn luyện tư duy logic của lập trình viên.
Hiện nay có rất nhiều các công ty công nghệ lớn như Facebook. Alphabet, Microsoft, Amazon,… tuyển dụng nhân viên thông qua lập trình thi đấu (chẳng hạn như Google CodeJam). Vì vậy, biết các kĩ năng về lập trình thi đấu chính là một thế mạnh để bạn đến với những công ty như trên.
Hoặc, nếu bạn chưa muốn nghĩ xa tới vậy, thì competitive programming cũng là quá trình bạn được học cấu trúc dữ liệu và thuật toán để có tư duy sáng hơn, tốt hơn, nhanh hơn so với những cách làm thông thường. Nhìn chung, lợi ích của việc năng nổ tham gia các cuộc thi lập trình thi đấu là rất nhiều!
II. Tài liệu tham khảo
Tài liệu trên Internet và các sách có rất nhiều, nhưng để chọn lọc dựa theo kinh nghiệm của mình và một số sách thì mình xin giới thiệu một vài quyển sau:
- Tài liệu giáo khoa Chuyên Tin (quyển 1,2,3)
- Giải thuật và Lập trình (DSAP Textbook) – Lê Minh Hoàng
- Competitive Programmer’s Handbook của Antti Laaksonen
- S. S. Skiena và M. A. Revilla: Programming Challenges: The Programming Contest Training Manual
- S. Halim và F. Halim: Competitive Programming 3: The New Lower Bound of Programming Contests
- K. Diks et al: Looking for a Challenge? The Ultimate Problem Set from the University of Warsaw Programming Competitions
- T. H. Cormen, C. E. Leiserson, R. L. Rivest và C. Stein: Introduction to Algorithms
- J. Kleinberg and É. Tardos: Algorithm Design
- S. S. Skiena: The Algorithm Design Manual
Một vài Website thú vị cho lập trình thi đấu:
- Codeforces: Một website khỏi phải bàn cho những người yêu thích lập trình thi đấu, ở đây có tất cả các bài tập bạn cần tìm, forum, contest để cọ sát,…
- TopCoder: Một trong những website nổi tiếng nhất về lập trình thi đấu, website gồm 4 mảng chính: thiết kế, lập trình, data science và lập trình thi đấu
- Google Code Jam: Đây là một website hết sức thú vị của một cuộc thi lập trình tới từ Google, nơi những lập trình viên hàng đầu cạnh tranh nhau chiếc vé tới cái ghế tại Google.
- Ngoài ra còn rất nhiều các website khác như Codechief, Codelearn,…
III. Các kỳ thi
1. Học sinh giỏi Tin Học cấp quốc gia
Cái tên đã nói lên tất cả, đây là cuộc thi uy tín nhất về lập trình thi đấu cho học sinh cấp 3 do Bộ Giáo Dục & Đào Tạo tổ chức. Cuộc thi diễn ra trong 2 ngày với tổng số điểm là 40. Các thí sinh được phân chia thành các giải Nhất, Nhì, Ba, Khuyến Khích, top 40 thí sinh sẽ được tham gia vào vòng TST (Team Selection Test) để chọn ra các bạn tham dự kì thi Olympic Tin Học châu Á – Thái Bình Dương (APIO) , những thí sinh rank cao nhất sẽ được chọn để thi IOI (Olympic Tin Học Quốc tế)
2. IOI
Olympic Tin học Quốc tế (IOI) là một cuộc thi thường niên dành cho học sinh THPT. Mỗi quốc gia được phép cử một nhóm bốn học sinh tham gia cuộc thi. Thường có khoảng 300 thí sinh tham gia từ 80 Quốc gia. IOI bao gồm hai ngày thi kéo dài năm giờ. Trong cả hai ngày thi, thí sinh tham gia được yêu cầu giải quyết ba bài toán có độ khó khác nhau. Các bài toán được chia thành các subtask, mỗi subtask có một số điểm được ấn định. Thậm chí nếu các thí sinh được chia thành các đội, họ thi đấu với tư cách cá nhân. Trước IOI, nhiều cuộc thi khu vực được tổ chức, chẳng hạn như Olympic Baltic về Tin học (BOI), Olympic Tin học Trung Âu (CEOI) và Olympic Tin Học Châu Á – Thái Bình Dương (APIO).
3. ICPC
International Collegiate Programming Contest (ICPC) là cuộc thi lập trình hàng năm dành cho sinh viên đại học. Mỗi đội trong cuộc thi bao gồm ba sinh viên, và không giống như trong IOI, các sinh viên làm việc cùng nhau; chỉ có một máy tính có sẵn cho mỗi đội. ICPC bao gồm một số giai đoạn và cuối cùng các đội giỏi nhất được mời tham gia Chung kết Thế giới. Trong khi có hàng chục nghìn người tham gia cuộc thi, chỉ có một lượng nhỏ các thí sinh có thể có mặt tại vị trí cao trên bảng xếp hạng. Trong mỗi cuộc thi ICPC, các đội có 5 giờ thời gian để giải quyết khoảng 10 các bài toán thuật toán. Giải pháp cho một vấn đề chỉ được chấp nhận nếu nó giải quyết được tất cả các test một cách hiệu quả.
4. Các cuộc thi online
Bên cạnh các cuộc thi mang tính chính thức nêu trên, thì cũng còn rất nhiều các kì thi được tổ chức hàng tuần, chẳng hạn như Div1, Div2 của Codeforces, Hackerrank, Topcoder. Thậm chí nhiều công ty cũng có cuộc thi lập tình của riêng mình như Facebook Hacker Cup, Google CodeJam, Yandex Algorithm,…
IV. Lộ trình học và cách học
Về việc học, ở lập trình thi đấu thường đề cao sự “cày cuốc” – tức làm nhiều bài tập nhất có thể theo các dạng để nâng cao trình độ, dưới đây là một lộ trình học cơ bản cho người mới bắt đầu.
1. Nhập môn
- Các khái niệm về lập trình;
- Chọn ngôn ngữ lập trình bản thân sẽ sử dụng (Python, C++,…);
- Toán học;
- Tư duy lập trình;
- Độ phức tạp thuật toán;
- Sắp xếp, cấu trúc dữ liệu (Stack, Queue,…);
- Trâu, tham lam;
- Quy hoạch động;
- Truy vấn.
2. Đồ thị
- Các khái niệm cơ bản của đồ thị;
- Đường đi ngắn nhất;
- DFS;
- BFS;
- Tìm kiếm đường đi;
- Thuật toán cây;
- Đồ thị có hướng;
- Đồ thị liên thông;
- Thuật toán Kosaraju;
- Thuật toán Kruskal;
- Thuật toán PRIM;
- Thuật toán Dijkstra,…
3. Kiến thức nâng cao
Lý thuyết đại số, lý thuyết trò chơi, xâu kí tự,…
V. Kết luận
Học lập trình thi đấu là quá trình đòi hỏi sự tập trung và kiên trì, trên đây là tóm tắt kiến thức về lập trình thi đấu dựa theo kinh nghiệm của bản thân, rất mong được các bạn độc giả góp ý cho bài viết của mình!
*** Đôi nét về tác giả – Học viên Vàng Đức Hoàng, học sinh THPT chuyên Hà Giang
✅ Giải Nhất Hội thi Tin Học Trẻ cấp tỉnh năm học 2018-2019
✅ Giải Nhất Học Sinh Giỏi môn Tin Học cấp tỉnh vượt cấp lớp 9 năm học 2018-2019
✅ Giải Nhất Học Sinh Giỏi môn Tin Học cấp tỉnh vượt cấp lớp 9 năm học 2019-2020
✅ Giải Nhất Học Sinh Giỏi môn Tin Học cấp thành phố vượt cấp lớp 9 năm học 2019-2020
✅ Giải Nhì Học sinh giỏi môn Tin Học lớp 9 cấp tỉnh năm học 2020-2021
✅ Giải Nhì Học Sinh Giỏi môn Tin Học vượt cấp lớp 12 năm học 2021-2022
✅ Giải Ba Hội thi Tin Học Trẻ Toàn Quốc 2021
14,578 total views, 3 views today