Chuyện là, ngài ấy rủ mình virtual một contest 5 tiếng.

Giới thiệu

Khu vực Bắc Mỹ có tổng cộng 11 kỳ thi Regional khác nhau. Khác với khu vực Đông Nam Á – Thái Bình Dương¹ với mỗi kỳ thi Regional tổ chức một thời điểm khác nhau, 11 Regionals này được gộp thành 4 miền (division): miền Đông, miền Tây, miền Nam, và miền Trung; các Regionals cùng miền sẽ được tổ chức cùng một ngày và thi chung một bộ đề, nhưng cơ chế chọn đội đi tiếp vào NA Championship hiển nhiên vẫn độc lập với nhau.

Miền Đông của khu vực Bắc Mỹ có ba điểm thi: Đông Bắc, Đông Trung, và khu vực Ba Bang² 🐧. Nơi đây có sự góp mặt của rất nhiều trường lớn như: Đông Bắc có MIT – đội vô địch toàn miền, Harvard; Đông Trung có Carnegie Mellon, Waterloo, Toronto, Purdue; GNY thì có Princeton, Cornell, Yale.

Bạn nào muốn virtual kèm bảng điểm gốc thì click vào đây (chưa bao gồm khu Greater New York).
Nào, bắt tay vào code thôi.

Diễn biến

Rank 27/264³	A	B	C	D	E	F	G	H	I	J	K	L
8 bài	+	+		+	+6	+1	+2		+1		+1
985 phút	6	103		21	298	13	54		70		200

[H-2] Mirror gốc nằm ở trên Kattis, nhưng hệ thống chấm bài này không hề có cơ chế virtual. Vì có bạn làm chung nên mình quyết định bỏ ra 15 phút để tổng hợp bảng điểm rồi đẩy lên VJudge, virtual cho nó giống thật nhất có thể. Mỗi tội là VJudge không có chức năng đóng băng bảng điểm, nên 1 tiếng cuối bảng điểm vẫn tiếp tục cập nhật.

Hai tiếng trơn tru đầu tiên

[0:00] Bắt đầu từ bài A. Lúc này thì mình đang nghe hơn nửa quyển For the beginning, L của anh Thành ~~Loot~~Luke.

Bài A: Có ba cỡ hộp bánh Pizza: hộp S 6 miếng, hộp M 8 miếng, hộp L 12 miếng. Cho \(n\) hộp bánh Pizza, mỗi hộp có cỡ bánh và số miếng còn thừa khác nhau. Ta cần gom các miếng thừa từ hộp bánh cùng cỡ lại với nhau, hỏi cần ít nhất bao nhiêu hộp?

[0:06] AC bài A.

Bài F: Cho dãy \(1, 2, 2\frac{1}{2}, 3, \frac{1}{3}, \frac{2}{3}, 4, 4\frac{1}{4}, 4\frac{1}{2}, 4\frac{3}{4}, 5, \dots\); nói cách khác là \(\bigcup\limits_{i=1} \bigcup\limits_{j=0}^{i-1} \left\{i + \frac{j}{i}\right\}\).
Tìm số thứ \(n\) trong dãy, phân số phải viết dưới dạng tối giản.

[0:11] WA bài F vì sai trường hợp \(n=1\), nhỡ in ra thành 1 0/1 thay vì chỉ 1.
[0:13] AC bài F.

Bài D: Cho một cuộc bầu cử theo format Instant-runoff:

Mỗi lá phiếu là một hoán vị, ban đầu chỉ tính mỗi lá phiếu cho người được xếp trên cùng;

Người giành được hơn 50% số phiếu là người giành chiến thắng.

Trong khi chưa có người chiến thắng, lần lượt chọn ra người giành được ít phiếu nhất, gạch tên họ ra và tính lại; nói cách khác là chuyển các lá phiếu của người giành được ít phiếu nhất cho những người còn lại.

Cho \(n\) người, mỗi người đang giành được một số phiếu khác nhau. Trong viễn cảnh đẹp nhất, phải loại đi ít nhất bao nhiêu người để người đang đứng ở rank 2 thắng cuộc bầu cử?

Rõ ràng là giả sử người thua dồn hết phiếu cho người đang đứng ở rank 2.
[0:21] AC bài D.

