ICPC World Finals · Baku 2025ICPC 2025Final

Tóm tắt

Một con robot đi theo thứ tự ưu tiên cố định NESW. Mỗi lần quyết định di chuyển, nó chọn hướng đầu tiên trong thứ tự đó mà không bị chặn.

Tuy nhiên vẫn có khả năng một tia vũ trụ (bức xạ) làm nó đổi sang một thứ tự khác — ví dụ từ NESW sang một hoán vị khác như ESNW.

Cho một danh sách các bản ghi LOG, tính số lần tối thiểu robot đã bị tia vũ trụ tác động.

Hướng làm

Có 24 (4!) trạng thái — chính là các hoán vị của thứ tự ưu tiên (N, E, S, W). Với mỗi thứ tự, đường đi của robot là xác định, nên có thể dùng đệ quy / quy hoạch động để tìm số lần đổi hướng tối thiểu.

Định nghĩa dp(suite, x, y, step): thử qua tất cả các hoán vị suite (cả 4! thứ tự).

Chuyển trạng thái

• Đổi suite → chi phí +1.
• Giữ nguyên suite → chi phí +0, nhưng chỉ khi nước đi hợp lệ (khớp log, không bị chặn).

Hàm phụ

getNext(suite, x, y) → {N, S, E, W}: trả về hướng thực sự được chọn dưới thứ tự ưu tiên đó, tại ô (x, y).

Tóm tắt

Cho m cái bát và n con mèo. Mỗi con mèo có một danh sách bát nó thích (wishlist).

Mèo đi từ trái sang phải, từ bát 1 đến bát m, và dừng ở bát đầu tiên xuất hiện trong wishlist của nó. Với mỗi con mèo, ta biết trước vị trí đích mà nó phải dừng.

Xác định xem có tồn tại cách sắp xếp các bát sao cho mọi con mèo đều dừng đúng vị trí đích hay không.

Hướng làm

Bài này có vài chỗ dễ làm ta rối khi đi tìm đáp án đúng. Ví dụ, nếu một con mèo thích tất cả các bát nhưng vị trí đích lớn hơn 1 thì vô nghiệm. Hoặc: các phụ thuộc thay đổi ngay khi ta chọn một bát, khiến kết quả khác đi. Thêm nữa, nếu một vị trí có nhiều bát chọn được, chọn bát này thì chạy nhưng lại chặn mất bát khác ở bước sau.

Xử lý hết các trường hợp đó khá khó, nhất là khi ràng buộc quá lớn để vét cạn. Vậy bài này cần quy hoạch động hoặc tham lam — mà quy hoạch động thì không có công thức nào rõ ràng, nên ta thử tham lam rồi chứng minh vì sao nó đúng.

Neo từng vị trí

Với mỗi vị trí, có hai trường hợp.

1 · Không con mèo nào cần dừng ở đây

Bát được chọn phải không nằm trong wishlist của bất kỳ con mèo nào. Gọi tập các bát như vậy là free set. Nếu free set rỗng — tức mọi bát đều xuất hiện trong ít nhất một wishlist — trả lời no luôn.

Để biết một bát có tự do hay không, ta giữ một tập cùng một biến đếm phụ thuộc cho mỗi bát: nếu bát nằm trong wishlist nào đó thì dep[pot] > 0; khi dep[pot] == 0 thì đưa bát đó vào free set.

2 · Có một nhóm mèo cần dừng ở đây

Ta phải chọn một bát nằm trong wishlist của tất cả các con mèo có đích là vị trí này — tức là giao của những wishlist đó. Chỗ này cần một cách làm khéo hơn một chút cho gọn.

Nếu chọn được một bát khiến mọi con mèo có đích ở đây đều dừng lại, thì phải giải phóng phụ thuộc cho toàn bộ bát trong wishlist của chúng: duyệt qua và giảm dep[pot], bát nào về 0 thì chuyển sang free set.

Sau đó mới tìm giao các wishlist: đổ hết bát vào một danh sách, sắp xếp rồi đếm số lần xuất hiện (hoặc dựng map đếm). Bát nào có số đếm bằng đúng số mèo là ứng viên hợp lệ.

