Phân tích: Power Swapper

Quan sát thấy rằng một thao tác hoán đổi kích thước \(2^x\) có thể được thực hiện độc lập với thao tác hoán đổi kích thước \(2^y\). Do đó, chúng ta có thể đơn giản hóa quá trình sắp xếp bằng cách thực hiện các lần hoán đổi từ kích thước nhỏ nhất đến kích thước lớn nhất và giả định rằng khi thực hiện hoán đổi kích thước \(2^z\), các số liền kề bên trong nó đã được sắp xếp hoàn toàn (bởi các lần hoán đổi kích thước nhỏ hơn trước đó). Ở đây, "sắp xếp hoàn toàn" có nghĩa là các số liền kề tăng dần liên tiếp (tức là mỗi số lớn hơn số trước đó đúng 1 đơn vị).

Hãy xem xét các lần hoán đổi có thể có cho phần tử kích thước \(2^k\) nhỏ nhất với \(k = 0\) (tức là hoán đổi hai tập hợp kích thước 1). Có \(2^N\) tập hợp hợp lệ kích thước 1. Tuy nhiên, chúng ta chỉ quan tâm đến việc hoán đổi hai tập hợp hợp lệ sao cho tất cả các tập hợp hợp lệ kích thước \(2^{k+1}\) đều được sắp xếp hoàn toàn. Điều này quan trọng vì khi hoán đổi các kích thước lớn hơn, chúng ta giả định các tập hợp hợp lệ kích thước nhỏ hơn đều đã được sắp xếp hoàn toàn. Hãy xem một số ví dụ:

• Hoán vị: 2 4 1 3. Cách duy nhất là hoán đổi 2 với 3, tạo ra 3 4 1 2, nơi tất cả các tập hợp hợp lệ kích thước \(2^1\) đều được sắp xếp hoàn toàn.
• Hoán vị: 1 4 3 2. Có hai cách để thực hiện hoán đổi sao cho tất cả các tập hợp hợp lệ kích thước \(2^1\) được sắp xếp hoàn toàn. Cách thứ nhất là hoán đổi 1 với 3 và cách kia là hoán đổi 4 với 2.
• Hoán vị: 1 4 3 2 6 5. Trong trường hợp này, có 3 tập hợp hợp lệ kích thước \(2^1\). Cần ít nhất hai lần hoán đổi để làm cho tất cả các tập hợp hợp lệ kích thước \(2^1\) được sắp xếp hoàn toàn. Do đó, không thể sắp xếp hoán vị này.

Từ các ví dụ trên, ta thấy chỉ cần xem xét việc hoán đổi tối đa hai tập hợp hợp lệ kích thước \(2^k\) cho \(k = 0\). Chúng ta có thể tổng quát hóa điều này cho \(k\) lớn hơn, giả sử tất cả các tập hợp hợp lệ có kích thước nhỏ hơn đã được sắp xếp hoàn toàn.

Để đếm số cách sắp xếp, chúng ta có thể sử dụng đệ quy (quay lui) để mô phỏng tất cả các lần hoán đổi khả thi. Trạng thái đệ quy bao gồm mảng hiện tại, giá trị \(k\), và số lượng phép hoán đổi đã thực hiện cho đến nay. Đệ quy bắt đầu từ các lần hoán đổi kích thước nhỏ nhất (\(k = 0\)) với mảng đầu vào ban đầu, sau đó nó quyết định tập hợp hợp lệ nào cần hoán đổi (nếu có) và đệ quy đến các lần hoán đổi lớn hơn (\(k + 1\)), và cứ tiếp tục như vậy cho đến khi đạt đến các lần hoán đổi kích thước lớn nhất (\(k = N\)).

Độ sâu của đệ quy tối đa là \(N\) và có tối đa hai nhánh cho mỗi trạng thái đệ quy (vì có tối đa hai lần hoán đổi khả thi cho mỗi kích thước) và mỗi trạng thái cần \(O(2^N)\) để thu thập tối đa hai tập hợp ứng viên hợp lệ cần hoán đổi. Do đó, thuật toán chạy trong \(O(2^{N \cdot 2})\). Khi đệ quy đạt đến độ sâu \(N\), nó sẽ có số lượng phép hoán đổi đã thực hiện. Vì thứ tự của các phép hoán đổi là quan trọng, số cách sẽ bằng giai thừa của số lượng phép hoán đổi. Chúng ta truyền số cách này ngược lên gốc để nhận giá trị cuối cùng.

Dưới đây là một ví dụ cài đặt bằng Python 3:

import math

def swap(arr, i, j, sz):  # Swap two sets.
  for k in range(sz):
    t = arr[i + k]
    arr[i + k] = arr[j + k]
    arr[j + k] = t

def count(arr, N, k, nswapped):
  if k == N:
    return math.factorial(nswapped)

  i = 0
  idx = []  # Candidates’ index for swappings.
  sz = 2**k
  while i < 2**N:
    if arr[i] + sz != arr[i + sz]:
      idx.append(i)
    i = i + sz * 2

  ret = 0
  if len(idx) == 0:  # No swap needed.
    ret = count(arr, N, k + 1, nswapped)

  elif len(idx) == 1:  # Only one choice to swap.
    swap(arr, idx[0], idx[0] + sz, sz)
    if arr[idx[0]] + sz == arr[idx[0] + sz]:
      ret = count(arr, N, k + 1, nswapped + 1)
    swap(arr, idx[0], idx[0] + sz, sz)

  elif len(idx) == 2:  # At most 2 choices.
    for i in [idx[0], idx[0] + sz]:
      for j in [idx[1], idx[1] + sz]:
        swap(arr, i, j, sz)
        if arr[idx[0]] + sz == arr[idx[0] + sz]:
          if arr[idx[1]] + sz == arr[idx[1] + sz]:
            ret = ret + count(arr, N, k + 1, nswapped + 1)
        swap(arr, i, j, sz)

  return ret


for tc in range(int(input())):
  N = int(input())
  arr = list(map(int, input().split()))
  print("Case #%d: %d" % (tc+1, count(arr, N, 0, 0)))

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