Bài G: Cho \((p, q)\), tìm một bộ \((r, g)\) sao cho \(r\leq 10^6\) và \(\frac{2rg}{(r+g)(r+g-1)} = \frac{p}{q}\).

Phân giải ra thì thành một đa thức hai biến \(r, g\): \(pr^2 + 2(p-q) rg + pg^2 - pr -pg = 0\), mình bắt đầu loay hoay chuyển hệ trục tọa độ. Tìm cách chuyển được tầm 10 phút thì mới nhận ra \(r \leq 10^6\), tức là chỉ cần duyệt \(r\) rồi quy về phương trình bậc 2 biến \(g\), với \(a = p, b = 2r(p-q), c = pr(r-1)\).

[0:46] WA bài G. Sau một hồi debug thì phát hiện ra lỗi ở đây:

ll sqrtDelta = sqrt(delta) - 20;
while ((sqrtDelta+1) * (sqrtDelta+1) <= delta) sqrtDelta++;

Sợ sai số nên trừ một ít rồi hiệu chỉnh lại, cơ mà trừ lố về âm, mà âm bình phương lại ra dương, tức là có khi vòng while không chạy ngay từ đầu. Thế là phải sửa thành sqrtDelta = max(0ll, ...).
[0:54] TLE bài G vì quên xóa cerr.
[0:54] AC bài G.

Bài I: Cho kim tự tháp gồm \(n\) hàng (minh họa \(n=6\) như hình dưới) với một số ô trống, một kim tự tháp hợp lệ phải có số ở trên bằng tổng hai số ở dưới, và mỗi số nằm trong khoảng \([-99; 99]\). Kiểm tra xem có một nghiệm duy nhất, vô số nghiệm, hay vô nghiệm.

Có vẻ là đoạn này hết audiobook rồi, choke hẳn =))

Về cơ bản, cứ thấy nhóm 3 ô mà có 2 số đã điền thì điền số còn lại thôi. Mình ước tính số lượt chạy quanh quanh \(\mathcal{O}(n)\).
[1:04] WA bài I. Mình quên, nhỡ đâu trong input đề cho có nhóm 3 ô sai từ đầu, kiểu như \((5;8,2)\).
[1:10] AC bài I. Cơ mà mình khá nghi ngờ thuật này nó không có chuẩn.

Bài B: Cho một cây biểu thức gồm các node phép and, phép or, lá true, lá false. Cần phải đổi giá trị của ít nhất bao nhiêu lá để giá trị của cây biểu thức thay đổi?

Một bài DP đơn giản, mỗi node chỉ cần: (1) số nhánh T/F, (2) chi phí để đổi giá trị mỗi nhánh. Phần khó nhất của bài này nằm ở việc parsing đầu vào.
[1:43] AC bài B.

Ba tiếng đọc nhầm đề???

Bài K: Cho \(w\leq 52; d\leq 10\). Đếm số dãy độ dài \(w\), mỗi phần tử \(\in \{A, B, C\}\) sao cho:

Không có hai phần tử \(A\) hoặc hai phần tử \(C\) hoặc ba phần tử \(B\) đứng kề nhau

Chênh lệch số phần tử của hai loại bất kỳ không quá \(d\)

Dãy không đối xứng (non-palindromic).

Ép hàm DP khá dễ:

Gọi \(dp[a][b][c][last]\) là số dãy độ dài \(a+b+c\); gồm \(a, b, c\) phần tử mỗi loại; và ký tự cuối cùng \(last\) là \(A, B, C,\) hay là hai chữ \(B\) liên tiếp. Chuyển trạng thái thì dựa vào last:
- \(A \rightarrow B, C\);
- \(B \rightarrow A, BB, C\);
- \(C \rightarrow A, B\);
- \(BB \rightarrow A, C\);
Trừ bớt dãy palindrome thì duyệt \(a, b, c, last\) (và nếu \(w\) lẻ thì thêm \(center \in \{A, B, C\}\) chứ không gồm \(BB\)), rồi check số lượng + điều kiện trùng ký tự ở khu vực trung tâm, nếu thỏa mãn thì trừ đi \(dp[a][b][c][last]\) (với mỗi \(center\) thỏa mãn, nếu \(w\) lẻ).

[2:15] WA bài K.
Mình đọc code phải tầm 2-3 lần không thấy sai, nên mình quyết định code trâu rồi so sánh.
Vì input khá nhỏ nên mình duyệt hết, đây là script bigcheck.sh:

