Phân tích: Checkerboard Matrix

Hãy bắt đầu bằng cách đưa ra một số quan sát về ma trận bàn cờ:

• Vì ma trận có kích thước \(2N \times 2N\), nên mỗi hàng và mỗi cột đều có số lượng số 0 và số 1 bằng nhau (mỗi loại có \(N\) số).
• Các góc của bất kỳ hình chữ nhật con nào trong ma trận bàn cờ luôn có hai số 0 và hai số 1, hoặc bốn số giống nhau (tổng số 1 ở 4 góc luôn là số chẵn). Cụ thể hơn, nếu ta lấy bất kỳ ma trận con nào có ít nhất 2 hàng và 2 cột, số lượng số 0 và số 1 ở bốn góc của nó sẽ luôn là số chẵn.

Dưới đây là ví dụ về một ma trận bàn cờ và hai ma trận con mẫu (được viền đỏ): một ma trận con có bốn số 1 ở các góc và không có số 0 nào, ma trận còn lại có hai số 1 và hai số 0 ở các góc.

Bây giờ, hãy phân tích điều gì xảy ra khi chúng ta hoán đổi 2 hàng hoặc 2 cột. Thao tác này không làm thay đổi số lượng số 0 và 1 trong một hàng hoặc cột. Quan trọng hơn, tính chất về số lượng số 0 và 1 chẵn ở các góc của bất kỳ ma trận con nào vẫn được giữ nguyên. Điều này có nghĩa là bất kỳ ma trận nào không thỏa mãn các tính chất trên đều không thể biến đổi thành ma trận bàn cờ.

Xét một ma trận thỏa mãn các tính chất trên, hãy xem xét một cặp hàng (lập luận tương tự cho các cột). Ta có thể chứng minh rằng tất cả các hàng bắt đầu bằng 1 sẽ thực sự giống hệt nhau, và tất cả các hàng bắt đầu bằng 0 cũng vậy (gọi hai tập hợp hàng này là A và B). Ngoài ra, các số ở cùng một cột của hàng loại A và hàng loại B sẽ khác nhau. Do đó, các hàng loại A sẽ là nghịch đảo (bit-flip) của các hàng loại B.

Chứng minh: Xét hai hàng cùng loại (ví dụ cùng bắt đầu bằng 1). Chọn một ma trận con có 2 góc nằm ở cột đầu tiên và 2 góc còn lại ở một cột bất kỳ khác. Theo định nghĩa loại hàng, 2 góc ở cột đầu tiên bằng nhau. Để tổng số 1 ở 4 góc là số chẵn, 2 góc ở cột còn lại cũng phải bằng nhau. Do đó, mọi vị trí tương ứng của các hàng cùng loại phải giống nhau. Tương tự, ta chứng minh được hàng loại A và B là nghịch đảo của nhau. Vì trong ma trận bàn cờ, mỗi hàng và cột có số lượng 0 và 1 bằng nhau, nên số lượng hàng mỗi loại phải bằng nhau (bằng \(N\)).

Dưới đây là ví dụ về một ma trận thu được bằng cách hoán vị các hàng và cột của một ma trận bàn cờ:

Trong một ma trận bàn cờ, các hàng (và cột) loại A và loại B phải xen kẽ nhau. Lưu ý rằng các phép biến đổi hàng và cột là độc lập. Ta có thể tìm số lần hoán đổi hàng tối ưu, sau đó là số lần hoán đổi cột tối ưu, rồi cộng chúng lại.

Bài toán trở thành: Cho một dãy gồm các ký tự 'A' và 'B' với số lượng bằng nhau, hãy hoán đổi các cặp phần tử để 'A' và 'B' xen kẽ nhau. Có 2 cấu trúc mục tiêu: ABAB... hoặc BABA.... Với mỗi cấu trúc, số lần hoán đổi tối thiểu bằng một nửa số vị trí bị sai (vì mỗi lần hoán đổi đúng chỗ được 2 vị trí).

Thuật toán

1. Gán hàng đầu tiên là loại A.
2. Duyệt qua tất cả các hàng và so sánh từng phần tử với hàng đầu tiên:
3. Nếu hàng đó giống hệt hàng đầu tiên, nó thuộc loại A.
4. Nếu hàng đó là nghịch đảo của hàng đầu tiên, nó thuộc loại B.
5. Nếu không rơi vào hai trường hợp trên, xuất "IMPOSSIBLE".
6. Kiểm tra xem số lượng hàng loại A và loại B có bằng nhau không (\(= N\)). Nếu không, xuất "IMPOSSIBLE".
7. Số lần hoán đổi hàng tối thiểu là \(\min(count\_wrong\_A, count\_wrong\_B) / 2\), trong đó \(count\_wrong\_X\) là số vị trí không khớp khi giả định hàng đầu tiên của bàn cờ mục tiêu là loại X. (Lưu ý: chỉ đếm các vị trí sai loại hàng, ví dụ nếu mục tiêu là ABAB mà hiện tại là BAAB thì có 2 vị trí sai).
8. Lặp lại các bước 1-4 cho các cột.
9. Kết quả là tổng số lần hoán đổi hàng và cột tối thiểu.

Cài đặt mẫu (Python 3)

def count_swaps(pos):
  nswaps = 0
  for i in pos:
    if i % 2 == 0:
      nswaps = nswaps + 1
  return nswaps


def inverse(A):
  return [chr(ord('0') + ord('1') - ord(c)) for c in A]

# min_swaps returns minimum swaps required to 
# form alternating rows. If B is an invalid matrix, 
# returns -1 to denote an impossible case.
def min_swaps(M, N):
  # Step 1.
  typeA = M[0]
  typeB = inverse(typeA)

  pos_A = []
  pos_B = []
  for i in range(2 * N):
    # Step 2 a.
    if M[i] == typeA:
      pos_A.append(i)
    # Step 2 b.
    elif M[i] == typeB:
      pos_B.append(i)
    # Step 2 c.
    else:
      return -1
  # Step 3.
  if len(pos_A) != len(pos_B):
    return -1

  # Step 4.
  return min(count_swaps(pos_A), count_swaps(pos_B))


def solve(M, N):
  # Step 1-4.
  row_swaps = min_swaps(M, N)
  if row_swaps == -1:
    return "IMPOSSIBLE"

  Mt = [list(i) for i in zip(*M)]  # Transpose matrix M

  # Step 5.
  col_swaps = min_swaps(Mt, N)
  if col_swaps == -1:
    return "IMPOSSIBLE"

  return row_swaps + col_swaps


for tc in range(int(input())):
  N = int(input())
  M = []
  for i in range(2 * N):
    M.append(list(input()))
  print("Case #%d: %s" % (tc + 1, solve(M, N)))

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