Nhiều ứng viên thì sao? Điểm mấu chốt là chỉ được chọn tuỳ ý nếu ứng viên đó nằm trong free set. Nếu không, nó vẫn còn trong wishlist của con mèo nào đó chưa tới đích, và chọn nó thì con mèo kia sẽ dừng ở đây thay vì ở đích của nó. Vậy nên: có nhiều ứng viên thì chọn bất kỳ ứng viên nào thuộc free set; nếu không ứng viên nào thuộc free set thì trả lời no.

Tóm tắt

Điểm ban đầu là 0. Sau mỗi lượt, điểm tăng thêm một lượng cố định, và có giới hạn điểm tối đa.

Bạn muốn điểm của đội luôn được hiển thị, nên phải chuẩn bị sẵn các tấm biển. Mỗi tấm in đúng một chữ số, ghép lại thành điểm số. Các tấm biển này khá đắt — hãy tìm số tấm tối thiểu cần mua để hiển thị được mọi điểm số có thể đạt tới.

Lưu ý: không cần tấm nào in chữ số 9, vì tấm 6 lật ngược lại là thành 9.

Hướng làm

Coi p như các đồng xu có số lượng không giới hạn, và đặt g = GCD(p[0], p[1], …, p[n]). Ta có tính chất: mọi tổng tạo được đều chia hết cho g.

Dựa vào bài toán đồng xu Frobenius:

Vậy mọi số ≥ g · (mn − m − n + 1) ≥ g · 10⁶ đều biểu diễn được. Chia bài toán làm hai phần.

Phần 1 · Sinh các số nhỏ

Sinh mọi số đạt tới được trong đoạn [0, limit]. Ý tưởng là dùng một hàng đợi: mỗi vòng lấy giá trị nhỏ nhất rồi cộng với từng phần tử trong danh sách P.

Phần 2 · Digit DP cho phần còn lại

Đã biết mọi số trong [limit, m] đều sinh được, nên giờ chuyển sang tìm số lần xuất hiện tối đa của một chữ số d (với d chạy từ 1 đến 9), bằng digit DP.

Mọi số trong [limit, m] chia hết cho g đều hợp lệ, nên trạng thái DP cần lưu:

• Số có chia hết cho g không → lưu số dư theo modulo g (1 → 999).
• Đã dựng được bao nhiêu chữ số (1 → 18).
• Chữ số d đã xuất hiện bao nhiêu lần (1 → 18).
• Số hiện tại đã nhỏ hơn m chưa (0 hoặc 1).
• Chữ số cuối hiện tại (0 → 9).

Luật chuyển:

• Nếu đã nhỏ hơn m, được đặt tự do chữ số 0 → 9.
• Nếu chưa, phải đặt theo đúng tiền tố của m.

Tóm tắt

Cho n bánh xe, mỗi bánh có n ký tự phân biệt, và thứ tự ký tự trên mọi bánh là như nhau.

Bạn đứng sau các bánh xe và có thể quay bánh bất kỳ bao nhiêu bước tuỳ ý. Mục tiêu là trúng jackpot: làm cho mọi ký tự đang hiện giống hệt nhau — dù bạn không nhìn thấy ký tự nào đang hiện.

Bạn được phép truy vấn để biết hiện đang có bao nhiêu ký tự phân biệt.

Hướng làm

Bài này giống như có tối đa 50 con số bị giấu đi, và ta chỉ biết hiện có bao nhiêu giá trị phân biệt. Mục tiêu là bingo — mọi số bằng nhau — trong không quá 10 000 nước.

Có thể có nhiều cách, nhưng hướng của tôi chia bài làm hai pha: pha 1 làm cho mọi số đôi một khác nhau; pha 2 tính xem mỗi vị trí cần quay bao nhiêu bước để khớp với số đầu tiên.

Pha 1 · Làm mọi số khác nhau

Làm được trong tối đa n² nước (nhiều nhất 2 500). Với mỗi vị trí, quay bánh đó từng bước một và dừng ngay khi thấy số giá trị phân biệt tăng lên.