for ((w = 2; w <= 52; w++)) # thực tế thì i = 15 là ngủm rồi, trâu 3^ mà
do
    for ((k = 0; k <= w && k <= 10; k++))
    do
        echo "$w $k" | cat > input.txt
        echo "checking" $w $k
        ./check.sh             # là một script khác chạy hai code rồi diff
        if [ $? -ne 0 ]
        then
            echo "******!!!!" # hơi bực mình, censored ^^
        fi
    done
done

Mình rất bối rối vì chạy tới \(w=16\) rồi mà diff vẫn không báo sai. Không nhẽ mình trâu sai?
Đọc lại đề, mình mới phát hiện ra… lại đọc nhầm đề rồi.

Bài K: The same panel cannot be highlighted during two consecutive weeks, except for the middle panel (B) […] can be highlighted during two consecutive weeks, but not during three or more consecutive weeks. Mình đọc thiếu mất phần này rồi??????

Lật đật sửa lại cả code full lẫn code trâu, ./bigcheck.sh phát nữa cho chắc.
[3:20] AC bài K.

Bài E: Cho \(n \leq 10\) quân cờ, mỗi nước đi được ghi lại dưới dạng ô 1 -> ô 2. Tìm dãy \(n-1\) nước đi có thứ tự từ điển nhỏ nhất, sao cho cả \(n-1\) nước đều ăn quân.

Ban đầu mình tính DP kiểu gì đấy, nhưng sau tầm 2 phút thì mình nhận ra không thể tách đồ thị thành các cây. 5 phút sau linh cảm bảo mình rằng hoặc là không gian trạng thái nhỏ, hoặc nếu không gian lớn thì nhiều nghiệm nên nghiệm nhỏ nhất tới rất nhanh. Thế là quay lui thôi.

Để giảm thời gian duyệt thì phải tìm cách liệt kê nghiệm theo thứ tự, nên mình sắp xếp các quân cờ theo thứ tự từ nhỏ tới lớn. Ban đầu mình nghĩ có thể ép được lượt thứ \(i\) quân \(i\) ăn quân khác, nhưng sau đó chạy không ra nghiệm, vậy là buộc phải duyệt for (killer) for (victim != killer).

[4:02] WA bài E.
Bắt đầu ngồi đọc code xem thiếu chỗ nào, rồi là một mớ cerr, rồi là một mớ test nhỏ chạy thử. Mình sợ thứ tự duyệt của mình bị sai, nên thôi tìm tất cả nghiệm rồi so sánh lấy thằng có thứ tự nhỏ nhất.
[4:22] vẫn WA bài E.

Sau khi đọc lại đề, mình mới nhớ ra: Xe, Tượng, Hậu không thể ăn quân nếu có quân khác chắn đường. Lại tốn thêm một vòng for (mid != killer và victim) để kiểm tra xem có quân nào cản đường không. Với bản tính vừa code vừa nghĩ thì mình sai logic khá nhiều lần:
[4:42] WA bài E.
[4:47] WA bài E.
[4:48] WA bài E.
[4:49] WA bài E.
[4:54] WA bài E, đổi lại logic chứ rối nhùi. Vẫn là tính chênh lệch hàng và cột giữa victim và mid so với killer, sau đó xét các trường hợp sau:

Nếu so hàng (hoặc cột), một cái \(=0\) và một cái \(\neq 0\) thì bỏ qua mid.
Nếu so hàng (hoặc cột), một cái âm và một cái dương (tích âm) thì bỏ qua mid
Lúc này thì chắc chắn victim và mid cùng hướng, nếu abs(d_mid) < abs(d_victim) thì tức là mid chen ngang.

[4:57] WA bài E, nhận ra for(mid) nhưng không dùng mid tí nào vì gõ nhầm?
[4:58] AC bài E.

Những bài còn lại

Bài H đọc không hiểu đề lắm, chưa cài thử, nhưng có vẻ là Dijkstra \(d[u][prv]\)

Phân tích

Vấn đề cài đặt

Lỗi của bài F giống lỗi của bài L ở HCMC Regional vừa rồi; phương án giải quyết là để ý kỹ các edge case nhỏ, nhất là với \(n=1, 2\).

