Phân tích: Kiểm tra dị ứng

Có hai chiến lược giải quyết bài toán này: một là sử dụng quy hoạch động, hai là giải pháp tổ hợp trực tiếp.

Quy hoạch động trên số lượng thực phẩm

Nhìn thoáng qua, đây có vẻ là một bài toán quy hoạch động (DP) tiêu chuẩn, nơi chúng ta tính toán số ngày tối thiểu cần thiết để xác định thực phẩm gây dị ứng trong số \(N\) loại thực phẩm. Chúng ta có thể chia \(N\) loại thực phẩm thành hai nhóm, thực hiện thí nghiệm trên một nhóm (tức là ăn tất cả thực phẩm trong nhóm đầu tiên) và đợi kết quả. Nếu Kelly có phản ứng dị ứng, thì thực phẩm gây dị ứng nằm trong nhóm đầu tiên, ngược lại nó nằm trong nhóm thứ hai. Số ngày cần thiết sau đó phụ thuộc vào số ngày cần để giải quyết từng tập hợp nhỏ hơn.

Chúng ta có thể thử tất cả các kích thước chia cho nhóm đầu tiên, điều này dẫn đến giải pháp \(O(N^2)\). Có thể cải thiện lên \(O(N)\) bằng cách nhận thấy rằng kích thước chia tối ưu cho \(N\) luôn ít nhất bằng kích thước chia tối ưu cho \(N-1\). Tuy nhiên, với \(N\) lên tới \(10^{15}\), cách tiếp cận này là không khả thi.

Tại sao việc chia đôi các loại thực phẩm không phải lúc nào cũng tối ưu? Ví dụ: \(A = 1, B = 100, N = 4\). Ở đây, chi phí của việc bị dị ứng là rất cao. Tốt hơn là thử từng loại thực phẩm một vì nếu Kelly ăn trúng loại gây dị ứng, cô ấy sẽ biết ngay vào ngày hôm sau, tổng cộng chỉ mất tối đa 3 ngày. Nếu chia thành hai nhóm mỗi nhóm 2 loại, cô ấy có nguy cơ bị dị ứng và vẫn chưa xác định được thực phẩm cụ thể, phải đợi 100 ngày cho thí nghiệm tiếp theo.

Quy hoạch động trên số ngày

Với \(A\) và \(B\) nhỏ, số ngày cần thiết chỉ nằm trong khoảng vài nghìn ngay cả với \(N\) lớn. Điều này gợi ý sử dụng số ngày làm trạng thái DP. Gọi max_foods(D) là số lượng thực phẩm tối đa mà Kelly có thể xác định trong tối đa \(D\) ngày. Chúng ta tìm \(X\) nhỏ nhất sao cho max_foods(X) >= N.

Để tính max_foods(D), ta xây dựng một cây nhị phân đầy đủ đại diện cho chiến lược xử lý nhiều thực phẩm nhất trong thời gian \(D\). Mỗi nút tương ứng với một tập hợp thực phẩm. Kelly bắt đầu ở gốc, ăn tất cả thực phẩm ở con bên phải. Nếu không phản ứng, cô di chuyển sang con bên trái. Nếu có phản ứng, cô di chuyển sang con bên phải. Các lá tương ứng với một loại thực phẩm duy nhất.

Định nghĩa "chiều cao" của một nút là số ngày còn lại. Gốc có chiều cao \(D\). Nếu một nút có chiều cao \(X\), con bên trái có chiều cao \(X-A\) (mất \(A\) ngày để biết không có phản ứng). Con bên phải có chiều cao \(X-A\) nếu nó là lá, và \(X-B\) nếu không phải (vì phải đợi \(B\) ngày để phản ứng biến mất trước khi thử tiếp).

Giá trị của một nút là số lượng thực phẩm tối đa nó có thể xử lý.

Nếu một nút có chiều cao \(D\), giá trị của nó là max_foods(D) = max_foods(D - A) + max_foods(D - B).

Ví dụ với \(A = 2, B = 3\) và \(D = 8\):

Từ hình trên, ta thấy max_foods(8) = 9, max_foods(6) = 5, v.v. Các nút có cùng chiều cao thường có cùng giá trị (ngoại trừ trường hợp lá là con bên phải).

Cài đặt mẫu bằng Python 3 sử dụng ghi nhớ (memoization):

from functools import lru_cache

@lru_cache(maxsize = None)  # Memoization.
def max_foods(D, A, B):
  if D < A: return 1  # Leaf node.
  return max_foods(D - A, A, B) + max_foods(D - B, A, B)

# We can also use binary search here.
def min_days(N, A, B):
  days = 0
  while max_foods(days, A, B) < N:
    days = days + 1
  return days

for tc in range(int(input())):
  print("Case #%d: %d" % (tc+1, \
    min_days(*map(int, input().split()))))

Quy hoạch động trên số lượng cạnh mỗi loại

Quan sát thấy với \(A, B\) lớn, tập hợp các ngày \(D\) mà max_foods(D) > max_foods(D-1) là thưa thớt. Mỗi cạnh làm giảm thời gian còn lại đi \(A\) hoặc \(B\). Gọi là cạnh-A và cạnh-B. Vì chiều cao của nút chỉ phụ thuộc vào số lượng cạnh-A và cạnh-B trên đường đi đến gốc, ta có thể dùng trạng thái DP gọn hơn:

