Về đề thi ACM ICPC 2006

Cuộc thi ICPC đã xong. Bảng tổng sắp đã có. Kết quả của BK Eagles còn khiêm tốn, nhưng lần đầu đi thi thế là tốt. Tôi vừa xem qua đề thi (PDF), có các phân tích sơ bộ như sau:

• Problem A: bài quy hoạch động (dynamic programming) thứ nhất.
• Problem B: về cơ bản là vấn đề hiện thực các thuật toán minimum weight perfect matching và maximum weight perfect matching trên bipartite (multi) graph. Bằng cách lấy phần bù của các weights, ta có thể biến maximum matching thành minimum matching; tức là chỉ cần implement một thuật toán là đủ. Bài báo này có tổng kết nhỏ trong phần giới thiệu về các kết quả đến nay, bao gồm các implementations của bài toán minimum weight perfect matching trên các graph tổng quát (có thể không bipartite). Xem thêm bài này nữa. Phương pháp đơn giản (nhưng có thể không hiệu quả nhất) cho bài này thường dùng các ý tưởng của linear programming (dùng weight shifting chẳng hạn).
• Problem C: hồi xưa ít vào lớp cơ ứng dụng, bây giờ quên hết vất lý kiểu này rồi . Bạn nào còn nhớ vật lý giải giùm bài này.
• Problem D: có thể giải bằng cách liệt kê các bipartite numbers từ số nhỏ nhất lớn hơn hoặc bằng public key (liệt kê các bộ tứ

  [m, s, n, t]

  ), sau đó chạy thuật toán Euclidean xem có chia hết cho public key không. Nếu biết thêm về các numerical algorithms và lý thuyết số thì chắc sẽ có lời giải hiệu quả hơn.

• Problem E: thêm một bài quy hoạch động nữa, có lẽ là bài dễ nhất trong đề.
• Problem F: bài này rất hay, quy hoạch động thứ ba.
• Problem G: bài quy hoạch động thứ tư.
• Problem H: mấy trò gấp giấy này thì có lẽ Eric Demaine là trùm sò. Bài này về ý tưởng về thuật toán không phức tạp lắm, nhưng thiết kế cấu trúc dữ liệu cho sạch sẽ thì hơi phiền. Đại khái, mỗi pocket được mô hình bằng ba đoạn thẳng song song, một đoạn đáy và hai đoạn miệng. (Các đoạn miệng có thể so le và không nhất thiết bằng nhau, đoạn đáy có thể nằm ở vô cực nếu pocket “thông” qua bên kia.) Tùy theo nếp gấp ở đâu (trái, phải, trên, dưới, cắt và cắt như thế nào các đoạn đáy và miệng pockets), và về hướng nào (L, R, U, D) mà ta cập nhật các pockets tương ứng. Giữ một biến đếm các pockets cho kết quả cuối cùng.
• Problem I: bài này hỏi tính đường kính của một đồ thị vô hướng cho trước. Để tính đường kính, có thể dùng thuật toán cho bài all-pair shortest paths, ví dụ thuật toán Floyd-Warshall (xem một bài giảng của tôi). Có các thuật toán chạy nhanh hơn, ví dụ thuật toán của Raimund Seidel.
• Problem J: bài này rất thú vị, cá nhân tôi thích nhất trong tất cả các bài.

(Disclaimer: tôi chưa thật sự ngồi bỏ thời gian ghi lại chi tiết lời giải của bài nào – các phân tích trên chỉ là phản ứng đầu tiên sau khi đọc đề bài, không đảm bảo độ chính xác tuyệt đối.)