Bài D mình bị ám ảnh với sai số của số thực, chứ thực ra hàm sqrt không chênh tới mức đấy. Nếu sợ thì lần sau nên sửa thành sqrtDelta = max(0, sqrt(delta) - 1) để tránh âm và giảm kiểm tra.

Mình tự tin tư duy tổng quát hóa để cài đặt khá ổn – bài B, I, K và E code khá nhanh, cơ mà mấy cái phải casework thì chậm rì, không biết có phải vì không nháp kỹ ra để khỏi phải động não lúc cài rồi phải cài lại hay không.

Cuối cùng là hai quả đọc nhầm đề, dẫn tới việc phải debug rất nhiều, và thậm chí là phải sinh test. Cơ bản là đề dài, não lag, nên mình đọc lướt, cơ mà khoảng tầm 15-20% số bài là mình sẽ bỏ sót chi tiết. Cũng may là trình độ tiếng Anh của mình bây giờ không thể dịch nhầm nữa rồi, ghét CollegeBoard tư bản ăn chặn tiền học sinh nhưng phải cảm ơn nó đã tạo ra phần Evidence-Based R+W trong SAT.

Vấn đề chiến thuật

Như các bạn có thể thấy, cứ mỗi khi bị cấn một bài cài đặt nặng, mình sẽ mắc kẹt rất lâu, ít nhất là 1 tiếng.

Hồi virtual luyện tập cho HCMC’25, có một lần cả team mình virtual với Đăng đề Seoul. Bỏ qua chuyện ngài ấy code khỏe vãi, thì trong khi mình bị phân tâm giữa 2-3 bài có thể giải được, ngài đơn giản là bám theo bảng điểm và tập trung từng bài một.

Mình nhiều khi không biết có nên hy sinh một tí cẩn thận lấy 2-3 phút penalty \(\times\) số bài hay không, máu hơi liều.

Về đề thi

Không rõ cả khu Bắc Mỹ mọi năm như nào, nhưng ít nhất với miền Đông năm nay, đề thi thiên hoàn toàn vào việc cài đặt, meta khác hẳn các đề thi của khu ĐNÁ-TBD chúng ta. Nhìn chung là hợp để luyện Leetcode.

Nếu xét độ khó thuật toán, mình không rõ 3 bài khó nhất như thế nào, nhưng 8 bài mà mình làm được chỉ ngang bài thứ 5-6 của APAC, bài H thứ 9 nếu đúng là Dijkstra thì sẽ là bài 6 HCMC’25. Gần như không phải đụng tới cấu trúc dữ liệu, mấy bài tầm của mình thì chủ yếu là DP nhưng không quá khó để gọi hàm và xét chuyển trạng thái, nhận xét tính chất thì cũng không có nhiều, không có tí tham lam nào.

Tuy nhiên, các mô hình bài toán theo mình khá xấu, điển hình như: bài B xử lý input hơi rườm rà, bài K chỉ là gò công thức DP nhưng xử lý A C khác B + palindrome nên cài cũng cực, bài E xét quá nhiều trường hợp. Mình không biết nên đánh giá độ khó cài đặt như nào nhưng bài E ở trên cũng tương đương bài I của Seoul’25.

Nếu như ở APAC, giải được Leetcode Hard(est) không giúp bạn đứng được nửa trên bảng xếp hạng; thì Leetcode chỉ… chưa đủ để bạn thành công ở East Division, nhưng ít ra nó cũng giúp bạn phần nào trong việc luyện cách tư duy tổng quát hóa, lên giàn cấu trúc code.

Một trong những đặc điểm khác của đề thi là giới hạn đưa ra thường khá nhỏ, con số các bạn thường thấy sẽ vào khoảng 2-3 chữ số, thay vì ép giới hạn biến sát giới hạn thời gian như chúng ta thường thấy. Bài E mà ép như thường thấy thì kiểu 3 for trên còn bị TLE nữa chứ không chỉ WA.

Ghi chú

Có lẽ là cách dịch chuẩn nhất của khu Asia Pacific, vì bình thường cụm “Châu Á – Thái Bình Dương” sẽ bao gồm toàn bộ châu Á. ↩
Northeast, East Central, và Greater New York ↩
Sau khi gộp cả ba Regional vào. Nếu tách riêng ra thì mình sẽ đứng ở vị trí 16/87 ở East Central, 9/97 ở Northeast, và 4/82 ở Greater New York. ↩