INF = 1e16

def max_foods(D, A, B):
  ans = 0
  mem = [0] * 60  # zero-array of 60 elements.
  mem[0] = 1
  for i in range(int(D / A + 1)):  # A-edges.
    for j in range(int(D / B + 1)):  # B-edges.
      H = i * A + j * B  # Height of this node.

      # Skip this node if it uses more than D days.
      if H > D: break

      # Aggregate the child’s value.
      if j > 0 and H + A <= D: mem[j] += mem[j-1]

      # if we are too close to D to add a B-edge,
      # the right child is a leaf,
      # so add this node to the answer.
      if H + B + A > D: ans += mem[j]

      # Avoid overflows.
      ans = min(ans, INF)
      mem[j] = min(mem[j], INF)

  return ans

Cách 1: Sử dụng công thức đóng cho số cạnh-B \(\le 2\)

Nếu \(B/A\) rất lớn, số cạnh-B sẽ rất ít. Nếu \(B/A > N\), sẽ không có cạnh-B nào (thử từng loại một). Ta có thể thiết lập công thức đóng cho trường hợp có 0, 1, hoặc 2 cạnh-B (tương ứng với chiều cao cây \(< B+A, < 2B+A, < 3B+A\)). Nếu \(B/A > 200,000\), ta dùng công thức đóng, ngược lại dùng DP.

def linear(D, A, B):
  return int(D / A + 1)

def quadratic(D, A, B):
  R = int((D - B) / A)
  if INF / R < R: return INF
  return int(linear(D, A, B) + (R * (R + 1)) / 2)

def cubic(D, A, B):
  ans = quadratic(D, A, B)
  a = int((D - 2 * B) / A)
  for i in range(a):
    R = a - i
    if INF / R < R: return INF
    ans += int((R * (R + 1)) / 2)
    if ans > INF: return INF
  return ans

def binary_search(N, A, B, low, high, func):
  while high - low > 1:
    D = int((high + low) / 2)
    if func(D, A, B) >= N:
      high = D
    else:
      low = D
  return high

def min_days(N, A, B):
  if quadratic(B + A, A, B) >= N:
    return binary_search(N, A, B, -1, B + A, linear)
  if cubic(2 * B + A, A, B) >= N:
    return binary_search(N, A, B, B + A, 2 * B + A, quadratic)
  if cubic(3 * B + A, A, B) + 1 >= N:
    return binary_search(N, A, B, 2 * B + A, 3 * B + A, cubic)
  return binary_search(N, A, B, 3 * B + A, 51 * B, max_foods)

for tc in range(int(input())):
  print("Case #%d: %d" % (tc+1, \
    min_days(*map(int, input().split()))))

Cách 2: Tăng tốc DP bằng nhân ma trận nhanh

Trạng thái DP tại bước \(i+1\) là tổng tuyến tính của trạng thái tại bước \(i\). Ta có thể biểu diễn quá trình chuyển đổi bằng nhân ma trận. Mặc dù ma trận thay đổi tùy theo chỉ số, nhưng số lần thay đổi cấu trúc ma trận là hữu hạn (tối đa 50 lần). Điều này cho phép dùng lũy thừa ma trận nhanh để tăng tốc. Độ phức tạp khoảng \(O(\log^6 N)\).

Giải pháp tổ hợp

Ta có thể tính max_foods(T) trực tiếp hơn. Với mỗi lá, đường đi từ gốc đến nó là một chuỗi các ký tự 'x' (trái) và 'y' (phải). Với các đường kết thúc bằng 'y' và có chiều cao \(< B-A\), ta loại bỏ 'y' cuối cùng.

Mỗi chuỗi gồm \(K\) ký tự 'x' và \(L\) ký tự 'y' sao cho \(T-B < KA + LB \le T\). Số lượng chuỗi như vậy là \(\binom{K+L}{L}\). Tổng số thực phẩm là:

Với \(T-B < KA + LB \le T\). Ta có thể viết lại tổng theo \(L\):

Tương đương với:

Vì số lượng chuỗi tăng theo hàm mũ với \(L\), giá trị cực đại của \(L\) là \(O(\log N)\), cho phép tính toán hiệu quả.

Cài đặt mẫu bằng Python 3:

def nCk(n, k):
  if k > n: return 0
  res = 1
  for i in range(1, min(n - k, k) + 1):
    res = res * (n - i + 1) // i
  return res

def max_foods(D, A, B):
  cnt = 0
  for L in range(min(51, D // B + 1)):
    K_min = (D - L * B - B) // A + 1
    K_max = (D - L * B) // A
    cnt += nCk(K_max + L + 1, L + 1) - nCk(K_min + L, L + 1)
  return cnt

def min_days(N, A, B):
  lo = 0
  hi = int(1e15)
  while lo < hi:
    D = (lo + hi) // 2
    if max_foods(D, A, B) >= N:
      hi = D
    else:
      lo = D + 1
  return lo

for tc in range(int(input())):
  print("Case #%d: %d" % (tc+1, \
    min_days(*map(int, input().split()))))

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