ICPC World Finals · Astana 2024ICPC 2024Final

Tóm tắt

Chia 2n chi hội thành hai đội, mỗi đội n chi hội. Chi hội thứ i có toạ độ (x[i], y[i]).

Cần chia sao cho khoảng cách Euclid giữa cặp chi hội gần nhau nhất mà khác đội là lớn nhất có thể. In khoảng cách đó và danh sách chi hội của đội một.

Hướng làm

Cốt lõi là đại lượng cần tối đa hoá: khoảng cách của cặp gần nhau nhất khác đội. Cứ giả sử nó là một giá trị D cố định rồi suy ra hệ quả.

Gom nhóm

Mọi cặp có khoảng cách nhỏ hơn D buộc phải cùng đội — trái lại là vi phạm ngay. Vậy duyệt mọi cặp, cặp nào gần hơn D thì hợp nhất bằng disjoint-set.

Chia hai đội

Sau khi gom, ta được m nhóm với các cỡ g₁, g₂, …, gₘ. Giờ chỉ cần quan tâm cỡ nhóm, không cần quan tâm khoảng cách nữa: mọi cặp gần hơn D đã bị nhốt chung nhóm ở bước trước, nên ràng buộc khoảng cách coi như đã xử lý xong.

Việc còn lại là xếp các cỡ đó vào hai đội sao cho mỗi bên tổng bằng n — đúng bài knapsack (subset sum).

Chọn D

Đáp án buộc phải là một trong các khoảng cách có sẵn giữa hai điểm của input, nên không gian tìm kiếm chỉ còn O(m²) giá trị với m = 2n. Sort chúng lại rồi chặt nhị phân.

Chặt nhị phân được vì bài toán đơn điệu: D giảm thì các nhóm chỉ có thể nhỏ đi, tức là “vỡ” ra từ các nhóm cũ. Nếu với D ta ghép được tổng n, thì với D − 1 vẫn ghép được — cứ dựng lại các nhóm cũ trước rồi mới sinh tổng. Nên không có chuyện D được, D + 1 không được, rồi D + 2 lại được.

Subset sum bằng bitset

Chỗ tôi thích nhất ở bài này: knapsack viết bằng <bitset> thay cho mảng dp. Mỗi khi thêm giá trị num, ta bật bit num và OR thêm chính trạng thái hiện tại dịch trái num — tức là cộng num vào mọi tổng đang đạt được:

Bài này còn cần truy vết để in ra đội, nên thay vì một bitset ta giữ một mảng bitset dp[i], rồi lần ngược: ở nhóm i có cỡ num, nếu dp[i+1][cnt] và dp[i][cnt − num] đều đúng thì nhóm đó thuộc đội một.

Tóm tắt

Có n người chơi, mỗi người một tờ gồm k số. Người 1 nhanh nhất, người n chậm nhất.

Mỗi lượt, người nhanh nhất còn khả dụng gạch một số trên tờ của mình; một số trùng nhiều lần thì mỗi lượt chỉ gạch được một bản. Trò chơi kết thúc khi cả n · k số đã bị gạch.

Thứ tự số được gọi là phân bố đều. Với mỗi người, in xác suất người đó là người xong cuối cùng.

Hướng làm

Nhận xét dọn đường

Nếu người i có giá trị X, việc X có xuất hiện ở những người 1 → i−1 hay không không quan trọng — những người nhanh hơn đã gạch X xong trước rồi, nên coi như X không hề xuất hiện ở đó.

Người i không thua nếu mọi giá trị trên tờ của họ cũng xuất hiện ở tờ của những người i+1 → n. Ngược lại, những giá trị mà không ai trong i+1 → n có — gọi là “giá trị thiếu” — sẽ chắc chắn bị gọi sau cùng, và người i thua.

Ra công thức

Giả sử tập giá trị thiếu là V = {v₁, …, vₘ} với vⱼ là số lần giá trị đó xuất hiện trên tất cả các tờ. Với tổng n · k lượt gọi, số cách sắp xếp là (n·k)! / (x₁! x₂! … xₘ!); số cách để kết thúc đúng ở v₁ là (n·k−1)! / (… (v₁−1)!). Cộng lại rồi rút gọn, phần lớn giai thừa triệt tiêu và còn đúng:

