Các bất biến cơ bản

Bài này đòi hỏi khá nhiều suy nghĩ, nhưng cuối cùng lại cần tương đối ít mã nguồn.

Gọi \(S\) là số chất xuất hiện trong toàn bộ bộ bài. Với mỗi chất, gọi lá có giá trị lớn nhất là ace, và lá lớn thứ hai (nếu có) là king. Một lá bài là đang lộ nếu nó nằm trên đỉnh một chồng; một chất là đang lộ nếu có ít nhất một lá của chất đó đang lộ.

Một khi một chất đã lộ, nó sẽ lộ mãi: khi bỏ một lá đang lộ, hoặc một lá cùng chất khác vẫn đang lộ, hoặc ta vừa làm lộ lá tiếp theo của chính chất đó. Nếu đang có đúng \(N\) chất lộ, ta hoặc đã thắng, hoặc không còn nước đi và thua. Nếu có ít hơn \(N\) chất lộ, ta hoặc đã thắng, hoặc vẫn đi được: có hai lá cùng chất đang lộ để bỏ lá nhỏ hơn, hoặc có một chồng rỗng để chuyển bài.

Do đó:

• nếu \(S<N\), luôn có thể thắng bất kể lựa chọn;
• nếu \(S>N\), không thể thắng, vì không bao giờ loại được lá cuối cùng của một chất;
• chỉ \(S=N\) là trường hợp đáng xét. Khi đó trạng thái thắng có đúng một ace của mỗi chất trong mỗi chồng.

Việc bỏ một lá hợp lệ không bao giờ gây bất lợi; lựa chọn thực sự duy nhất là chuyển lá nào vào chồng rỗng. Vì vậy ta tiền xử lý bằng cách bỏ mọi lá đang bỏ được. Nếu đã thắng thì trả lời POSSIBLE; nếu chưa thắng và không có chồng rỗng thì IMPOSSIBLE. Từ đây giả sử có một chồng rỗng.

Điều kiện cần từ nước đi cuối

Giả sử tồn tại một ván thắng và xét nước đi cuối. Ngay trước nước đó ta chưa thắng nhưng còn đi được, nên có ít hơn \(N\) chất lộ. Nước cuối phải làm lộ lần đầu một chất mới. Chất này chỉ có đúng một lá, và lá đó đã nằm ở đáy chồng ngay từ đầu. Đây là nguồn gốc của khái niệm source bên dưới.

Ở cuối ván, mỗi chồng chứa một ace. Khi một ace đã được chuyển xuống đáy chồng rỗng, nó không bao giờ bị che lại. Bởi vậy trước hành động thắng cuối, \(N-1\) ace đã ở đáy các chồng và hành động cuối là chuyển ace còn lại vào chồng rỗng. Một số ace đã lộ trước nước cuối; các chất ấy không còn đáng quan tâm, vì nếu ta làm lộ thêm lá cùng chất thì ace đang lộ cho phép bỏ lá đó ngay. Những ace chưa lộ ở thời điểm đó mới là phần quan trọng: chúng phải vốn nằm dưới đáy từ ban đầu, vì ace một khi đã lộ không thể bị che lại; toàn bộ bài che phía trên chúng cũng phải ở nguyên trong chồng ấy từ đầu. Do đó chỉ cần tìm đường source–target trong trạng thái ngay trước nước cuối, vì đường đó chắc chắn đã tồn tại từ trạng thái ban đầu.

Đồ thị các chất

Tạo một đỉnh cho mỗi chất có ace nằm ở đáy một chồng ban đầu.

• Đỉnh \(s\) là source nếu ace là lá duy nhất của chất \(s\).
• Đỉnh \(s\) là target nếu trong chồng có ace của \(s\) ở đáy còn có một ace của chất khác.
• Thêm cạnh \(s_1\to s_2\) nếu king của \(s_2\) nằm trong chồng có ace của \(s_1\) ở đáy.

Ta chứng minh trò chơi thắng được khi và chỉ khi đồ thị có một đường đi từ source tới target.

Đường đi là điều kiện đủ

Để hiểu điều kiện này, trước hết xét trường hợp đơn giản trong đó đường đi chỉ gồm một cạnh từ source \(s_1\) tới target \(s_2\). Chất \(s_1\) có đúng một lá — ace ở đáy chồng \(A\) — và king của \(s_2\) cũng nằm trong \(A\). Để \(s_1\) là source nhưng không đồng thời là target, giả sử \(A\) không chứa ace nào khác. Để \(s_2\) là target, giả sử ace của nó ở đáy một chồng khác \(B\), còn ace của chất thứ ba \(s_3\) nằm cao hơn trong \(B\); ta chọn ace \(s_3\) là ace gần đáy nhất ngoài chính lá dưới cùng của \(B\) (tức ace thấp thứ hai trong \(B\)).

