Code Jam 2009 - Vòng 3

Phân tích: Alphabetomials

1. Tích của hai tập hợp

Bài toán được nghĩ ra trong một cuộc đi bộ ngắn ở Manhattan vào một buổi tối mùa hè. Hình ảnh đầu tiên xuất hiện là một ma trận \(N \times M\). Gọi \(A\) là tập gồm \(N\) từ \(\{A_i \mid 1 \le i \le N\}\) và \(B\) là tập gồm \(M\) từ \(\{B_j \mid 1 \le j \le M\}\). Với một từ \(X\) bất kỳ, ký hiệu \(X(c)\) là số lần ký tự \(c\) xuất hiện trong \(X\). Tại ô \((i,j)\) của ma trận, chẳng hạn ta ghi tích \(A_i(\text{'a'})B_j(\text{'a'})B_j(\text{'b'})\). Tổng của tất cả các ô là bao nhiêu?

Ta có thể tính lần lượt \(NM\) số hạng. Nhưng dễ thấy rằng, dù cộng theo hàng hay theo cột, đó chẳng qua là khai triển đầy đủ của biểu thức

Nói cách khác, ta có thể tính riêng tổng trên \(A\) và tổng trên \(B\), rồi nhân chúng.

Nếu, như trong bài toán của chúng ta, thay vì ghi \(A_i(\text{'a'})B_j(\text{'a'})B_j(\text{'b'})\) ở ô \((i,j)\), ta ghi \(Z(\text{'a'})^2Z(\text{'b'})\), trong đó \(Z\) là phép nối \(A_i\) và \(B_j\), thì sao? Nghĩa là ta không quan tâm chữ a nào đến từ tập thứ nhất, chữ nào đến từ tập thứ hai. Trường hợp này không có biểu thức đơn giản như (1). Nhưng ta có thể rút gọn nếu có quan tâm mỗi chữ a đến từ tập nào. Ta dùng ký hiệu được đơn giản hóa đôi chút (và gần với phát biểu bài toán hơn): ký hiệu \(a\) từ đây cũng biểu diễn số chữ a trong một xâu. Với một xâu cố định \(Z\) là phép nối một từ của \(A\) và một từ của \(B\), gọi \(a_1\) là số chữ a do tập thứ nhất đóng góp, \(a_2\) là số chữ a do tập thứ hai đóng góp. Ở mỗi ô ma trận ta ghi \(a^2b\), bằng \((a_1+a_2)^2(b_1+b_2)\). Khai triển ra, ta có

Ở bước cuối, trong từng số hạng, vì các ký tự từ tập thứ nhất và các ký tự từ tập thứ hai đã được tách riêng gọn gàng, ta có thể áp dụng đúng lập luận của (1).

2. Tích của mười tập hợp

Bài toán yêu cầu tính tổng các biểu thức như \(a^2b\) trên tích Descartes của một tập từ điển với chính nó tối đa 10 lần. (Tổng quát hơn, ta có thể xem đó là tích của 10 tập.) Kích thước của tập tích là con số khổng lồ \(n^{10}\). Nhưng nếu dùng thủ thuật ở phần trước, viết \(a^2b\) thành

rồi khai triển, ta quy bài toán về nhiều nhất \(K^D\) bài toán dễ hơn, trong đó \(D\) là bậc tối đa (\(K \le 10\) và \(D \le 4\) trong bài này). Mỗi bài toán dễ hơn có thể được giải tương tự (1).

Điều này cho ta một lời giải. Hãy xét lần lượt từng đơn thức. Về cơ bản, ta chọn nguồn gốc (một trong mười tập) cho mỗi chữ cái trong đơn thức, vì vậy mỗi tập nhận một đơn thức con; đơn thức con này có thể biểu diễn bằng một tập con các chỉ số của những chữ cái trong đơn thức ban đầu.

Ta tính trước \(\sum_{X \in A}q(X)\) cho mỗi đơn thức con \(q\); có nhiều nhất 16 đơn thức như vậy. Sau đó, với mỗi trong \(K^D\) “bài toán dễ hơn”, phép tính chỉ gồm việc nhân \(K\) số đã tính trước.

3. Tăng tốc

Lời giải trên có thể dễ dàng tăng tốc để xử lý \(K\) lớn hơn nhiều và \(D\) lớn hơn đôi chút, nếu ta tính các tổng tăng dần, mỗi bước lấy tích của hai tập (gọi đó là quy hoạch động hay không cũng được).

Trước tiên, ta tính tổng trên \(A \times A\), không chỉ cho đơn thức đang xét mà cho tất cả các đơn thức con của nó. Sau đó ta tính các tổng trên \(A^3\). Giờ có thể xem \(A^3\) là \(A^2 \times A\). Mỗi đơn thức con có thể khai triển thành nhiều nhất \(2^D\) số hạng, và từng số hạng đều tuân theo thủ thuật đơn giản trong (1). Vì ta đã có tổng trên \(A^2\) cho mọi đơn thức con, mỗi trong \(2^D\) bài toán có thể giải trong thời gian hằng số. Thời gian chạy của lời giải này chủ yếu là \(O(3^D K)\) cho mỗi đơn thức trong đầu vào.

Hãy quan sát dòng cuối của (2). Vì bài toán chỉ có một tập từ điển, ta có thể bỏ các chỉ số dưới — \(A\), \(B\), v.v. đều là cùng một tập. Có thể tăng tốc thêm theo hướng này bằng cách khai thác tính đối xứng của các chỉ số. Chúng tôi lược bỏ chi tiết.

4. Lý thuyết đằng sau

Nếu quen với xác suất rời rạc, bạn có lẽ biết lý thuyết xác suất cung cấp một bộ máy trừu tượng mạnh mẽ cho các bài toán đếm. Những gì ta vừa làm chỉ là vài bài tập dễ trong xác suất. Giải bài này với lý thuyết trừu tượng ấy trong đầu chắc chắn giúp bạn suy nghĩ nhanh hơn và tin tưởng hơn vào lời giải.

Cụ thể, ta đã sử dụng sự kiện quan trọng rằng kỳ vọng của tích \(K\) biến ngẫu nhiên bằng tích kỳ vọng của từng biến, với điều kiện \(K\) biến ngẫu nhiên độc lập lẫn nhau. Độc giả quan tâm có thể tự thiết lập đầy đủ các phép tương ứng hình thức.

Nguồn

Bản dịch dựa trên phân tích chính thức của Google Code Jam 2009 - Round 3 - Alphabetomials, thuộc kho Google Coding Competitions (Apache-2.0).