Cài đặt

Gọn đến mức chỉ cần một map đếm số lần xuất hiện của mỗi giá trị, rồi quét ngược từ người n về người 1, giữ một set các giá trị đã xét: giá trị nào chưa từng xét thì cộng số lần xuất hiện của nó vào điểm của người hiện tại rồi đánh dấu đã xét.

Quét ngược đúng vì nó đảm bảo người chậm hơn được tính trọn phần giá trị chỉ riêng mình giữ. Đáp án của người i là ans[i] / (n · k).

Tóm tắt

Để nhập tịch, bạn phải có mặt ở nước đó ít nhất d ngày mỗi năm, trong y năm liên tiếp gần nhất. Năm ở đây là chu kỳ 12 tháng tính lùi từ ngày xin; coi mỗi năm có 365 ngày.

Bạn đã sống ở đó ít nhất y năm, nhưng đã ra khỏi nước n lần. Mỗi lần vắng cho bởi hai mốc YYYY-MM-DD, và các khoảng vắng đã xếp theo thứ tự thời gian.

In ra ngày sớm nhất mà bạn đủ điều kiện.

Hướng làm

Hình dung mỗi ngày là một điểm trên trục thời gian chạy từ trái sang phải. Miền năm nhỏ nên tổng số điểm kiểm soát được: tối đa 5000 × 365 ≈ 1.8 triệu — đủ nhỏ để quản bằng map hay set.

Phát biểu lại cho gọn

Cho một tập điểm, chia thành các xô có độ rộng cố định w = 365. Với mỗi mốc i, xét các xô [i, i−w+1], [i−w, i−2w+1], … và đòi mỗi xô có ít nhất d ô trống.

Công thức

Trộn tổng tiền tố với quy hoạch động. Gọi s[i] là số ô đã bị chiếm từ mốc gần nhất đến i, tức s[i] = s[i−1] + (1 nếu i là ngày vắng). Gọi dp[i] là số khoảng con hợp lệ kết thúc tại i:

Chặn miền duyệt

fromLive lấy min giữa “mốc cuối của input trừ y năm” và mốc đầu của input; toLive là mốc cuối. Nhưng toLive không bảo đảm đủ y năm, nên phải cộng thêm — và chỉ cần cộng tối đa y năm là từ đó về sau mọi khoảng đều hợp lệ. Vậy duyệt đến toLive cộng một năm là đủ, rồi ngày cần tìm lấy bằng cách cộng thêm max(0, y − dp[i]) năm.

Tóm tắt

Cho cây n đỉnh với n−1 cạnh: dòng thứ i cho v[i] và t[i], nghĩa là có cạnh trọng số t[i] nối đỉnh i với đỉnh v[i], và v[i] < i.

Cần đặt f xe cứu hoả. Hãy tính tổng thời gian di chuyển nhỏ nhất để xe tới được mọi đỉnh.

Hướng làm

Đặt giới hạn h: khoảng cách từ mỗi xe tới mọi đỉnh nó phụ trách không vượt h. Khi h tăng thì số xe tối thiểu cần dùng giảm — miền rộng hơn thì dễ xếp hơn, và bao được cả kết quả của miền hẹp hơn.

Mà “tối thiểu” nghĩa là: nếu x xe đủ thì x+1, x+2, … cũng đủ. Nên chỉ cần x ≤ f là chắc chắn xếp được f xe thoả ràng buộc. Vậy chặt nhị phân trên h, miền [0, n · max(t)].

Quy hoạch động trên cây cho mỗi h

Với mỗi đỉnh, giữ đúng ba giá trị:

• fn — số xe đã dùng.
• fu — đường dài nhất trong cây con chưa được phủ. Không cần đặt xe ngay: cứ giữ danh sách các đường dài ≤ h, và chỉ đặt xe khi buộc phải. Mà giữ cả danh sách thì thừa — chỉ cần giữ giá trị lớn nhất. −1 nghĩa là không có đường nào.
• fd — khoảng cách còn lại lớn nhất tới xe trong cây con, −1 nếu chưa có xe nào.

