Competitive Programming

Viết ít dòng, hồi tưởng về những gì mình đã làm trên con đường Competitive Programming.  (Warning: wall of text).

Một chút background của mình: mình không học chuyên, mình chỉ luyện CP cho vui. Nhưng mà trong hơn 5 năm qua mình đã (hoặc suýt) làm được vài chuyện cũng to. Cuộc vui nào cũng có hồi kết, mình cũng tìm được niềm vui mới với NLP. Vậy nên post này coi như giã từ sự nghiệp Competitive Programming.

Sẵn đây mention lại repository code CP mình luyện từ 2018 đến giờ, cũng như link các tài liệu training CP mình nhặt nhạnh được trong suốt quá trình train mà có thể bạn sẽ cảm thấy có ích.

Bắt đầu nào.

Khởi động: đội tuyển

Hồi đó mình học ở trường làng nên chẳng biết Học Sinh Giỏi Tin là Competitive Programming (kind of) đâu, chỉ nghĩ là giống như đi thi nghề phổ thông: vào làm Word, Excel rồi 10 10 10 là pass. 

Giữa kì 1 năm lớp 10 (2016) mình được gọi vào đội tuyển. Cô Kim Ngân gọi mình và 1 classmate vào vì có tư duy lập trình. Đội tuyển lúc đó do cô Quỳnh Dao coach, xài Pascal. Mình còn nhớ buổi đầu vào chỉ ngồi code 10 bài code cơ bản rồi về. Lúc đấy mình đã có base coding từ trước nên làm trong 1s rồi đòi thêm bài mới làm, oách vl :/

Fact: Hồi đó crush học đội tuyển cùng mình, nhờ vậy mà mình lại có thêm động lực lên tuyển. 

Nhưng mà đội tuyển nào cũng vậy, càng về sau kiến thức càng nhiều. Kiến thức thì cô Dao xoáy sâu vào backtracking và dynamic programming - 2 mảng mà sau này mình hối hận vl vì hồi đó không train kĩ. Thời gian thì team tăng giờ train, mà lại tăng trái buổi. Thành ra có những hôm mình đi học đội tuyển từ 7h sáng tới 12h trưa, mà 12h30 là vào lớp chiều. Chính vì vậy nên các bạn cũng lần lượt bỏ đi hết. Roommate đại học của mình hồi đó cũng là teammate đội tuyển, sau switch sang đội Lý vì Tin khoai quá. Crush mình cũng bỏ đi mất luôn. Team còn lại có 2 mạng, là mình và anh bạn Thanh Sang (@tsdocode on GitHub - giờ pro vl bên mảng AI).

Mùa 1: KK (HSG Bến Tre 2018).

Mình và anh bạn Sang vào train tiếp đến tầm tháng 10/2017 thì cô Dao đi học, giao quyền coach cho thầy Thiện và thầy này freestyle. Nghĩa là từ đây những gì mình được học hầu hết cũng chỉ cho vui, còn làm bài thì phang phương pháp nào cũng được, miễn là nó chạy.

Tuy vậy mình cũng được học phép loang (DFS), được học greedy. Ngoài ra mình còn solve được vài task mr Thiện giao, nên cũng gọi là oách. Cũng dạo này mình được cái kim bài miễn tử HSG, nên cúp học thể dục đi train tuyển thường xuyên. Bạn bè thì đánh bóng nhảy xa, mình thì đánh bàn phím nhảy khủng long.

Có cái kỉ niệm nho nhỏ giai đoạn này, là trận Việt Nam đá với Qatar năm 2018. Mình với Sang đang cúp thể dục train tuyển, hè nhau rủ thầy coi đá banh khỏi học. Cuối cùng thầy cười hề hề bảo "thầy hông có coi đá banh". Thế là 2 thằng train sml đến 5 rưỡi chiều :/