Liên tục thực hiện các nước hợp lệ nhưng chưa làm lộ ace của \(s_1\), cho đến khi nước hợp lệ cần thực hiện còn lại là chuyển ace \(s_3\) vào một chồng rỗng. Trạng thái này luôn đạt được vì khi chưa lộ ace của \(s_1\) thì vẫn có ít hơn \(N\) chất lộ. Lúc đó, cả ba sự kiện sau đều đúng:

• Có một chồng rỗng. Nếu không, vì \(s_1\) chưa lộ nên \(N\) lá trên đỉnh chỉ thuộc nhiều nhất \(N-1\) chất; phải có hai lá lộ cùng chất và ta vẫn có thể bỏ lá nhỏ hơn.
• \(A\) và \(B\) là hai chồng duy nhất có nhiều hơn một lá. Nếu một chồng khác cũng còn nhiều lá, ta vẫn có thể chuyển lá trên cùng của nó vào chồng rỗng.
• Mỗi chồng trong \(N-3\) chồng còn lại — ngoài \(A\), \(B\) và chồng rỗng vừa nói — chứa đúng ace của một trong \(N-3\) chất còn lại. Các ace không thể đã bị bỏ, và chúng cũng không nằm trong \(A\) hay \(B\).

Chuyển ace \(s_3\) sang chồng rỗng rồi dọn chồng \(B\) tới ace \(s_2\). Mọi lá chắn hoặc thuộc \(s_2\) và nhỏ hơn king đang lộ, hoặc thuộc chất khác có ace đang lộ, nên đều bỏ được. Sau đó bỏ king \(s_2\) và dọn \(A\) tới ace \(s_1\): lúc này ace của mọi chất ngoài \(s_1\) đều đang lộ, còn chất \(s_1\) vốn không có lá nào khác, nên mọi lá chắn trong \(A\) đều bỏ được. Ta thắng. Với đường dài hơn, trước hết dọn mọi thứ ngoại trừ các ace được nhắc đến trên đường đi, sau đó chuyển ace ở cuối đường vào chồng rỗng và bỏ lần lượt toàn bộ các lá còn lại; lập luận hoàn toàn tương tự.

Đường đi là điều kiện cần

Xét trạng thái ngay trước nước thắng cuối. Trước hết, các lá trên đỉnh những chồng còn nhiều lá phải thuộc chính tập các chất có ace đang bị che; nếu thuộc một chất có ace đã lộ thì chúng đã bị bỏ ngay. Ta sẽ chứng minh rằng mỗi lá trên đỉnh ấy đều là king.

Giả sử ngược lại một lá trên đỉnh chỉ là lá thấp hơn, chẳng hạn queen của chất \(x\). Vì queen đang lộ mà chưa bị bỏ, king của \(x\) phải còn nằm đâu đó trong một chồng và chưa lộ. King cũng không thể đã bị bỏ: để bỏ được king thì ace của \(x\) phải lộ, và khi đó queen đang lộ cũng đã bị bỏ.

Nếu chuyển queen vào chồng rỗng, ta kích hoạt một chuỗi bỏ bài tất định. Chuỗi không thể kết thúc bằng việc bỏ queen, nếu không ta đã có thêm một nước không phải nước thắng; vì vậy nó phải kết thúc bằng việc làm lộ ace của chất còn thiếu và khiến ta thua. Bây giờ thực hiện nước thắng thật: sau mỗi lần bỏ trung gian chỉ có \(N-1\) chất lộ nên lựa chọn tiếp theo là duy nhất. Chuỗi cuối cùng sẽ làm lộ king hoặc ace của \(x\) — lá nào xuất hiện trước — rồi bỏ queen và lặp đúng chuỗi tất định vừa nói. Lá cao còn lại của chất \(x\) (lá còn lại trong hai lá king và ace) không thể đồng thời được lộ trong chuỗi này: nếu có, ở kịch bản chuyển queen nó đã khiến queen bị bỏ sớm hơn. Vì thế cuối cùng vẫn còn ít nhất một lá không lộ, mâu thuẫn với việc thắng.

Vậy các lá trên những ace bị che đều là king. Bắt đầu từ source do nước cuối xác định và lần theo chất của các king; vì hữu hạn, ta đi tới chồng chứa hai ace, tức một target. Đường source–target đã có ngay từ trạng thái ban đầu.

Thuật toán và độ phức tạp

Tính ace/king, vị trí đáy và chồng chứa từng lá, dựng đồ thị rồi DFS/BFS đa nguồn từ mọi source để xem có tới target hay không. Việc dựng dữ liệu và duyệt đồ thị đều tuyến tính theo số lá cộng số chất (hoặc \(O(NC)\) nếu quét trực tiếp mọi chồng). Bộ nhỏ cũng có thể backtracking trên các nước đi, nhưng không đủ cho bộ lớn.

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2017, World Finals, bài Stack Management; kho Google Coding Competitions (Apache-2.0).