Phân loại trạng thái

Cách duy nhất khiến ta không trở thành Kiếm Sư là mắc kẹt ở trạng thái mà với mọi kiếm sĩ còn lại — những người chưa bị ta đánh bại — ta không thể thắng nếu không học thêm kỹ năng. Tại mọi thời điểm, chia các kiếm sĩ còn lại thành bốn nhóm:

1. D1: những người ta chắc chắn đánh bại được.
2. D2: những người có một đòn công ta không đỡ được và có thế thủ cho mọi đòn công của ta.
3. D3: những người thiếu thế thủ cho ít nhất một đòn công của ta, nhưng có một đòn công ta không đỡ được.
4. D4: những người không có đòn công nào ta không đỡ được, nhưng có thế thủ cho mọi đòn công của ta.

Nếu còn người trong D1, ta chỉ việc đánh bại họ. Nếu có người trong D3 và người trong D4, ta có thể tiến triển — giảm số đối thủ còn lại hoặc chuyển một người sang D1 — như sau:

1. Chọn bất kỳ \(A\in D3\) và \(B\in D4\).
2. Đấu với \(A\). Vì \(A\in D3\), họ có một đòn ta không đỡ được. Hoặc \(A\) dùng một đòn như vậy và ta học đòn đó, hoặc ta đỡ được đòn họ dùng và thắng, từ đó học toàn bộ đòn công của \(A\). Sau trận, ta học được một đòn công \(a\) mà mình chưa có thế thủ tương ứng.
3. Nếu \(B\) không đỡ được \(a\), \(B\) đã chuyển sang D1 và ta có tiến triển. Nếu \(B\) đỡ được, đấu với \(B\) và dùng \(a\). Nếu \(B\) không phòng thủ, ta thắng. Nếu \(B\) phòng thủ, ta học thế thủ \(a\).
4. Khi đã học thủ \(a\), \(A\) có thể chuyển sang D1, hoặc vẫn ở D3 vì còn một đòn khác ta chưa đỡ được. Nếu \(A\) vào D1, ta có tiến triển; nếu không, lặp bước 2 cho đến khi \(A\) không còn đòn nào ta chưa đỡ được.

Vì thế, các trạng thái duy nhất có thể khiến ta thất bại là: mọi kiếm sĩ còn lại đều thuộc D2 hoặc D3; hoặc mọi người đều thuộc D2 hoặc D4.

Trường hợp D2/D3 và tập \(G_1\)

Nếu mọi người còn lại thuộc D2 hoặc D3, mỗi người đều có một đòn ta không đỡ được. Từ đó, họ luôn có thể dùng một đòn ta không đỡ được và chọn không phòng thủ; ta sẽ không học thế thủ mới. Vì vậy ta không thể thắng thêm ai và chắc chắn thất bại.

Thực ra có thể phát hiện tình huống này ngay từ đầu. Nếu tồn tại một nhóm kiếm sĩ \(G_1\) không chứa ta, sao cho mỗi người trong \(G_1\) có ít nhất một đòn mà không ai ngoài \(G_1\) đỡ được, thì ta chắc chắn thua. Chiến lược của họ là mỗi người trong \(G_1\) cứ tấn công trúng ta và không phòng thủ; nhờ vậy ta không học được thế thủ mới nào mà người trong \(G_1\) biết.

Để kiểm tra \(G_1\), bắt đầu với \(G'_1\) gồm mọi kiếm sĩ trừ ta. Lặp lại việc xóa khỏi \(G'_1\) bất kỳ người nào mà ta có thể đỡ mọi đòn, đồng thời thu nhận toàn bộ thế thủ của người đó. Quy trình chạy trong \(O(NP)\). Độ phức tạp này cũng bị chặn bởi tổng số đòn công và thế thủ mọi người biết, tức tuyến tính theo kích thước dữ liệu vào.

Test Set 1

