Phân tích

Trong một kỳ thi gồm nhiều bài toán lạ, bài này nổi bật vì có vẻ "bình thường" hơn các bài khác. Tuy nhiên, điều đó không có nghĩa là nó dễ! Các kỹ thuật chính ở đây là quy hoạch động và đếm tổ hợp cơ bản, nhưng bạn cần thành thạo chúng để có cơ hội giải quyết bài toán.

Quan sát quan trọng nhất là bạn không thể xây dựng chuỗi từ trái sang phải. Với \(450,000\) ký tự, có quá nhiều trạng thái cần lưu trữ. Cách tiếp cận đúng đắn là đặt tất cả các ký tự của một loại, sau đó đến loại tiếp theo, và cứ thế tiếp tục. Để thực hiện điều này, hãy gọi \(N_c\) là số lượng ký tự loại \(c\), và định nghĩa \(X_{c,r}\) là số cách sắp xếp tất cả các ký tự từ loại \(1, 2, \dots, c\) sao cho có đúng \(r\) runs. Chúng ta sẽ tính các giá trị \(X\) theo cách lặp bằng quy hoạch động.

Xét một chuỗi \(S\) chỉ sử dụng \(c-1\) loại ký tự đầu tiên và có \(r_0\) runs. Lưu ý rằng \(S\) có tổng cộng \(M = N_1 + N_2 + \dots + N_{c-1}\) ký tự. Ngoài ra, nó có một vài loại "vị trí biên" giữa các ký tự:

• Có vị trí biên trước ký tự đầu tiên và biên sau ký tự cuối cùng. Nếu chúng ta thêm một run gồm các ký tự loại \(c\) vào một trong hai vị trí này, tổng số runs sẽ tăng thêm 1.
• Có \(r_0 - 1\) vị trí biên giữa các ký tự khác nhau. Nếu chúng ta thêm một run gồm các ký tự loại \(c\) vào bất kỳ vị trí nào trong số này, tổng số runs sẽ tăng thêm 1.
• Có \(M - r_0\) vị trí biên giữa các ký tự giống nhau. Nếu chúng ta thêm một run gồm các ký tự loại \(c\) vào bất kỳ vị trí nào trong số này, tổng số runs sẽ tăng thêm 2.

Giả sử chúng ta thêm \(x\) runs gồm các ký tự loại \(c\) vào bất kỳ vị trí nào trong số \(r_0 + 1\) vị trí biên từ hai nhóm đầu tiên, và thêm \(y\) runs gồm các ký tự loại \(c\) vào bất kỳ vị trí nào trong số \(M - r_0\) vị trí biên từ nhóm thứ ba. Có đúng \(\binom{r_0 + 1}{x} \times \binom{M - r_0}{y}\) cách chọn các vị trí này, và chúng ta sẽ nhận được \(r_0 + x + 2y\) runs theo cách này. Cuối cùng, chúng ta cần chia \(N_c\) ký tự loại \(c\) vào \(x + y\) runs này. Điều này có thể thực hiện theo đúng \(\binom{N_c - 1}{x + y - 1}\) cách (bài toán chia kẹo Euler hay Stars and bars).

Do đó, số cách thêm tất cả \(N_c\) ký tự loại \(c\) vào \(S\) để có được chuỗi với đúng \(r\) runs có thể được tính như sau:

• Duyệt qua tất cả các số nguyên không âm \(x, y\) sao cho \(r_0 + x + 2y = r\).
• Cộng \(\binom{r_0 + 1}{x} \times \binom{M - r_0}{y} \times \binom{N_c - 1}{x + y - 1}\) vào tổng đang tính.
• Sau khi duyệt hết \(x, y\), tổng này sẽ chứa kết quả chúng ta cần.

Lưu ý rằng kết quả ở đây chỉ phụ thuộc vào \(r_0\). Do đó, tổng đóng góp từ tất cả các chuỗi có \(r_0\) runs chính bằng \(X_{c-1,r_0}\) nhân với đại lượng này. Duyệt qua tất cả các \(r_0\) sẽ cho chúng ta công thức truy hồi cần thiết cho \(X\)!

Cách cài đặt và Độ phức tạp

Phương pháp này thực tế khá nhanh. Chúng ta có thể dùng \(O(450,000 \times 100)\) thời gian để tính trước tất cả các giá trị tổ hợp. Mọi thứ khác chạy trong thời gian \(O(26 \times 100^3)\).

Lưu ý, bạn nên tính các giá trị tổ hợp bằng cách lặp thay vì đệ quy. \(450,000\) lần gọi đệ quy sẽ khiến hầu hết các chương trình bị tràn bộ nhớ ngăn xếp (stack space) và bị treo! Dưới đây là mã giả với một ví dụ cài đặt (các phép toán modulo đã được loại bỏ để dễ nhìn):

def CountTransitions(M, Nc, r0, r):
  # Special case: If adding the first batch of characters the
  # only possible result is to have one run, and there is only
  # one way to achieve that.
  if r0 == 0:
    return r == 1 ? 1 : 0
  result = 0
  dr = r - r0
  for (y = 0; r0 + 2 * y <= r; ++y):
    x = r - (r0 + 2 * y)
    nways_select_x = Choose(r0 + 1, x)
    nways_select_y = Choose(M - r0, y)
    nways_split = Choose(Nc - 1, x + y - 1)
    result += nways_select_x * nways_select_y * nways_split
  return result


def Solve(freq, runs_goal):
  runs_count = [0 for i in range(0, runs_goal + 1)]
  runs_count[0] = 1
  M = 0
  for i, Nc in enumerate(freq):
    if Nc > 0:
      old_runs_count = list(runs_count)
      runs_count = [0 for i in range(0, runs_goal + 1)]
      for (r0 = 0; r0 <= runs_goal; ++r0):
        for (int r = r0 + 1; r <= runs_goal; ++r):
          nways = CountTransitions(M, Nc, r0, r)
          runs_count[r] += nways * old_runs_count[r0]
      M += Nc
  return runs_count[runs_goal]

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