Phân tích

Test set 1

Nếu bạn chỉ muốn giải quyết test set 1, bài toán Equal Sums có thể được coi là một bài toán quy hoạch động kinh điển. Dưới đây là phác thảo của một giải pháp khả thi bằng Python:

def GetSetWithSum(x, target):
  if target == 0: return []
  return GetSetWithSum(x, target - x[target]) + [x[target]]

def FindEqualSumSubsets(S):
  x = [0] + [None] * (50000 * 20)
  for s in S:
    for base_sum in xrange(50000 * 20, -1, -1):
      if x[base_sum] is not None:
        if x[base_sum + s] is None:
          x[base_sum + s] = s
        else:
          subset1 = GetSetWithSum(x, base_sum + s)
          subset2 = GetSetWithSum(x, base_sum) + [s]
          return subset1, subset2
  return None

Ý tưởng là trong x, chúng ta lưu trữ một cách để đạt được mọi tổng tập hợp con có thể. Nếu chúng ta đạt được một tổng theo hai cách khác nhau, thì chúng ta có thể xây dựng hai tập hợp con có cùng tổng đó.

Đối với test set 1, cách tiếp cận này hoạt động tốt. Tuy nhiên, x sẽ phải có kích thước \(500 \times 10^{12}\) cho test set 2. Kích thước đó quá lớn để xử lý, và bạn sẽ cần một cách tiếp cận khác ở đó.

Test set 2

Bước đầu tiên để giải quyết test set 2 là nhận ra rằng đề bài có vẻ rất "đánh đố"! Giả sử bạn chỉ có 50 số nguyên nhỏ hơn \(10^{12}\). Có \(2^{50}\) cách chọn một tập hợp con của chúng, và tổng của các số nguyên trong bất kỳ tập hợp con nào như vậy tối đa là \(50 \times 10^{12} < 2^{50}\). Theo Nguyên lý chuồng bồ câu, điều này có nghĩa là luôn tồn tại hai tập hợp con khác nhau có cùng tổng.

Vậy điều đó có ý nghĩa gì đối với bài toán này? Ngay cả khi bạn chỉ có 50 số nguyên để chọn thay vì 500, câu trả lời sẽ không bao giờ là "Impossible". Bạn cần tìm một cặp tập hợp con có cùng tổng, và có rất nhiều không gian để làm việc đó. Bí quyết là tìm cách tận dụng sự dư thừa đó.

Phương pháp "Nghịch lý" ngày sinh

Giải pháp đơn giản nhất dựa trên một câu đố toán học cổ điển: nghịch lý ngày sinh.

Nghịch lý ngày sinh nói rằng nếu bạn chỉ có 23 người trong một phòng, thì khả năng cao là có hai người trong số họ có cùng ngày sinh. Điều này có thể gây ngạc nhiên vì có 365 ngày khả thi, và 23 nhỏ hơn nhiều so với 365. Nhưng đó là sự thật! Một cách tốt để nhìn nhận nó là: có \(\binom{23}{2} = 253\) cặp người, và mỗi cặp có xác suất \(1/365\) có cùng ngày sinh. Cụ thể, số lượng cặp người kỳ vọng (trung bình) có cùng ngày sinh là \(253 / 365 = 0.693...\) Khi bạn viết nó theo cách đó, không quá ngạc nhiên khi xác suất có ít nhất một cặp trùng nhau là khoảng 0.5.

Hóa ra lập luận chính xác này cũng áp dụng tốt cho bài toán Equal Sums. Đây là một thuật toán đơn giản:

• Chọn ngẫu nhiên 6 số nguyên từ \(S\), cộng chúng lại và lưu kết quả vào một bảng băm (hash set). (Tại sao lại là 6? Chúng ta sẽ quay lại vấn đề đó sau...)
• Lặp lại cho đến khi hai tập hợp gồm 6 số nguyên có cùng tổng, sau đó dừng lại.

Sau khi chọn \(t\) tập hợp, sẽ có \(\binom{t}{2}\) cặp, và mỗi tập hợp sẽ có tổng tối đa là \(6 \times 10^{12}\). Do đó, số lượng va chạm kỳ vọng sẽ xấp xỉ \(t^2 / (12 \times 10^{12})\). Khi \(t\) vào khoảng \(10^6\), kỳ vọng này sẽ gần bằng 1, và lập luận từ nghịch lý ngày sinh cho thấy chúng ta có khả năng cao sẽ có va chạm.

