Xàm xí

Sau thất bại ở HCMC, mình tiếp tục với đam mê bằng SWERC’25.

Đây là khu vực của ngài Đăng (2 HCV IMO, cựu teammate HUS.WFKC, thành viên team ENS Ulm 3 trên BXH).

Meta đề khá hợp với mình: thuật tường minh, nhận xét không quá khó, code ngắn. Đưa bộ đề này vào đánh ở APAC, bảng rank chắc cao hơn tí.

Diễn biến

Kết quả	A	B	C	D	E	F	G	H	I	J	K	L
8 bài	+	+	+	+1	+	+				+2		+3
1171 phút	33	96	207	37	221	49				134		274

[0:00] Đọc đề bài A. Thấy cũng ngon ăn nên bắt tay vào làm luôn.

Quy về mảng đếm, sau đó sử dụng một set và một map để lần lượt quản lý các giá trị \(=0\) và \(>1\).
Hơi vội vàng trong việc xử lý logic nên có xóa đi code lại.

[0:33] Sau khi nộp lần 1 thì phát hiện ra quên xóa debug, nộp lần hai thì AC bài A ở cả hai lần nộp. Nhìn bảng điểm thấy D, E, F nhiều đội làm được, tiến hành đọc đề D trước.

[0:37] Sau khi WA vì quên mất \(0 \leq a_i\) thì mình đã bổ sung để AC bài D.
Nhìn thấy bài E công thức hơi rườm rà (???) thì mình quyết định làm F

[0:49] AC bài F. Lúc này thấy các đội làm B và J nhiều, mình quyết định xử lý B trước.

Ban đầu mình cho ra hai nhận xét sau:
- Nhận xét 1: Nếu chọn cược \(p \leq a_i\) thì dù \(p\) có là bao nhiêu, số điểm tăng lên vẫn là \(a_i - p\); tương tự với cược \(p \geq a_i\). Suy ra ta sẽ ưu tiên cược \(\leq\) cho \(a_i\) lớn và \(\geq\) cho \(a_i\) nhỏ.
- Nhận xét 2 (thừa): Nếu \(l \geq a_i\) hoặc \(r \leq a_i\), ta luôn chốt cược như vậy.
Mình loay hoay với việc chọn cái nào cược \(\geq\) cái nào cược \(\leq\), mình phát hiện ra hai nhận xét nữa:
- Nhận xét 3: Đại khái là nếu để đảm bảo điểm tăng dù \(p\) thay đổi như nào, giả sử mảng \(a\) tăng dần, cứ cược \(\geq a_i\) và \(\leq a_j\) với \(i<j\) để đảm bảo số điểm tăng lên \((a_j-p)+(p-a_i)=a_j-a_i\).
- Nhận xét 4: Sau khi chốt cược, tổng số điểm nhận về có dạng \(Y + Xp\) là hàm bậc nhất của \(p\), nên cực tiểu buộc phải nằm ở \(p=l\) hoặc \(p=r\). Cụ thể hơn, nếu \(X<0\) thì cực tiểu tại \(p=r\) và ngược lại \(X > 0\) thì cực tiểu ở \(p=l\).
Đến khi ra được NX4 thêm vài phút nữa thì mình quyết định duyệt \(X = -n \rightarrow n\).
- Không mất tính tổng quát, giả sử \(X < 0\):
  - Lhi đó chúng ta chọn \(X\) giá trị \(a_i\) lớn nhất để cộng vào \(Y\).
  - Phần còn lại, từ nhận xét 3 suy ra cứ chia đều cho cả hai loại cược thì \(Y\) luôn tăng mà \(X\) không bị thay đổi.
  - Vì thế, ta sẽ chọn ra \(X^+\) giá trị lớn nhất và \(X^-\) giá trị nhỏ nhất của mảng \(a\), sao cho \(X^+ + X^- = n\) và \(X^+ - X^- = X\), lấy hết hoặc có thể lẻ một phần tử.
  - Vì đã giả sử mảng \(a\) tăng dần, tổng cần tính là một đoạn liên tiếp \(\Rightarrow\) dùng mảng tổng tiền tố

[1:36] AC bài B in one blow. Sau khi đọc C không có ý tưởng gì, và nghĩ sơ bài E vẫn lag thì mình đi kiếm Job.

DP khá cổ điển: dp[iB][iA] có thể tạo bởi một trong hai hoặc cả hai trường hợp sau:
1. dp[iB-1][iA-1] nếu a[iA] == b[iB]
2. dp[iB-1][?] nếu b[iB] tính bằng cách gộp một đoạn
Câu hỏi là gộp một đoạn như nào?
- Mình tưởng sẽ phải xem thử mỗi đoạn \((l,r)\) gộp ra số gì, cơ mà có vẻ có khả năng gộp được ra khá nhiều số
- Vãi cả nhận xét: mọi đoạn \((l;r)\) đều có thể gộp ra mọi số \(x\) thỏa mãn \(1 \leq x \leq r-l+1\)

