Hi, mình là Kriz_Wu (hoặc Lamu) đến từ HCMUS, team HCMUS-AtCoder.
Mình vừa trải qua một kì ICPC đáng nhớ cùng với team tại ICPC World Finals tại Baku. Vì một thành viên trong team chuyển trường nên team sẽ rã vào mùa sau. Mình muốn chia sẻ thêm về hành trình của team mình trong năm vừa qua và chiến thuật của team.
ICPC là gì
International Collegiate Programming Contest (ICPC) là kì thi lập trình thi đấu dành cho bậc đại học lớn nhất thế giới. Một đội gồm 3 thành viên và 1 máy tính phải giải các bài toán (~12-14 bài) trong vòng 5 tiếng. Kì thi tập trung vào tư duy thuật toán, cài đặt và khả năng làm việc nhóm.
Giới thiệu thành viên
HCMUS-AtCoder gồm 3 thành viên Kriz_Wu (Lamu, năm 2), DeMen100ns (DeMen, năm 2) và Pannda (Ann, năm 1).
Kriz_Wu
https://codeforces.com/profile/Kriz_Wu
Kinh nghiệm 6 năm CP. Nhất thủ khoa VOI (2023). Thế mạnh của mình là ở các bài toán optimization, greedy, hình học, tree, game theory, khả năng nghĩ và phản ứng nhanh, rà bug và đưa ra edge case hộ người khác và toàn diện ở hầu hết các mảng (trừ các mảng mình yếu). Điểm yếu của mình là ở các bài counting, math, number theory, random và heuristics.
Pannda
https://codeforces.com/profile/Ann
Nhì VOI + APIO 2024. Điểm mạnh là DS, graph, tree. Điểm yếu là số học, geometry, dần dần ở trong team thì yếu thêm combinatorics/probability tại được gánh rồi. Role: ngồi nhìn du nhập đạo. Quirk: hay typo.
DeMen100ns
https://codeforces.com/profile/DeMen100ns
Nhì VOI + APIO 2023. Hiểu biết hầu hết mọi thuật toán ở mức tương đối. Điểm yếu là geometry (mù hẳn) và cây (nhẹ). Điểm mạnh là combin/number theory/algebraic problem, heuristic/optimization problem. Đôi khi cũng đóng vai trò là người tính toán đpt, bách khoa toàn thư thuật toán của team.
Trước khi lập team
Lamu và DeMen tham gia ICPC năm trước dưới team HCMUS-PeTalNyKing cùng với Danh (Đồng IMO). Sau vòng Super Regional (APAC24) thì team rã vì Danh chuyển trường.
Trước khi thi APAC, có chút lưỡng lự sẽ không teamup với DeMen cho năm sau nữa (thấy gà quá, còn không nghĩ tới sẽ đi WF). Cơ bản vì cảm giác không hợp với mình cũng không đặt mục tiêu cao với ICPC. Nhưng sau khi thi xong thì vẫn quyết định đâm đầu thêm 1 năm nữa. Nên suýt nữa thì HCMUS-AtCoder sẽ không có mình mà là một ai đó khác :v.
Lamu và DeMen scout được Ann (lúc đó là đàn em cùng trường PTNK, vừa mới đậu TST/APIO) và quyết định teamup tạo thành đội hình như bây giờ. Vì từng gặp nhau từ trước nên dễ làm quen với nhau hơn;
Những buổi train đầu tiên
Team bắt đầu train từ hè 2024, lúc đấy khá rảnh nên team virt liên tục để tăng chemistry.
Vạn sự khởi đầu nan. Các virtuals đầu tiên của team, theo mình đánh giá, hơi “thảm họa”. 3 người sẽ chọn ra 3 bài, mỗi người nghĩ 1 bài, cuối cùng ai ra bài nào thì giành máy vào code. Lúc đó thì khá là “luật rừng”.
Sau vài buổi như vậy, tụi mình cũng xác định được strength và weakness của nhau:
- Ann code khỏe nên gần như thành “máy code” của team lúc đó, chúa imple. Ann khá giỏi trong các bài cần tư duy, observations, thường hay đưa ra một số lemma cho các bài toán.
- DeMen thì có nền toán vững, kết hợp với một số kiến thức sâu về combinatorics, polynomial, number theory.
- Lamu thì giỏi greedy, game, graph flow, tree dp, computational geometry hoặc các bài có idea “lạ” nên sẽ cover phần đó. Mình có khả năng thích ứng và rà bug hộ người khác nên sẽ support nếu có ai đó đang bug.
Từ đó thì team có thêm các interaction có ý nghĩa hơn:
- Các bài trung bình khó phải được một người khác “confirm thuật” thì mới được vào code
- Role “monitor” - 2 người cài cùng lúc, một người cài, một người rà bug live.
- Dựa vào tag để delegate bài cho hợp lý
- Quản lý progress / queue trong contest.
Quản lý
Một thứ khá mởi mẻ so với các team mình từng tham gia. Team mình luôn có một mindset phải quản lý tất cả mọi thứ lại, để sau này có data để phân tích.
Inspired từ coach GATECH (Chenjb), team sẽ log lại mọi buổi virtual các thông tin như bài nào được giải, ai giải / cài bài đó.
Có 2 cột có label thành viên, bên trái là solver, bên phải là implementer. Nhiều người có thể solve, implement một bài.
The start
Do có mấy buổi virtual quá tệ, team quyết định họp bàn chiến lược và tạo ra một bộ formal rule ngay trước vòng National.
Một điều khá khác biệt so với các team ICPC của mình trước đây.
Start of the Strategy (Strat AtCoder 1.1)
Goals
Trước khi các kì thi diễn ra, team đều sẽ đặt ra mục tiêu và baseline cần đạt cho kì thi đó:
- Baseline: thứ mình chắc chắn phải làm được trong bắt cứ hoàn cảnh nào.
- Goal: thứ mình muốn đạt được, và có khả năng đạt được trong hoàn cảnh tốt nhất.
Quy ước
Bài sẽ được phần thành 3 loại chính:
(1) - Bài *800, bài nghĩ trong 10’, cài trong 15’
(2) - Bài nghĩ trong 30’, cài trong 30’
(3) - Nhiều người làm chung thì <= 90ph, cần sự phối hợp của nhiều người
Thời gian
Chia làm 3 phase:
Phase 1: Opening [0h, 2h)
- Chia problemset thành 3 phần, chia cho mỗi người.
- Đọc đề phần mình.
- “Skim and scan”, detect bài (1) và gắn tag. Có thể dựa vào tag để delegate bài cho người khác.
- Nếu một người đang trên máy và chưa đọc hết set bài của họ, đẩy các bài chưa đọc cho 2 teammate còn lại.
PHASE 1 GOAL:
- AC hết (1)
- (2) và (3) phải được đọc bởi ít nhất một người.
- Push (2), (3) vào queue càng nhiều càng tốt.Phase 2: Mid phase [2h, 4h)
- Các bài (2) và (3) phải được đọc bởi mọi thành viên của team.
- Nếu queue >= 3 bài, cần có 2 người pop bài, 1 trên máy, 1 code giấy.
- Nếu queue <= 2 bài, sẽ có một người pop bài, (hoặc 2 nếu bài được pop có độ khó (3)).
FINAL PHASE 2 GOAL:
- Push all (2) vào queue
- Cố pop hết các bài (2) trước freeze
- Cố push nhiều (3) vào queue nhất
- Các bài chưa giải được phải được một người nghĩ trong 20-30'Phase 3: Freezing phase [4h, 5h)
- Pop mọi bài trong queue, giải phóng người
- Nếu queue >= 2 bài, toàn team dồn lực debug, pop queue
- Nếu queue = 1 bài, chia ra 1-2 hoặc 3-0 (cài - nghĩ)
- Ở phase này, các bài loại (3) phải được nghĩ bởi ít nhất 2 người
- Trường hợp đặc biệt:
- Nếu ăn pen và thua 1-2 bài, ưu tiên debug kỹ trước khi nộp, giữ lợi thế pen
- Nếu cần AC 2-3 bài, có thể break luật 3.4
Other notes
Khi gặp bug:
- Đọc lại đề bài :)))
- Nếu queue còn bài: 2.1. In code 2.2. Code bài tiếp theo trong lúc bài được debug 2.3. Khi máy trống thì chạy vào stress 2.4. Khi ra được bug: 2.4.1. Nếu bug dễ -> “cho tui xin 5s” 2.4.2. Nếu bug khó (sửa nhiều), ưu tiên làm sau bài đang cài. (nếu quá sai thì phải quay lại quy trình code giấy)
- Nếu queue hết bài: 3.1. Debug mắt (should be 5-10 mins) 3.2. Nếu không ra -> stress
Hết cứu quá thì đi cầu cứu viện :v
Principles:
- Penalty luôn quan trọng
- Hệ thống các bài để quản lý
- Thử một vài test tay trước khi nộp!!!
- If you keep getting WA on a problem, let it be for a while and try to solve another problem. Phần lớn thời gian của team sẽ nằm trong nhà vệ sinh
- Do not hesitate to tourist, bài toàn <=15ph
- Use good judgement to cầu cứu. Chỉ cầu cứu sau khi đã tự debug một mình
Start of the Traditions
Nếu mọi người để ý thì team mình mang khá nhiều mascot đi thi. Traditions này chắc là bắt đầu từ mình. Ở vòng national mình muốn mang con gì đó lên nhìn cho đẹp nên mang thêm đèn con gà này theo, thế là nó đã thành linh vật đầu tiên của team.
Con gà đã đồng hành với mình (và team mình) trong suốt tất cả các kì thi icpc,
Từ đó, sau một khoảng thời gian team lại tậu thêm vài mascot nữa.
Nhờ có những con fumo nên team cũng được dịp giao lưu với các team khác.
(Friendships with Gyerantak, N-Dimensional Sum, 7 is our favourite number and NYCU_MyGO!!!)
ICPC National
Như đã bàn từ trước, Ann template, Lamu queue và DeMen chia bài. Các bài được chia đều cho DeMen(ABCD) - Ann(EFGH) - Lamu (IJKL).
DeMen đọc và có thuật cho bài Aa (AC A 11’). Vào tốn 5 đấm, mình nhớ là ngộ nhận thuật hơi nhiều. Biến team mình thành top các team penalty cao nhất cho bài A (bài dễ nhất). Sau đóm DeMen đã sửa lỗi bằng 1 đấm AC bài D (AC D 17’).
Sau đó An vào cài H (AC H 20’) và mình vào cài K (AC K 28’, 2 đấm). Sau bài K, mình thấy đã có người ac I nên nhảy qua bàn bài đó chung với DeMen (AC I 54’).
Sau bài I, team chính thức bước vào phase 2. Mọi người bắt đầu đưa đẩy bài cho nhau, chia người ra để insight các bài còn lại.
Nhìn vào standing lúc đó có F và G nên tụi mình cũng tập trung hơn vào 2 bài đó. Ann ra công thức bài F từ đầu giờ nhưng không biết cách cài sao cho nhanh. May có DeMen phụ để optimize phần đấy (AC F 133’). Trong lúc đó, mình với Ann cũng bàn với nhau một chút bài G và ra được idea. Ann đẩy cho mình phần cài đặt để chạy qua F với DeMen (AC G 173’).
Sau khi nháp tay ra vài trường hợp, mình propose một thuật cho Ann và nhờ Ann code trâu để check trâu. Sau đó thì mình cảm giác tự làm được nên tự đảm nhiệm bài L, đẩy 2 người kia qua các bài còn lại. (AC L 220’, 2nd solve)
Sau bài L, team quyết định đổi qua phase 3. Nhìn về standing lúc đó, có các bài B, C, E, J (B với C có vẻ dễ hơn). Team ngồi họp lại để chọn một bài all-in. Và thế là tụi mình quyết định chọn bài E, một bài planar graph + geometry. Dù đã ra được idea cốt lõi nhưng việc cài đặt và xử lý trên planar graph, chưa ai trong team từng cài nên team đã dành 80’ còn lại suffer trong việc cài đặt và không AC. Kết thúc với 8 bài, top 2 National.
Đây là lần đầu team áp dụng strat và cảm thấy có hiệu quả khá rõ rêt, mọi người bắt đầu ăn ý với nhau hơn và có sự tương tác nhiều hơn. Đây là bước đệm cho sự phát triển của strat AtCoder.
Jakarta trip
Day 0: Travel day
Lần đầu tiên team được ra nước ngoài thi nên khá háo hức.
Khách sạn khá nhiều tiện nghi. Họ có bàn bida, bóng bàn, bể bơi, sân bóng rổ, sân bóng đá. Sau khi nhận phòng mình với Ann ra test phòng gym.
Tối ăn ở Tsuka Ramen. Quán không ai biết nói tiếng anh nên cần google dịch. Ramen phiên bản Indo và ăn khá ngon, mình reccommend các team nếu có đi thi ở Jakarta có thể ghé qua.
Day 1: Rehearsal day
First impression là trường khá to. Trong trường còn có thang cuốn để di chuyển.
Bên Indo người ta tổ chức khá chuyên nghiệp.
Vì là team nước ngoài nên sẽ có một bạn escort dẫn đi trong suốt quá trình thi. Bạn escort team mình khá nice, bạn còn dẫn bọn mình vào thư viện trường Binus.
Vào lúc team photo, Ann suggest làm cái gì đó “lạ”. Idea ban đầu là làm hình ngôi sao, tính một hồi thì không đủ người nên đổi thành hình tam giác cho đơn giản.
Khu vực thi được tách thành các phòng máy. Phòng có style khá giống i52 ở HCMUS nên tạo cảm giác khá quen thuộc. Trong kì thi không cho xài CodeBlocks, một IDE quen thuộc với team mình nên xài vscode khá gượng.
Trái với kì Regional trước đó, tâm lý trước khi thi của mình khá thoải mái. Vì mình tin đồng đội của mình và tự tin phong độ của team lúc đó. Mọi thứ khá thuận lợi để bước vào kì thi.
Day 2: Contest day
Trong lúc ăn sáng, Ann với mình uống thử lon cold brew Starbuck mới mua tối hôm trước. Lúc uống thấy có vị lạ lạ, thế là cả 2 đau bụng trước khi thi :<.
Trước lúc thi Ann rủ mình đi hít đất cho nóng người. Từ buổi đó, hít đất trở thành truyền thống của team mình luôn.
Bắt đầu kì thi, dựa vào strat, mình viết tờ queue, Ann vào máy viết template.cpp, DeMen thì ngồi tách đề. Mình được phân set bài J-K-L-M.
Mình đọc M vào và ra được idea. Trong lúc nháp M thì Triệu vào máy và AC A (13’). Sau đó mình chạy vào cài M. Do đã nháp kĩ nên mình cài khá nhanh, AC M(24’). Lần đầu first solve trong một kì thi.
Sau đó, Ann lấy máy và cài C. Do các bài đầu dễ nên team speed qua khá nhanh (AC C 33’).
Mình đọc xong J,K,L và không biết làm bài nào. Qua đọc I của Ann và ac I (61’).
Tại đây có thể nói là đã kết thúc phase 1, mọi người bắt đầu vào phase 2, trao đổi bài với nhau nhiều hơn.
Mình có ra idea F nhưng idea sai. Bài F nhận thấy cũng khá căng (loại(3) và hiện chưa có ai làm) nên tạm thời skip.
Sau đó, do thấy std_abs ac B nên mình chạy qua với Triệu đấm B, trong lúc đó thì an cài H. (AC B 147’, AC H 139’).
Sau đó thì mình quay lại sống mái tiếp với bài F. Nhưng vẫn chưa ra được gì cụ thể. Ann có nghĩ ra được một hướng cho G nên Ann với Triệu invest vào G. Còn mình tách 2-1 và được đẩy bài E. Mình hơi bất ngờ với E vì là một bài dễ nhưng lại bị hầu hết team bỏ qua. Team mình sau đó đều cài trơn tru cả hai bài. (AC G 215’, AC E 253’).
Sau khi ac E thì mình lại tiếp tục với F. Với bản thân mình thì mình đã nghĩ F được 1-2h rồi. Do là phase cuối nên Triệu với Ann vào và support mình F luôn. Tụi mình chia nhau, một người code trâu (DeMen), 1 người tạo edge case (Ann) và mình ngồi nghĩ lại idea bài F. Sau một hồi thì mình mới thấy được pattern của bài. Dù chưa được chứng minh chặt chẽ nhưng lúc đầy gần hết giờ rồi nên cứ “thử” và may mắn AC F (288’), được một pha hú hét khắp phòng.
Trong contest, tụi mình có dùng trick mà team hay nói vui là “trick bài L”. Nhìn thấy bài L là một bài khá khó và rối, tụi mình nộp 2 đấm printf(“Hello World”), một trước freeze, một sau freeze để các team khác đổ xô đi làm bài đó ;).
Khúc cuối còn dư 15-20’, team ngồi nghĩ J với L nhưng không có tiến triển gì mấy. Team mình dứng lại với 9 bài và 1273 penalty.
Kết quả cuối cùng team được top 3 Jakarta.
Dù không được kết quả mong đợi nhưng mình thấy team mình đã cố hết sức. Khúc sau Ann có nghĩ ra J nữa và mới biết J cũng là một bài dễ … Đây cũng là lần đầu team mình được gold medal nên cũng khá vui.
Vì first solve nên còn được thêm 3 cái ly
Sau bế mạc, ban tổ chức cho ăn tối tại sảnh và chuẩn bị xe đưa các team về.
Quà mình tặng cho bạn escort.
Sau khi về thì mình rủ Ann với DeMen đi dạo chơi Jakarta. Tụi mình bắt xe ra một cái mall khá to.
Có một sảnh của mall tổ chức fes pokemon nhìn khá hay.
Cảnh Jakarta về đêm
Do lúc đó muộn nên mall chuẩn bị đóng cửa, không mua được gì. Khúc sau tụi mình còn khá suffer với việc đặt xe vì mall như mê cung và tài xế không biết nói tiếng anh. Kết thúc chuyến đi.
Day 3: Excursion Departure day
Thật ra ngày 3 là ngày excursion nhưng vé tụi mình bay sáng hôm đó nên không đi được. Mình được nghe bảo là đi Disneyland bến đó. Khá tiếc vì không đi được.
Kết thúc chuyển đi, bọn mình bàn với nhau chuyến lược để chuẩn bị cho vòng Regional tiếp theo tại Hanoi.