Chỉ vậy thôi! Vì chúng ta có thể nhanh chóng tạo ra \(10^6\) tập hợp con nhỏ và đưa tổng của chúng vào một bảng băm, thuật toán đơn giản này chắc chắn sẽ giải được bài toán. Bạn có thể lo lắng về tính ngẫu nhiên, nhưng ít nhất đối với bài toán này, bạn không nên lo lắng. Thuật toán này cực kỳ đáng tin cậy. Nhân tiện, phương pháp này cũng sẽ hoạt động trên test set 1, vì vậy bạn không cần phải thực hiện giải pháp quy hoạch động nếu không muốn.

Lưu ý: Có nhiều cách tiếp cận tương tự có thể hoạt động. Ví dụ, trong các thử nghiệm nội bộ của chúng tôi, một người đã giải quyết bài toán bằng cách chỉ tập trung vào 50 số nguyên đầu tiên và thử các tập hợp con ngẫu nhiên từ đó. Chứng minh dưới đây áp dụng cho thuật toán này cũng như nhiều thuật toán khác.

Chứng minh chặt chẽ

Nếu bạn có kiến thức toán học, chúng ta thực sự có thể chứng minh một cách chặt chẽ rằng tính ngẫu nhiên không có gì phải lo lắng. Tất cả đều bắt nguồn từ phiên bản sau của định lý ngày sinh:

Bổ đề: Gọi \(X\) là một tập hợp gồm \(N\) số nguyên có giá trị trong khoảng \([1, R]\). Giả sử bạn chọn \(t + 1\) trong số các số nguyên này một cách độc lập và ngẫu nhiên. Nếu \(N \ge 2R\), thì xác suất để các số nguyên được chọn ngẫu nhiên này đều khác nhau là nhỏ hơn \(e^{-t^2 / 4R}\).

Chứng minh: Gọi \(x_i\) là số lượng số nguyên trong \(X\) có giá trị bằng \(i\). Số cách chọn \(t + 1\) số nguyên phân biệt từ \(X\) chính xác là:
sum_(1 ≤ i_1 < i_2 < ... < i_{t+1} ≤ R) [ x_{i_1} * x_{i_2} * ... * x_{i_{t+1}} ].

Ví dụ, nếu \(t=1\) và \(R=3\), tổng sẽ là \(x_1 * x_2 + x_1 * x_3 + x_2 * x_3\). Mỗi số hạng ở đây đại diện cho số cách chọn các số nguyên với một tập hợp các giá trị cụ thể. Thật không may, tổng này khá khó xử lý trực tiếp, nhưng bất đẳng thức Maclaurin khẳng định rằng nó tối đa là:
\(\binom{R}{t+1} \times [ (x_1 + x_2 + ... + x_R) / R ]^{t+1} = \binom{R}{t+1} \times (N/R)^{t+1}\).

Mặt khác, số cách chọn bất kỳ \(t + 1\) số nguyên nào từ \(X\) bằng \(\binom{N}{t+1}\). Do đó, xác suất \(p\) mà chúng ta đang tìm kiếm tối đa là:
\([ \binom{R}{t+1} / \binom{N}{t+1} ] \times (N/R)^{t+1} = \frac{R}{N} \times \frac{R-1}{N-1} \times \frac{R-2}{N-2} \times ... \times \frac{R-t}{N-t} \times (N/R)^{t+1}\).

Bây giờ, vì \(N \ge 2R\), chúng ta biết điều sau đây là đúng cho tất cả \(a \le t\):
\(\frac{R-a}{N-a} < \frac{(R - a/2)^2}{R \times (N-a)} \le \frac{(R - a/2)^2}{N \times (R-a/2)} = \frac{R - a/2}{N}\).
(Điều này là do \((R - a/2)^2 \ge R(R-a)\)).

Do đó, \(p\) nhỏ hơn:
\(R \times (R - 1/2) \times (R - 2/2) \times ... \times (R - t/2) / R^{t+1}\).

Dễ dàng kiểm tra thấy \((R-a/2) \times (R-t/2+a/2) \le (R-t/4)^2\), từ đó suy ra \(p\) cũng nhỏ hơn:
\((R - t/4)^{t+1} / R^{t+1} = (1 - t/4R)^{t+1} < (1 - t/4R)^t\).

