Phân tích: Part Elf

Ở thế hệ đầu tiên (tức là 40 thế hệ trước), chỉ có Elf thuần chủng (1/1) hoặc Người (0/1). Nếu chúng ta liệt kê tất cả các khả năng của con cái trong 3 thế hệ tiếp theo, ta có:

1st gen:  0/1                                     1/1
2nd gen:  0/2                 1/2                 2/2
3rd gen:  0/4       1/4       2/4       3/4       4/4
4th gen:  0/8  1/8  2/8  3/8  4/8  5/8  6/8  7/8  8/8

Dễ dàng nhận thấy rằng ở bất kỳ thế hệ nào, mẫu số luôn là một lũy thừa của hai. Do đó, việc kiểm tra trường hợp impossible rất đơn giản: đầu tiên hãy rút gọn phân số đã cho về dạng tối giản và kiểm tra xem mẫu số có phải là lũy thừa của hai hay không. Một phân số có thể được rút gọn bằng cách chia cả tử số và mẫu số cho ước chung lớn nhất (GCD) của chúng.

Câu hỏi còn lại là đối với một người là Elf P/Q, số thế hệ tối thiểu trước đây có thể có một Elf 1/1 là bao nhiêu?

Với Small dataset, nơi Q tối đa là 1000, chúng ta có thể tạo ra 10 thế hệ đầu tiên (với \(2^{10}\) tổ tiên có thể có) để bao phủ tất cả các trường hợp. Khi tạo ra con cái từ hai cha mẹ, chúng ta ghi lại mối quan hệ của họ. Sau đó, để trả lời câu hỏi, ta chỉ cần thực hiện tìm kiếm theo chiều rộng (BFS - đường đi ngắn nhất trong đồ thị không trọng số) trên đồ thị quan hệ bắt đầu từ Elf P/Q và dừng lại bất cứ khi nào gặp Elf 1/1, sau đó báo cáo độ dài đường đi. Thuật toán này chạy trong \(O(2^N \cdot 2^{2N})\) để tạo đồ thị quan hệ kích thước \(1001 \times 1001\), khả thi với Small dataset nhưng không khả thi với Large dataset.

Đối với Large dataset, cần một góc nhìn khác. Hãy xem xét ví dụ để hiểu quy luật. Giả sử Vida là Elf 3/8, các cặp cha mẹ khả thi là gì?

• (0/8 + 6/8) / 2 = 3/8
• (1/8 + 5/8) / 2 = 3/8
• (2/8 + 4/8) / 2 = 3/8
• (3/8 + 3/8) / 2 = 3/8

Các giá trị tử số của cha mẹ có thể là: 0/8, 1/8, 2/8, 3/8, 4/8, 5/8, 6/8, tạo thành một dải phân số "liên tiếp" từ 0/8 đến 6/8.

Nói một cách chính thức, một Elf P/Q có thể có cha/mẹ là Elf Z/Q với Z nằm trong khoảng từ \(max(0, \mathbf{P} - (\mathbf{Q}-\mathbf{P}))\) đến \(min(\mathbf{Q}, \mathbf{P} \times 2)\). Lưu ý rằng mẫu số Q không thay đổi trong các bước trung gian này (trước khi rút gọn).

Với nhận định này, rõ ràng để đạt được Elf thuần chủng 1/1 nhanh nhất có thể, chúng ta muốn tham lam tạo ra một người cha/mẹ có tử số lớn nhất có thể. Nói cách khác, từ Elf P/Q, chúng ta muốn chọn cha/mẹ Z/Q sao cho Z là cực đại. Chúng ta tiếp tục quá trình này cho đến khi đạt được tỉ lệ 1/1. Thuật toán tham lam này chạy trong \(O(\log \mathbf{Q})\). Dưới đây là một ví dụ cài đặt bằng Python 3:

from fractions import gcd

def is_power_of_two(x):
  return x & (x - 1) == 0

def min_generation(P, Q):
  g = gcd(P, Q)
  P = P // g
  Q = Q // g

  if not(is_power_of_two(Q)):
    return "impossible"

  gen = 0
  while P < Q:
    P = P * 2
    gen += 1
  return gen


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

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