Phân tích: Saving the Jelly

Test Set 1

Với \(N\le10\), có thể dùng quy hoạch động bitmask, trong đó mỗi viên kẹo còn lại và mỗi đứa trẻ còn lại tương ứng với một bit. Cách này về bản chất thử mọi thứ tự của trẻ và mọi cách phá hòa. Tổng độ phức tạp là \(O(N^2\cdot2^{2N})\). Thuật toán vẫn chạy kịp vì ta chỉ xét các trạng thái mà số trẻ đã ghép bằng số kẹo đã ghép.

Test Set 2

Trước hết, xây dựng một đồ thị hai phía với \(N\) trẻ và \(N\) viên kẹo không tính viên thạch việt quất làm các đỉnh. Thêm cạnh từ trẻ \(a\) tới kẹo \(b\) nếu khoảng cách từ \(a\) tới \(b\) không lớn hơn khoảng cách từ \(a\) tới thạch việt quất.

Rõ ràng, một điều kiện cần — nhưng thoạt nhìn chưa chắc đủ — để Mr. Jolly giữ được thạch là đồ thị có một ghép cặp hoàn hảo.

Hóa ra đây cũng là điều kiện đủ. Ta sẽ chứng minh bằng cách biến một ghép cặp hoàn hảo thành thứ tự gọi tên bọn trẻ.

Trước hết, nếu có một trẻ đang được ghép với viên kẹo gần em ấy nhất, ta có thể gọi trẻ đó rồi xóa cả trẻ lẫn viên kẹo khỏi đồ thị.

Nếu không, mọi trẻ đều đang được ghép với một viên kẹo chưa bị lấy nhưng không phải viên gần nhất. Khi đó ta tìm một chu trình bằng quy trình sau, bắt đầu từ một trẻ \(a\) bất kỳ:

1. Tìm viên kẹo \(b\) gần trẻ \(a\) nhất và đi tới \(b\). Cạnh này chắc chắn không thuộc ghép cặp hiện tại.
2. Tìm trẻ \(a\) hiện đang được ghép với kẹo \(b\) và đi tới \(a\). Cạnh này thuộc ghép cặp hiện tại.

Cuối cùng, quá trình sẽ tạo một chu trình có độ dài chẵn, không nhất thiết chứa trẻ ban đầu. Vì ta luân phiên đi qua cạnh thuộc và không thuộc ghép cặp, có thể đổi vai trò hai loại cạnh trên chu trình để thu được một ghép cặp hoàn hảo mới. Sau phép đổi, mọi trẻ trên chu trình đều được ghép với viên kẹo gần mình nhất, nên ít nhất một trẻ có thể được gọi.

Ta đã chứng minh ghép cặp hoàn hảo là điều kiện cần, đồng thời từ một ghép cặp hoàn hảo luôn xây dựng được thứ tự thỏa yêu cầu của Mr. Jolly. Vì thế, ghép cặp hoàn hảo tồn tại khi và chỉ khi có thể cứu viên thạch.

Có thể tìm ghép cặp hoàn hảo trong \(O(N^2\sqrt N)\) bằng thuật toán Hopcroft–Karp. Nếu cài đặt cẩn thận, việc dựng lời giải từ ghép cặp tốn \(O(N^2)\).

Dữ liệu kiểm thử

Google khuyến nghị bạn luyện gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Phân tích chính thức của Google Code Jam 2022, Vòng 2, bài Saving the Jelly.