Và cuối cùng, chúng ta sử dụng sự thật hữu ích rằng \(1 - x \le e^{-x}\) với mọi \(x\). Điều này cho chúng ta \(p < e^{-t^2 / 4R}\) như yêu cầu.

Trong trường hợp của chúng ta, \(X\) đại diện cho tổng của tất cả các tập hợp con gồm 6 số nguyên. Chúng ta có \(N = \binom{500}{6}\) và \(R = 6 \times 10^{12}\). Bạn có thể kiểm tra rằng \(N \ge 2R\), vì vậy chúng ta có thể áp dụng bổ đề để ước tính xác suất thuật toán vẫn tiếp tục sau \(t+1\) bước:

• Nếu \(t = 10^6\), xác suất vẫn tiếp tục tối đa là 0.972604477.
• Nếu \(t = 5 \times 10^6\), xác suất vẫn tiếp tục tối đa là 0.499351789.
• Nếu \(t = 10^7\), xác suất vẫn tiếp tục tối đa là 0.062176524.
• Nếu \(t = 2 \times 10^7\), xác suất vẫn tiếp tục tối đa là 0.000014945.
• Nếu \(t = 3 \times 10^7\), xác suất vẫn tiếp tục tối đa là \(10^{-11}\).

Nói cách khác, chúng ta có cơ hội tốt để hoàn thành sau 5.000.000 bước, và chúng ta chắc chắn sẽ hoàn thành sau 30.000.000 bước. Lưu ý đây là một sự thật toán học, bất kể 500 số nguyên ban đầu là gì.

Nhận xét: Điều gì xảy ra nếu bạn xem xét các tập hợp con có 5 phần tử thay vì 6? Chứng minh toán học thất bại hoàn toàn vì \(N < R\). Tuy nhiên, trong thực tế, nó vẫn hoạt động tốt trên tất cả dữ liệu thử nghiệm mà chúng tôi có thể nghĩ ra.

Cách tiếp cận xác định

Phương pháp ngẫu nhiên được thảo luận ở trên chắc chắn là cách đơn giản nhất để giải quyết bài toán này. Tuy nhiên, đó không phải là cách duy nhất. Đây là một cách khác, lần này không có tính ngẫu nhiên:

• Lấy 7.000.000 tập hợp con gồm 3 số nguyên của \(S\), sắp xếp chúng theo tổng của chúng, và gọi hiệu nhỏ nhất giữa hai tổng gần nhất là \(d_1\). Gọi \(X_1\) và \(Y_1\) là các tập hợp con tương ứng.
• Loại bỏ \(X_1\) và \(Y_1\) khỏi \(S\), và lặp lại 25 lần để có \(X_i, Y_i\) và \(d_i\) cho \(i\) từ 1 đến 25.
• Gọi \(Z = \{d_1, d_2, ..., d_{25}\}\). Tính tất cả \(2^{25}\) tổng tập hợp con của \(Z\).
• Hai trong số các tổng tập hợp con này được đảm bảo là bằng nhau. Tìm chúng và truy ngược lại qua \(X_i\) và \(Y_i\) để tìm hai tập hợp con tương ứng của \(S\) có tổng bằng nhau.

Có hai điều cần chứng minh ở đây để biện minh rằng thuật toán này hoạt động:

• \(S\) sẽ luôn có ít nhất 7.000.000 tập hợp con gồm 3 số nguyên. Điều này là do ngay cả sau khi loại bỏ \(X_i\) và \(Y_i\), \(S\) sẽ có ít nhất 350 số nguyên, và \(\binom{350}{3} > 7.000.000\).
• \(Z\) sẽ luôn có hai tập hợp con có cùng tổng. Trước tiên, hãy lưu ý rằng các tập hợp con trong bước đầu tiên có tổng tối đa là \(3 \times 10^{12}\), và do đó hai trong số các tổng phải khác nhau tối đa là \(3 \times 10^{12} / 7.000.000 < 500.000\). Do đó, mỗi \(d_i\) tối đa là 500.000. Bây giờ, \(Z\) có \(2^{25}\) tập hợp con, và mỗi tập hợp có tổng tối đa là \(25 \times 500.000 < 2^{25}\), và theo Nguyên lý chuồng bồ câu, hai tập hợp con có cùng tổng.

Các phương pháp tương tự khác cũng khả thi. Đây là một bài toán khá mở!

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