Chứng minh luôn tăng được: mỗi lần thử, ta duyệt qua mọi giá trị từ 1 đến n. Nếu không thể tăng số giá trị phân biệt, thì mỗi lần quay đều phải rơi vào một nhóm đã có sẵn mà không sinh ra giá trị mới. Điều đó đòi hỏi ít nhất n nhóm phân biệt, cộng thêm chính bánh xe đang quay, thành ít nhất n + 1 nhóm — mâu thuẫn với việc chỉ có n bánh xe.

Pha 2 · Dò số bước để khớp bánh đầu

Giờ mọi số đã khác nhau. Với mỗi vị trí, ta cần kiểm tra xem nó có bằng số đầu tiên không. Chiến lược như sau: thử quay vị trí i thêm x bước (x chạy từ 1 đến n − 1). Với mỗi kết quả, ta giả định rằng sau khi quay, giá trị ở vị trí i bằng giá trị ở vị trí 1.

Dựa trên giả định đó, việc còn lại là kiểm chứng. Nếu đúng, ta xác nhận quay x bước sẽ khớp vị trí 1, ghi lại vào bộ nhớ, rồi quay vị trí i về trạng thái cũ và sang vị trí tiếp theo.

Cách kiểm chứng: nếu quay bánh i thêm x bước mà nó bằng giá trị của bánh 1, thì sau khi quay bánh 1 một số bước, bánh 1 rồi cũng sẽ nhận giá trị của bánh i. Đúng lúc đó, số giá trị phân biệt phải quay lại n.

Xấu nhất có thể cần tới n lần quay để kiểm tra, làm cả quy trình thành O(n²): lặp tối đa n giá trị x cho bánh i, mỗi x lại lặp tối đa n bước để thử bánh 1. Nhưng vì mọi vị trí đang có giá trị phân biệt nên không phải lúc nào cũng chạm trường hợp xấu nhất.

Cắt sớm

Sau lần quay đầu của bánh i, số giá trị phân biệt phải tụt xuống n − 1, vì bánh i giờ đã trùng với một bánh nào đó — ta giả định nó trùng bánh 1. Rồi khi quay bánh 1, số giá trị phân biệt phải thành n − 1 hoặc n. Thành n thì dừng ngay; đổi theo kiểu khác thì bác bỏ giả định luôn.

Nếu quay bánh i thêm x bước mà không khớp bánh 1, ta vẫn còn n − 1 giá trị phân biệt (vì bánh i đã va vào bánh khác). Khi quay bánh 1, nó có thể nhảy vào đúng giá trị gốc của bánh i, hoặc vào giá trị khác và làm số phân biệt tụt xuống n − 2. Cả hai trường hợp thường chỉ cần 2–3 lần kiểm tra là bác bỏ được giả định sai.

Ghi chú cài đặt

Ta phải quay vị trí i thêm x nước, và có khi phải quay ngược về. Việc này khó quản lý, nên hãy coi quay về là đưa vị trí i về trạng thái gốc, tức 0 nước.

• Dùng một mảng memo và dựng một interface hỗ trợ quay vị trí i thêm x bước, giấu toàn bộ phần phức tạp của truy vấn ra sau nó.
• Cache kết quả: nếu need == 0 thì khỏi gọi truy vấn, trả về kết quả lưu lần trước.
• Cách này cũng giúp chỉnh bánh xe về đúng vị trí. Ví dụ muốn chuyển bánh i từ vị trí x sang y với y < x, phép chỉnh sẽ gọi roll với need = y − x, là một số âm.
• Khi cần lại giá trị thì trả thẳng giá trị đã cache, dùng lại nhiều lần mà không tốn thêm lượt tương tác nào.

Tóm tắt

Cho n cái cốc hình trụ, cốc thứ i cao 2i − 1 cm. Cốc i lọt hoàn toàn vào trong cốc j khi và chỉ khi i < j.

Rửa xong, bạn xếp tất cả thành một tháp. Luật xếp: mỗi cốc phải đặt thẳng đứng, miệng hướng lên, và tâm của mọi cốc thẳng hàng theo phương dọc.