[2:06] WA bài J. Mình không biết vì sao sai nên sửa bậy trường hợp cơ bản f[0][0] = true thành f[0][i bất kỳ] = true

[2:07] WA bài J ngay test 1. Sau một chặp thì mình phát hiện ra sai logic, cụ thể mình đã kết luận sớm \(f[iB][iA] \Rightarrow f[iB][iA+1]\), trong khi điều này chỉ đúng với trường hợp 2.

[2:14] AC bài J. Mình thấy G ngon ăn, đâm đầu vào nhưng không ra, sau đó nghĩ E vẫn lag nên mình quyết định thử C.

Lúc này mình mới nhận ra mình đọc thiếu điều kiện: \(p\) là hoán vị.
Thế là chỉ cần tạo mảng nxt để dựng đồ thị hoán vị xong xử lý bậy bạ thôi.

[3:27] AC bài C. Lúc này mới nhìn lại E

Thứ tự của 4 với 8 không quan trọng.
Với một xâu độ dài \(l\) có \(c_8\) ký tự 8, điểm \((x;y)\) sẽ được mở khóa nếu \(x+y \leq l+c_8\).

[3:41] AC bài E. Nhìn bảng điểm thì ngoài G còn L, mình đọc L thử

\(f(t)\) rõ ràng bằng ký tự xuất hiện nhiều lần nhất, tính được bằng 26 mảng tổng tiền tố.
Giả sử một trong số đó là \(c\). Các xâu \(LFS(t)\) không thể chồng lấn lên nhau, nói cách khác, \(c\) không thể xuất hiện 2 lần trong xâu này. Lý do là vì lần xuất hiện cuối của \(c\) không còn \(c\) nào nữa.
Ta cần biết giữa hai lần xuất hiện liên tiếp của \(c\), phần xâu trùng dài nhất là bao nhiêu. Cái này làm trâu được, tổng độ phức tạp cho bước này là \(\mathcal{O}(n)\).
Với mỗi truy vấn \((l; r)\), ta chỉ cần tìm lần đầu và lần cuối xuất hiện của \(c\), rồi lấy \(\min\) các phần xâu trùng đã tính bằng tìm kiếm nhị phân + một CTDL cây. Chú ý xâu cuối có thể tràn khỏi \(r\).

[4:14] Mình dùng Sparse Table, ban đầu khai báo mảng [26][19][5e5] thế là MLE

[4:16] Chiều cuối cùng mình sử dụng vector thay vì mảng thường, vậy là thành WA.

[4:29] Ném một mớ assert để đảm bảo code không bug, vẫn thành WA.

[4:34] Mình không chú ý tới xâu cuối, chú ý xong thì AC bài L.

Cuối cùng là bài G, bài mà mình tiêu tốn khá nhiều thời gian. Mình không giải được bài này trong phòng thi.

Ban đầu mình nghĩ tới việc chia thành các block \(b \approx \sqrt{250000}\), xếp block tuần tự từ nhỏ tới lớn, mỗi block xếp ngược lại. Code một script Python ngắn chạy thử, thấy cost toàn là \(10^7\) đồng.
Sau đó mình mới nghĩ ra chuyện đưa về hệ nhị phân: ưu tiên các số lẻ \(+1\), rồi các số chia 2 không chia 4, rồi các số chia 4 không chia 8, … Mỗi block như vậy tốn 125000 đồng, tầm 8 block như vậy là hết sạch 1 triệu đồng, mà \(\lfloor\log_2(250000)\rfloor = 17\). Tối ưu một tí thì cost vẫn vào khoảng 1 củ rưỡi đồng.
Mình có nghĩ tới việc chuyển sang hệ tam phân, cơ mà test thử cả tam lẫn tứ phân thì cost đều vượt quá.

Hết giờ đọc solution thì BTC bảo dùng hệ… \(\sqrt[3]{250000} \approx 62\).

Nhận xét

Điểm cộng

Nghĩ bài tập trung hơn, chi tiết ở mức đủ để code luôn.
Code tương đối nhanh, bug ở mức chấp nhận được.

Điểm trừ

Thứ tự nghĩ bài không phù hợp, ảnh hưởng tới pen
- bài E dễ hơn lại nghĩ sau
- bài C cũng dễ nhưng không để ý chi tiết hoán vị.
Cần viết rõ công thức QHĐ + tối ưu trước khi code để tránh bug
- Maybe dần dần bỏ thói quen vừa code vừa nghĩ?
Cần đọc kỹ đề hơn.

Cần học thêm

Hình học

Tính viết học thêm về hệ cơ số, tại quả hệ 62-phân thì mình khá bất ngờ. Cơ mà nếu cho thêm 5 tiếng nữa thử nghiệm thì chắc là được, tại mình vẫn chưa khám phá kỹ chi phí của các hệ cơ số, chứ mình nghĩ kiến thức về hệ cơ số như vậy là ổn.