Tháng 2/2018 tụi mình vào thực chiến, đề bài dễ (theo đánh giá bây giờ :/) - task 1 là tìm dãy cell caro dài nhất, task 2 là đếm số siêu nguyên tố, task 3 là đếm số lần xuất hiện của matrix nhỏ trong 1 matrix lớn. Mình solve task 2 ẩu, bỏ task 1 và solve 1 subtask của task 3. Thế mà ra vẫn được 5/20 - Khuyến khích.

Mùa 1.5: Tạch ĐTQG (2018).

Mình cứ tưởng thế là xong, tập trung ôn thi đại học. Thế quái nào ngay ngày đầu nhập học cô Ngân gọi mình, bảo chuẩn bị để 2 ngày nữa thi chọn đội tuyển HSGQG. Thế là quick rush, nhưng mà kiến thức mình có lúc đó quá sơ sài, cũng không có gì gọi là đặc sắc, không biết nhiều thuật + không biết cách ứng dụng mấy thuật đã học. Đề bài có task 1 là bài này, task 2 là sinh hoán vị và task 3 là Travelling Salesman Problem. Tất nhiên là mình tạch :/

Đợt này cô Ngân bổ sung thêm 2 em lớp 10 là Chí Tâm và Thành Văn. Mình, Sang và Tâm tạch nhưng Văn thì pass. Mình cũng cảm thấy loser, nên có 1 khoảng thời gian mình mất động lực theo tin học.

Mùa 2: Giải 3 (HSG Bến Tre 2019).

Được ít hôm thì cô Dao về và triệu tập đội tuyển. Mình và Sang thì xin train online vì đang dành nhiều thời gian ôn thi đại học nên cô cũng đồng ý. Lúc này chọn train team tiếp là khá mạo hiểm, vì từ lúc tạch ĐTQG thì mình đã xác định là kiến thức tin học có thể dùng về sau, nhưng không phải bây giờ, nên không train nữa.

Đợt đó xin được cô Dao quyển Lý thuyết đồ thị về cày. Ít hôm sau cô cho thêm quyển bồi dưỡng HSG tin về đọc. Tuy vậy khúc này tự dưng mình lại nổi hứng cày nghiêm túc, nên lên mạng và tìm được quyển DSAP của thầy Lê Minh Hoàng. Mình cày từ chương Đồ thị về sau, đến Maxflow thì mình switch sang học Dynamic Programming kiểu nửa hiểu nửa học vẹt, vì còn có 2 3 tháng nữa thi mà mình mới động đến DP một cách nghiêm túc :/

Khúc sau thì mình cũng có gửi solution đề mẫu cho cô Dao xem thử, AC được 2 3 bài gì đó cũng vui. Xong tự tin hơn thì giải bài trên SPOJ và cũng AC được kha khá. Thế là mình đủ tự tin đi vào thi. Tháng 2/2019 mình, Văn, Tâm, Sang bước vào thi. Đề task 1 là tìm đường đi trên grid, task 2 là bài greedy nhưng nhiều case vl, task 3 là bài này. Mình AC bài 1, solve ẩu bài 2, solve ẩu luôn bài 3. May quá vẫn được 10/20 - giải 3. Team có Văn được giải 1, Tâm với Sang được KK.

Có được cái giải 3, mình tự tin đi tiếp quãng đường còn lại. Mình pass đại học, vào HCMUS.

Mùa 3: Không có giải (Olympic tin học HCMUS 2019).

Từ lúc vào HCMUS mình đã tự cao vl, nghĩ mình cũng thuộc "tầng lớp có giải". Mình mạnh mồm nổ vè Big-O trong group chat, mạnh mồm đề xuất thuật với roommates, ..etc.

Vài lời cảnh báo đầu tiên đến từ Codewar 2019 - HCMUS. 5 task mà mình giải được có 4, trong room lúc đó có anh Nguyễn Hy Hoài Lâm và Lê Duy Thức - 2 ông pro vl làm xong trong < 5 phút xong ngồi mở tank.io chơi. Ngồi cạnh mình còn có Nguyễn Đức Hạnh - giải 3 HSGQG. Vì vậy mình đã bắt đầu ngộp và tự ngồi ôn lại kiến thức, để dành cho Olympic tin học HCMUS.