Cho giá trị h, tìm một thứ tự xếp sao cho tháp cao đúng h, hoặc báo là không thể.

Hướng làm

Cốc lớn chứa được cốc nhỏ hơn. Chiều cao nhỏ nhất đạt được là 2n − 1, lớn nhất là 1 + 3 + … + (2n − 1) = n².

Nghĩa là ta gộp các tập bằng cách nhét cái nhỏ vào cái lớn — nói cách khác là dựng tổng của các tập con. Tổng luôn phải chứa (2n − 1), cộng thêm một tập con bất kỳ của các giá trị còn lại. Vậy dùng tham lam: cho K, duyệt từ (2n − 1) xuống 1 và trừ đi bất cứ khi nào trừ được.

Hai trường hợp đặc biệt

• K = 2n + 1: nếu n ≥ 4, xếp được bằng (2n − 1), 3 và (2n − 2). Nếu n < 4 thì không.
• K = n² − 2: vô nghiệm. Để đạt tổng n² ta phải trừ đi 2, nhưng chỉ trừ được 1 hoặc 3 — không có cách nào trừ đúng 2.

Giả sử trừ được 2 bằng cách gộp vài cốc. Không làm được với 1–2 cốc: hai cốc không gộp vừa vặn được, vì hoặc chúng đóng góp thẳng vào tổng n², hoặc cốc này phải nằm trong cốc kia.

Với ba cốc x, y, z (z lớn nhất), chiều cao tối đa là max(z, x + y + 1). Tức lượng mất đi là z hoặc (x + y), mà cả hai luôn ≥ 4. Vậy không thể mất đúng 2 khi xếp nhiều hơn hai cốc.

Bẫy của tham lam

Ngoài hai trường hợp trên thì luôn dựng được bằng tham lam. Nhưng phải tránh trừ H đi 2i − 1 khi H = 2i + 1, vì phần dư còn lại sẽ bất khả thi. Ví dụ chiều cao còn lại là 9 thì không được lấy 7, vì sẽ còn 2, mà không có cách nào tạo 2 từ các chiều cao lẻ còn lại.

Tóm tắt

Cần đi từ địa điểm thi (xc, yc) tới lễ trao giải (xa, ya).

Tia nắng đi theo hướng (0, 1), tức từ nam lên bắc. Bạn sẽ bị chói nắng nếu đi theo hướng (x, y) với y < 0, bất kể x là bao nhiêu.

Có n hình chữ nhật (x1, y1, x2, y2) che nắng nếu ta đi vào bên trong. Các hình chữ nhật này không chạm cũng không cắt nhau. In ra quãng đường tối thiểu phải đi dưới nắng.

Hướng làm

Chia bài dựa trên mấy nhận xét sau:

• Nếu điểm trao giải cao hơn điểm thi (ya ≥ yc) thì ta không phải đối mặt với nắng, vì tia nắng đi từ nam lên bắc — đáp án là 0.
• Đi sang trái hay sang phải không ảnh hưởng tới kết quả, nên chỉ cần quan tâm chuyển động theo chiều dọc.
• Có thể đi xuyên qua các hình chữ nhật cắt toạ độ y hiện tại. Nếu có hình chữ nhật trải dọc từ y1 tới y2 thì nó che được toàn bộ đoạn [y1, y2]. Toạ độ x1, x2 không quan trọng với bài này.

Với các nhận xét đó, việc còn lại chỉ là tìm cách đi từ yc tới ya khi biết n đoạn được che [y1, y2].

Đếm phần hở

Ta đếm tổng các đoạn không được che khi đi từ ya về yc. Giữ một danh sách các đoạn [y1, y2] và thêm vào đó một đoạn [yc, yc], để khi chạm yc thì dừng.

Khởi tạo một con trỏ bằng ya. Sắp xếp danh sách đoạn tăng dần rồi duyệt: nếu con trỏ hiện tại nhỏ hơn điểm đầu của đoạn đang xét, cộng khoảng hở đó vào kết quả. Luôn cập nhật con trỏ thành giá trị lớn nhất trong các điểm cuối đã đi qua, và dừng khi đoạn hiện tại bắt đầu tại yc.