Cứ hình dung mỗi cây con giữ một danh sách “chuỗi” mà một đầu là xe, đầu kia là đỉnh hiện tại. Danh sách đó teo dần khi đi lên, nên giữ giá trị lớn nhất là đủ — tham lam: giá trị lớn nhất bảo đảm ta nối được đỉnh hiện tại vào chuỗi gần nhất đang có xe.

Gộp một cây con

Giả sử đang tính (fn, fd, fu) tại u, vừa thăm cây con v và có (sn, sd, su), với w là trọng số cạnh u–v:

• fn += sn.
• fd = max(fd, sd − w).
• Nếu su > −1 và su + w > h: buộc phải đặt xe tại v, vì đặt ở u thì không phủ nổi các đường trong cây con của v. Khi đó fd = max(fd, h − w) và fn++.
• Nếu su + w ≤ h: chỉ cần fu = max(fu, su + w).

Tính xong, nếu fd ≥ fu thì mọi đường trong fu đều đã với được xe trong h, nên đặt lại fu = −1. Cuối cùng, gọi đệ quy từ gốc: nếu fu vẫn khác −1 thì còn đường chưa phủ, đặt thêm một xe ở gốc (fn++).

Tóm tắt

Con đường ban đầu trống. Qua n ngày, mỗi ngày thêm một robot hoặc một cửa hàng vào một vị trí chưa bị chiếm:

• t[i] = 1 — thêm robot ở vị trí x[i].
• t[i] = 2 — thêm cửa hàng chứa c[i] tenge.

Di chuyển robot tốn 1 tenge mỗi mét; lợi nhuận khi đưa robot tới một cửa hàng là số tenge ở đó trừ đi quãng đường đã đi. Mỗi cửa hàng mỗi ngày chỉ bị một robot vét. Cuối ngày robot về chỗ cũ và cửa hàng được nạp lại.

Mỗi ngày, in lợi nhuận lớn nhất có thể.

Hướng làm

Xét trước trường hợp không có cập nhật. Nhận xét chốt: hai robot không bao giờ cắt nhau, thậm chí không chạm nhau — làm thế chắc chắn không tối ưu.

Năm trạng thái của một đoạn

Coi bài toán là một dãy vị trí, mỗi vị trí là robot hoặc cửa hàng. Xét đoạn giữa hai vị trí liền nhau, chỉ có đúng năm khả năng:

• Z0 — không robot nào băng qua đoạn.
• L1 — một robot băng từ phải sang trái.
• L2 — băng phải sang trái, rồi quay lại sang phải.
• R1 — một robot băng từ trái sang phải.
• R2 — băng trái sang phải, rồi quay lại sang trái.

Ma trận 5 × 5 cho mỗi vị trí

Mỗi vị trí i kẹp giữa hai đoạn: đoạn bên trái cho trạng thái trước, đoạn bên phải cho trạng thái sau. Vị trí đầu và cuối coi như có đoạn ảo trạng thái Z0.

Dựng cho mỗi vị trí một ma trận 5 × 5 ghi chi phí theo cặp (trạng thái trước, trạng thái sau), khởi tạo toàn −∞. Có những cặp gán được ngay bất kể vị trí đó là gì; riêng cặp (Z0, Z0) thì nếu có robot và có cửa hàng cùng chỗ thì chi phí tăng, còn không thì bằng 0 vì chẳng có gì xảy ra. Còn những cặp đòi phải có robot thì không có robot là không dựng được đoạn sau.

Gộp hai vị trí

Hai vị trí liền nhau gộp được khi trạng thái phải của vị trí trước trùng trạng thái trái của vị trí sau. Đó đúng là nhân ma trận, chỉ cần thay phép cộng bằng max và phép nhân bằng cộng:

Segment tree giữ ma trận

Để chịu được cập nhật online, dùng segment tree mà mỗi nút là một ma trận như trên; đáp án nằm ở nút gốc, cụ thể là T[1][Z0][Z0]. Mỗi truy vấn thêm robot hay cửa hàng thì chỉ dựng lại ma trận của một lá rồi gộp ngược lên.

Các vị trí được nén lại trước bằng sort và lower_bound; một vị trí chưa có gì coi như cửa hàng với 0 tenge.