Mình dự thi khối không chuyên, và dù là đề khá dễ nhưng mình lại dùng hướng greedy + naive cho cả 5 problems - kết quả không ngoài dự đoán là tạch hoàn toàn. Đợt này classmate là Nguyệt lại được giải 3 KC, nên mình lại thêm áp lực vl.

Sau Olympic tin học thì mình có biết được Duy Tiến và Nhật Đăng. Đoạn sau sẽ có mặt của 2 ông này nhiều.

Mùa 4: Không có giải (Olympic tin học HCMUS 2020).

Mùa này thì học hành nghiêm túc hơn, hoàn chỉnh hơn. Mình cày lại sách thầy Hoàng, đọc quyển cpbook của thầy Steven Halim. Mình học thêm hashmap, học thêm nhiều cấu trúc cây, cày nhiều DP hơn, join nhiều contest trên Codeforces, Codechef. Dạo này là mình post bài trên blog nhiều nhất, nhiều nhất là trong lúc dịch không có gì làm lại lôi code ra cày.

Đợt này thi thì có Tiến chung bảng chuyên Tin. Kết quả là mình xếp hạng 28/89 (nhưng không có giải :/), Tiến được khuyến khích. Tuy không có giải nhưng mình vẫn vui, là ít ra mình vẫn nằm ở nửa trên bảng, thua KK có 11 điểm :/

Mùa 5: KK (ACM-ICPC Southern Provincial 2021).

Tính là sau mùa Olympic 2020 là mình dự nốt cái Olympic 2021 rồi retire. Thế mà Tiến với Đăng rủ train team ICPC luôn cho máu. 3 thằng tính lập team từ 2019 rồi, nhưng mà dịch đến rồi deadline các thứ nên lại không train được. Team chủ yếu train mấy tuần cuối, solve bài codeforces với tìm bài ở mấy site khác làm.

Trước ngày thi thì vì dịch mà trường quyết định dùng kết quả warmup pick team dự vòng Southern cmnl - tự dưng lại thấy khả quan vì team rank 15 trong lúc warmup. Đến lúc vào thật thì solve được 6 bài - hầu như là Tiến solve hết còn mình với Đăng ngồi tấu hài. Mình còn cài hỏng cái thuật DP mà tới tay Tiến thì mới AC trong 10 phút cuối :/

Chung cuộc thì team được KK - rank 61.

Lời cuối

Vẫn như mọi khi, đây là kỉ niệm và trải nghiệm của mình. Vui có, buồn có, thất bại có, thành công có. Chia sẻ vậy để nhẹ lòng tí, sau này có khi nhìn vào lại nhớ :D

Ít dòng chia sẻ cho các bạn thích CP hoặc rộng hơn là thích tin:

Thứ nhất, học cho chắc. Vào một tối năm 3 đại học mình phải giở quyển giáo khoa chuyên Tin để chép lại đúng cái trang mà năm 17 tuổi mình bỏ qua. Đừng hời hợt quá để sau này lại tiếc.

Thứ hai, không có gì là vô bổ. Tất cả những thứ mình học thời đội tuyển trở thành cái nền cho những gì mình học sau này. Từ những bài tập nhập môn lập trình cho đến lúc mình ngồi trên lab đề xuất approach mới cho khóa luận, tất cả đều bất đầu từ mấy dòng trong sách mình đọc năm 17 tuổi.

Cuối cùng, không hối hận. Một ngày nào đó trong tương lai mình sẽ hối hận vì những gì mình đã và đang làm, nhưng rất vui là ngày đó không phải hôm nay.

Nói thế cũng có nghĩa, từ nay về sau mình sẽ không post bài về CP lên đây thường xuyên nữa. Nếu tự dưng mình thích ăn mày quá khứ và mở codeforces lên giải bài, lúc đấy mình sẽ post. Còn giờ thì đến đây thôi. 

Happy coding :D