Phân tích: Paradox Sort

Chúng ta có thể xem tập hợp các sở thích như một đồ thị có hướng. Mỗi viên kẹo là một nút trong đồ thị, và nếu Vlad thích kẹo \(X\) hơn kẹo \(Y\), sẽ có một cạnh có hướng từ nút \(X\) đến nút \(Y\).

Đầu tiên, chúng ta mô tả quy trình để xác định xem có tồn tại bất kỳ hoán vị hợp lệ nào không, sau đó mô tả quy trình tìm hoán vị có thứ tự từ điển nhỏ nhất.

Kiểm tra tính khả thi của hoán vị

Để trả lời câu hỏi này, chúng ta sử dụng tìm kiếm theo chiều sâu (DFS) trên đồ thị mô tả ở trên. Sử dụng \(A\), viên kẹo mục tiêu, làm gốc của tìm kiếm. Một hoán vị hợp lệ tồn tại khi và chỉ khi chúng ta có thể đi thăm tất cả các viên kẹo khác từ gốc \(A\). Nếu không, không có hoán vị hợp lệ. Tại sao lại như vậy?

Nếu tất cả các viên kẹo đều được thăm trong DFS, chúng ta có một cây có hướng gốc tại \(A\) chứa tất cả các nút. Khi đó, chúng ta có thể tạo ra một hoán vị hợp lệ bằng cách in các nút theo thứ tự duyệt hậu thứ tự (post-order traversal) của cây.

Trong hoán vị đó, \(A\) là viên kẹo cuối cùng được đưa cho Vlad, và Vlad sẽ giữ nó. Để hiểu tại sao, hãy xem xét cây DFS. Giả sử \(X\) là viên kẹo Vlad đang giữ trước khi nhận kẹo \(A\). \(X\) phải được thích hơn mọi viên kẹo nằm giữa \(X\) và \(A\) trong thứ tự duyệt hậu thứ tự. Nếu \(X\) không phải là con của \(A\), thì một trong những viên kẹo đó phải là cha của \(X\) trong cây, viên kẹo mà Vlad sẽ thích hơn \(X\). Do đó \(X\) phải là con của kẹo \(A\) trong DFS, vì vậy anh ấy sẽ chọn giữ \(A\) khi được đưa nó.

Ví dụ cho trường hợp sau:

4 1
-YNY
N-YN
YN-N
NYY-

Thứ tự duyệt hậu thứ tự cho ta hoán vị 3, 2, 4, 1, đây là một thứ tự hợp lệ để kẹo 1 thắng cuối cùng.

Ngược lại, nếu có một kẹo \(X\) không thể thăm được từ \(A\) bằng DFS, thì không có hoán vị nào hợp lệ. Giả sử Vlad kết thúc với \(A\). Xét danh sách các viên kẹo mà Vlad giữ qua từng bước. Nếu \(X\) xuất hiện trong hoán vị, tại thời điểm đưa \(X\), Vlad sẽ giữ \(X\) hoặc một kẹo \(Y\) mà anh ấy thích hơn \(X\). Nếu cuối cùng Vlad giữ \(A\), phải có một chuỗi các kẹo từ \(Y\) đến \(A\) sao cho kẹo sau được thích hơn kẹo trước. Điều này có nghĩa là phải có đường đi từ \(A\) đến \(X\), mâu thuẫn với việc \(X\) không thăm được từ \(A\).

Kiểm tra các lời giải riêng phần hợp lệ

Chúng ta sử dụng chiến lược tham lam để tìm hoán vị có thứ tự từ điển nhỏ nhất. Tại mỗi bước, ta cần kiểm tra xem một tiền tố (danh sách kẹo đã chọn) có thể được mở rộng thành một hoán vị hợp lệ hay không. Giả sử kẹo hiện tại Vlad đang giữ là \(B\) (có thể là \(A\)). Ta loại bỏ các kẹo đã chọn khỏi đồ thị (ngoại trừ \(B\)).

Nếu \(A\) đã bị loại bỏ trước đó mà không phải là kẹo cuối cùng, điều đó là không thể. Nếu \(A\) chưa bị loại bỏ:

1. Nếu \(B = A\): \(A\) phải thích hơn tất cả các kẹo còn lại để Vlad giữ được \(A\) đến cuối cùng.
2. Nếu \(B \neq A\): Chúng ta không thể dùng trực tiếp DFS từ \(A\) vì \(B\) đã được Vlad giữ, nên các nút "phía sau" \(B\) không thể xuất hiện trước \(B\) trong hoán vị.

Quy trình kiểm tra như sau:

1. Thực hiện DFS từ \(A\) trên các nút còn lại, nhưng khi gặp \(B\), không đi tiếp các cạnh từ \(B\).
2. Với mỗi nút \(X\) chưa được thăm, nếu có cạnh từ \(B\) đến \(X\), thêm \(X\) làm con của \(B\).
3. Nếu tất cả các nút còn lại đều được đưa vào cây, tiền tố đó hợp lệ.

Tìm hoán vị có thứ tự từ điển nhỏ nhất

Bắt đầu với tiền tố rỗng, lặp lại việc thêm viên kẹo có số hiệu nhỏ nhất chưa dùng sao cho tiền tố mới vẫn hợp lệ theo kiểm tra ở trên.

Mã giả:

Let P = []  // The partial solution

If !IsValidPartialSolution(P)
  return IMPOSSIBLE

Repeat N times
  For i = 1 to N
    // Test if appending i to P gives a valid partial solution
    If P.contains(i) is false
      If IsValidPartialSolution(P + [i]) is true
        P = P + [i]
        Break

Return P

Cài đặt tham khảo bằng Python 3:

def dfs(i, removed, visited):
  visited.add(i)
  for j in range(len(prefer[i])):
    if prefer[i][j] == 'Y':
      if j not in visited and j not in removed:
        dfs(j, removed, visited)


def valid(partial):
  B = partial[0]
  for i in partial:
    if prefer[i][B] == 'Y':
      B = i

  removed = set(partial)
  removed.remove(B)

  # Trivial case.
  if A in removed: return False

  # Case (i)
  if A == B:
    for i in range(N):
      if i != A and i not in removed:
        if prefer[A][i] != 'Y':
          return False
    return True

  # Case (ii)
  visited = set([B])
  dfs(A, removed, visited)
  for i in range(len(prefer[B])):
    if prefer[B][i] == 'Y':
      visited.add(i)
  return len(visited.union(removed)) == N


def solve():
  visited = set()
  dfs(A, set(), visited)
  if len(visited) != N: return "IMPOSSIBLE"

  partial = []
  for i in range(N):
    for j in range(N):
      if j not in partial and valid(partial + [j]):
        partial = partial + [j]
        break
  return ' '.join(map(str, partial))


for tc in range(int(input())):
  [N, A] = map(int, input().split())
  prefer = []
  for i in range(N):
    prefer.append(input())
  print("Case #%d: %s" % (tc + 1, solve()))

Dựa trên phân tích chính thức của Google Code Jam.