Trong bộ 1, trường hợp mọi người còn lại thuộc D2 hoặc D4 là đối xứng. Mọi người còn lại đều đỡ được mọi đòn của ta. Do đó tồn tại nhóm \(G_2\) không chứa ta, sao cho mỗi người trong \(G_2\) có thế thủ cho mọi đòn công có sẵn ngoài \(G_2\). Ta cũng chắc chắn thua: mọi người trong \(G_2\) luôn đỡ đòn của ta và luôn dùng công \(1\), nên ta không học được đòn công mới nào mà người trong \(G_2\) biết.

Có thể kiểm tra trước sự tồn tại của \(G_2\) bằng thuật toán tương tự phép kiểm tra \(G_1\).

Test Set 2

Trong bộ 2, trường hợp mọi người còn lại thuộc D2 hoặc D4 phức tạp hơn. Khác biệt là đối thủ bắt buộc phải tấn công, nên ngay cả khi đấu người đỡ được mọi đòn của ta, ta vẫn có thể học một đòn công mới. Đòn mới có thể chuyển một người từ D4 sang D1 hoặc từ D2 sang D3. Vì vậy, chỉ biết mọi người thuộc D2/D4 chưa đủ kết luận thất bại.

Hãy hình dung một trạng thái ta thật sự hết đường: cuối cùng mọi người còn lại thuộc D2/D4, ta sẽ không bao giờ thắng thêm ai và cũng không học thêm công hoặc thủ. Trạng thái như vậy phải xuất hiện sau hữu hạn thời gian, vì chỉ có hữu hạn kỹ năng để học. Ở đó, ta có thể đấu một trận với từng người còn lại và học các đòn họ dùng. Theo định nghĩa, ta đã biết sẵn mọi đòn ấy; cũng theo định nghĩa, mọi đối thủ đều đỡ được tất cả chúng.

Vì vậy, để ta bị kẹt theo nhánh này, phải tồn tại một nhóm kiếm sĩ \(G_2\) và một phép chọn cho mỗi người một đòn công

sao cho mỗi kiếm sĩ \(d\in G_2\) biết \(a(d)\), đồng thời biết cách đỡ mọi đòn được biết bên ngoài \(G_2\) và mọi đòn \(a(d')\) với \(d'\in G_2\).

Điều kiện này khó kiểm tra hơn. Giả sử \(G_2\) tồn tại. Với hai kiếm sĩ \(X,Y\), nếu \(X\) có một đòn mà \(Y\) không đỡ được, thì \(Y\in G_2\) kéo theo \(X\in G_2\). Quan hệ đó định nghĩa đồ thị có hướng trên các kiếm sĩ, với cạnh từ \(Y\) đến \(X\).

Tìm các thành phần liên thông mạnh (SCC) của đồ thị. Nếu một người trong SCC thuộc \(G_2\), toàn bộ SCC phải thuộc \(G_2\). Do đó \(G_2\) là một tập đóng phía trên — không có cạnh đi từ tập ra ngoài — trong DAG co các SCC. Nếu một tập đóng phía trên là \(G_2\) hợp lệ, thì mọi tập con của nó vẫn đóng phía trên cũng là \(G_2\) hợp lệ với cùng cách chọn đòn. Vì thế chỉ cần kiểm tra các SCC lá của DAG: nếu có \(G_2\) hợp lệ bất kỳ, cũng tồn tại một \(G_2\) là SCC lá.

Với mỗi SCC lá, kiểm tra xem mỗi kiếm sĩ trong SCC có thể chọn một đòn mà mọi người trong SCC đều đỡ được hay không. Trước hết lấy giao \(D\) của các tập thế thủ mà mọi kiếm sĩ trong SCC biết; sau đó kiểm tra mỗi kiếm sĩ có ít nhất một đòn công thuộc \(D\).

Để dựng đồ thị trong \(O(NP)\), có thể thêm cả các đỉnh đại diện đòn công. Thêm cạnh từ kiếm sĩ đến đòn công nếu kiếm sĩ đó không đỡ được đòn ấy; thêm cạnh từ đòn công đến kiếm sĩ nếu kiếm sĩ biết đòn đó. Toàn bộ lời giải chạy trong \(O(NP)\).

Nội dung trên được chuyển ngữ đầy đủ từ phân tích chính thức của Google Code Jam 2018, Chung kết thế giới, bài Swordmaster.