Test Set 1

Điều đầu tiên cần nhận ra: nếu binh sĩ \(s\) không hành động đầu tiên, không có lý do để \(s\) di chuyển trước khi mọi binh sĩ sẽ bắn trước cô ấy hoàn tất nhiệm vụ.

Gọi output là một chiến lược: một phép ghép giữa một số binh sĩ và các tháp, kèm thứ tự cụ thể. Với chiến lược cố định, ta kiểm tra tính khả thi bằng một BFS cho mỗi binh sĩ theo thứ tự. Dừng ở binh sĩ đầu tiên không thể tới vị trí bắn tháp được giao và báo số tháp đã bắn trước đó. Mọi chiến lược phá số tháp cực đại có thể mở rộng thành một phép ghép giữa toàn bộ binh sĩ và tháp, nên cách biểu diễn này bao phủ mọi khả năng.

Ngoài ô trống và tường thông thường, một số ô có thể đi vào nhưng không thể đi ra: các ô nằm trong tầm nhìn của những tháp sẽ bị một binh sĩ sau binh sĩ hiện tại phá. Mỗi BFS mất \(O(RC)\).

Không thể vét cạn chiến lược: có tới \(10!\) phép ghép và \(10!\) thứ tự, tức \((10!)^2\) chiến lược. Ta dùng tiền xử lý để tăng tốc kiểm tra và DP để sinh chiến lược.

Gọi \(S\) là số binh sĩ và \(T\) là số tháp. Với mỗi binh sĩ và mỗi tập con tháp còn sống, tiền xử lý tập tháp cô ấy có thể tới vị trí bắn bằng BFS. Cần tối đa \(2^T S\) BFS, tổng \(O(2^TSRC)\).

Đặt \(f(s,t)\) là chiến lược phá nhiều tháp nhất với tập binh sĩ còn lại \(s\) và tập tháp còn lại \(t\), hoặc báo không tồn tại. Hai tập được biểu diễn bằng bitmask nên có tối đa \(2^{S+T}\) trạng thái. Ở mỗi trạng thái, thử từng binh sĩ với từng tháp đang tới được; danh sách đã tiền xử lý nên mất tối đa \(ST\) phép thử. DP có ghi nhớ tốn \(O(2^{S+T}ST)\), thoải mái trong giới hạn nhỏ. Lưu lựa chọn chuyển trạng thái để dựng thứ tự output.

Test Set 2: đồ thị hai phía

Mọi cách mũ đều không phù hợp Test Set 2. Ta vẫn dùng BFS để kiểm tra khả năng tới tháp, nhưng cần thêm các nhận xét.

Dựng đồ thị hai phía \(G\) có một đỉnh cho mỗi binh sĩ và mỗi tháp. Có cạnh \((s,t)\) khi và chỉ khi binh sĩ \(s\) có thể phá tháp \(t\) sau khi mọi tháp khác đã bị phá. Một BFS từ mỗi binh sĩ dựng được \(G\).

Ta khẳng định có thể phá \(Q\) tháp khi và chỉ khi \(G\) có một matching phủ \(Q\) tháp. Chiều “chỉ khi” hiển nhiên vì điều kiện tạo cạnh là nới lỏng điều kiện thực tế của chiến lược. Phần còn lại là chứng minh chiều “nếu”; chứng minh mang tính xây dựng và chính là thuật toán.

Nếu \(G\) rỗng thì kết luận hiển nhiên. Nếu không, dùng Ford–Fulkerson tìm matching cực đại ban đầu \(M\) kích thước \(Q\). Chỉ giữ các binh sĩ xuất hiện trong \(M\), bỏ những binh sĩ không được ghép. Từ đây mọi binh sĩ được nói tới đều thuộc matching.

Ở trạng thái hiện tại, dựng \(G'\) trên cùng tập đỉnh nhưng chỉ giữ cạnh \((s,t)\) nếu \(s\) có thể phá \(t\) ngay lúc này, khi các tháp khác còn hoạt động. Rõ ràng \(G'\subseteq G\). Mỗi binh sĩ trong \(M\) có ít nhất một cạnh ra trong \(G'\): nếu cạnh \((s,t)\) của \(G\) chưa có trong \(G'\), một tháp khác \(t'\) đang chặn đường tới \(t\) phải là tháp mà \(s\) có thể tới và bắn ngay, nên \((s,t')\in G'\).

Tạo đồ thị có hướng \(H\) là hợp của các cạnh \(G'\) đi từ binh sĩ sang tháp và các cạnh matching \(M\) đảo chiều đi từ tháp sang binh sĩ.

Nếu \(H\) có cạnh \((s,t')\) tới một tháp \(t'\) chưa được \(M\) phủ, thay cạnh \((s,t)\) đang ghép \(s\) trong \(M\) bằng \((s,t')\). Matching mới \(M'\) vẫn cực đại và cùng kích thước.

Nếu không có cạnh như vậy, mọi binh sĩ có bậc ra ít nhất 1 nhờ \(G'\), và mọi tháp được ghép có bậc ra ít nhất 1 nhờ cạnh đảo của \(M\). Bắt đầu từ bất kỳ binh sĩ nào và đi theo cạnh, cuối cùng phải gặp một chu trình \(C\). Cạnh ra khỏi tháp chỉ là cạnh matching đảo, nên \(C\) luân phiên giữa cạnh đảo của \(M\) và cạnh của \(G'\). Lật matching dọc chu trình: giữ các cạnh \(M\) không thuộc chu trình và thay các cạnh matching trên chu trình bằng các cạnh \(G'\) xen kẽ. Ta thu được matching \(M'\) cùng kích thước; nếu chu trình dài 2 thì \(M'=M\).

Trong cả hai trường hợp, ta xây được matching cùng kích thước có ít nhất một cạnh thuộc \(G'\), tức có ít nhất một hành động có thể thực hiện ngay. Thực hiện tất cả \(A\ge1\) hành động matching đang khả thi, xóa \(A\) binh sĩ và \(A\) tháp đã dùng. Phần matching còn lại có kích thước \(Q-A\) trong đồ thị nhỏ hơn. Lặp đến khi rỗng. Bất biến này chứng minh mọi matching kích thước \(Q\) trong \(G\) đều chuyển thành chiến lược phá đủ \(Q\) tháp theo một thứ tự hợp lệ.

Độ phức tạp

Dựng \(G\) bằng \(S\) BFS tốn \(O(SRC)\). Tìm matching ban đầu bằng Ford–Fulkerson tốn \(O((S+T)^3)\); có thuật toán matching nhanh hơn nhưng cách này quen thuộc, dễ cài đặt và đủ dùng.

Có nhiều nhất \(T\) vòng sửa matching và xóa đỉnh. Mỗi vòng dựng \(G'\) bằng tối đa \(S\) BFS, tốn \(O(SRC)\); các thao tác còn lại tuyến tính theo kích thước \(G,G',H\), đều không quá \(O((S+T)^2)\) và nhỏ hơn phần BFS. Tổng là

Còn có thể cải thiện: mỗi lần dựng lại \(G'\), BFS chỉ tới cùng những nơi cũ hoặc xa hơn do tháp dần bị phá. Nếu ghi nhớ các BFS và tiếp tục từ nơi từng dừng thay vì khởi động lại, tổng chi phí dựng \(G'\) giảm một hệ số \(T\) xuống \(O(SRC)\). Độ phức tạp cuối là

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2017, Round 2, bài Shoot the Turrets; kho Google Coding Competitions (Apache-2.0).