Phân tích: Trie Sharding

Ta được cho một tập \(S\) gồm \(M\) xâu phân biệt. Ta muốn gán các xâu này vào \(N\) máy chủ sao cho mỗi máy chủ có ít nhất một xâu. Sau đó, mỗi máy chủ dựng một trie từ các xâu được gán cho nó. Bài toán yêu cầu tìm những phép gán làm cho tổng số nút của các trie trên tất cả máy chủ lớn nhất có thể, đồng thời báo cáo tổng số phép gán khác nhau như vậy.

Để giải bài toán, trước hết ta dựng trie cho các xâu trong \(S\), rồi tính đáp án từ trie đó. Để tiện giải thích, ta dùng một tập xâu khác với tập trong đề bài: AA, AB, AAA, B, với \(N=3\) máy chủ. Các tiền tố tương ứng trong ví dụ là "", A, AA, AAA, AB và B. Hình sau biểu diễn trie của các xâu này. Nếu chưa quen với trie, có thể tham khảo tài liệu hướng dẫn về trie mà bản phân tích chính thức dẫn tới.

Những nút có hai đường tròn biểu thị rằng tiền tố của nút đó thuộc tập xâu \(S\). Với mỗi nút \(p\), tiền tố của nút được định nghĩa là xâu tạo bởi việc nối các ký tự trên đường đi từ gốc tới nút ấy. Giá trị \(K_p\), trong đó \(p\) là tiền tố của nút, sẽ được giải thích ở đoạn tiếp theo.

Trước khi mô tả \(K_p\), hãy xét \(T_p\). Với một tiền tố \(p\), đặt \(T_p\) là số xâu chứa tiền tố \(p\). Trong ví dụ, các giá trị tương ứng là \(T_{""}=4\), \(T_A=3\), \(T_{AA}=2\), \(T_{AAA}=1\), \(T_{AB}=1\) và \(T_B=1\). Hãy hình dung một phép gán tối ưu, tức phép gán có số nút lớn nhất; cách tính một phép gán như vậy sẽ được mô tả ở phần sau. Trong phép gán tối ưu, giả sử một tiền tố \(p\) xuất hiện nhiều lần nhất trong phạm vi cho phép; ta cũng sẽ chứng minh điều này ở phần sau. Tuy nhiên, số lần tiền tố đó có thể xuất hiện bị chặn trên bởi số máy chủ \(N\). Trong ví dụ, tiền tố rỗng chỉ có thể xuất hiện nhiều nhất 3 lần chứ không phải 4 lần (dù \(T_{""}=4\)), vì chỉ có 3 máy chủ để nó xuất hiện. Để biểu diễn việc \(T_p\) bị chặn bởi \(N\), đặt

Vì thế, \(K_p\) là số lần lớn nhất mà tiền tố \(p\) có thể xuất hiện trong bất kỳ phép gán nào. Quay lại bài toán, tối đa hóa số nút về bản chất tương đương với việc tìm một phép gán trong đó mỗi tiền tố \(p\) xuất hiện \(K_p\) lần (nếu điều đó khả thi), rồi đếm số phép gán khác nhau đạt số nút lớn nhất.

Xác định số nút lớn nhất

Để tạo một phép gán có tổng số nút lớn nhất trên tất cả máy chủ, ta dùng phương pháp tham lam. Trước hết, sắp xếp các xâu đã cho theo thứ tự từ điển. Trong ví dụ, các xâu ban đầu là AA, AB, AAA, B; sau khi sắp xếp, dãy là AA, AAA, AB, B. Theo định nghĩa ở trên, tiền tố \(p\) là tiền tố của \(T_p\) xâu. Ta khẳng định rằng sau khi sắp xếp, \(p\) sẽ nằm trong \(T_p\) xâu liên tiếp theo thứ tự này. Chẳng hạn, tiền tố A xuất hiện trong 3 xâu liên tiếp; tương tự, AA xuất hiện làm tiền tố hai lần, và hiển nhiên tiền tố rỗng xuất hiện bốn lần.

Bây giờ ta mô tả chiến lược tham lam để gán xâu cho các máy chủ. Gán xâu thứ \(i\) trong dãy đã sắp xếp cho máy chủ thứ \(i\bmod N\) (hiểu các chỉ số theo cùng một quy ước tuần hoàn). Với ba máy chủ trong ví dụ, phép gán là {AA,B}, {AAA} và {AB}: xâu thứ nhất và thứ tư vào máy chủ thứ nhất, còn xâu thứ hai và thứ ba lần lượt vào máy chủ thứ hai và thứ ba. Nếu có hai máy chủ, phép gán sẽ là {AA,AB}, {AAA,B}. Ta khẳng định phép gán tham lam này là tối ưu, làm số nút lớn nhất và khiến mỗi tiền tố \(p\) xuất hiện trên \(K_p\) máy chủ khác nhau. Lý do là mỗi \(p\) xuất hiện trong \(T_p\) xâu liên tiếp như đã chứng minh ở trên. Khi lần lượt phân các xâu theo vòng tròn vào \(N\) máy chủ, \(p\) sẽ xuất hiện trên đúng \(\min(N,T_p)=K_p\) máy chủ. Do đó, để tính số nút lớn nhất, chỉ cần lấy

trên tất cả các nút tiền tố \(p\) của trie.

Đếm số phép gán đạt số nút lớn nhất

Trước khi tiếp tục, ta nhắc lại ngắn gọn về tổ hợp. Có thể dùng tam giác Pascal để tiền xử lý các số tổ hợp. Mọi phép cộng và nhân đều được thực hiện theo modulo \(1\,000\,000\,007\), đúng như đề yêu cầu. Trong phần phân tích này, ký hiệu \(Choose(n,k)\) là số cách chọn \(k\) phần tử trong \(n\) phần tử. Theo định nghĩa, \(Choose(n,k)=0\) khi \(n<k\).

Giả sử ta đã dựng trie cho \(S\) và đã tính \(K_p\) cho mỗi nút có tiền tố \(p\); đây là số máy chủ lớn nhất mà nút tiền tố \(p\) có thể được gán tới. Ta duyệt trie theo hậu thứ tự và tính \(W_p\), là số cách phân phối cây con của nút hiện tại lên \(K_p\) máy chủ sao cho đạt số nút lớn nhất. Cây con của nút \(p\) chứa mọi xâu có tiền tố \(p\). Vì gốc, với \(p=""\), là tiền tố của mọi xâu, ta có đáp án cuối cùng sau khi xử lý xong nút gốc.

Trước hết xét trường hợp đơn giản khi phép duyệt tới một nút lá. Nút lá biểu diễn một xâu hoàn chỉnh. Vì một xâu chỉ có thể được đặt trên đúng một máy chủ, \(K_p=1\) với mọi nút lá \(p\). Cũng chỉ có đúng một cách đặt một xâu lên một máy chủ, nên \(W_p=1\) với mọi nút lá \(p\).

Tiếp theo xét nút không phải lá, tức nút trong \(p\). Sau khi thăm tất cả các nút con \(c\) của \(p\), ta tính \(W_p\) từ các thông tin sau:

• \(K_c\): số máy chủ được gán cho mỗi nút con \(c\);
• \(W_c\): số phép gán đạt số nút lớn nhất cho mỗi nút con \(c\);
• \(K_p\): số máy chủ được gán cho nút \(p\). Mỗi khi một nút được gán tới một máy chủ, tất cả các nút cha của nó cũng phải được gán tới chính máy chủ đó. Vì vậy, không nút nào có thể nằm trên nhiều máy chủ hơn nút cha của nó, tức \(K_p\ge K_c\);
• tiền tố \(p\) có phải là một xâu hoàn chỉnh, nghĩa là có thuộc \(S\), hay không.

Để tính \(W_p\) cho nút trong \(p\), trước hết cần tính:

• \(C_1\): số cách chọn nút con nào đi tới máy chủ nào trong \(K_p\) máy chủ;
• \(C_2\): số cách sắp xếp cây con của mỗi nút con \(c\) trên \(K_c\) máy chủ của nó;
• \(C_3\): số cách đặt xâu của chính nút này lên một trong \(K_p\) máy chủ, nếu tiền tố \(p\) thuộc \(S\) (ví dụ nút mang nhãn \(K_{AA}\) trong hình trên).

\(W_p\) là tích của \(C_1\), \(C_2\) và \(C_3\). Mặt khác, \(C_2\) là tích của \(W_c\) trên mọi nút con \(c\) của \(p\), bởi mỗi nút con có thể phân phối các nút trong cây con của mình lên máy chủ một cách độc lập.

Ta có thể gộp phép tính \(C_1\) và \(C_3\). Nếu tiền tố \(p\) là một xâu trong \(S\) (như nút mang nhãn \(K_{AA}\) trong hình), ta thêm một nút lá giả làm con của \(p\). Sau khi thêm lá giả, việc tính \(C_1\) đồng thời bao gồm việc tính \(C_3\). Lưu ý rằng \(C_1\) không phụ thuộc vào các giá trị \(W_c\) của con; để tính \(C_1\), ta chỉ cần các giá trị \(K_c\). Nói cách khác, để đếm số cách chọn những máy chủ trong \(K_p\) máy chủ cho mỗi nút con, chỉ cần biết mỗi nút con \(c\) được gán tới bao nhiêu máy chủ, tức \(K_c\). Việc gộp \(C_3\) vào \(C_1\) chính là thêm một nút con giả \(c\) với \(K_c=1\).

Bây giờ xét cách tính \(C_1\). Có thể tính \(C_1\) bằng quy hoạch động. Lưu các giá trị \(K_c\) của mọi nút con vào một danh sách; nếu cần tính cả \(C_3\), danh sách còn có \(K_c=1\) của nút con giả. Ta muốn gán các bản sao ứng với mỗi nút con lên \(K_p\) máy chủ sao cho hai bản sao của cùng một nút con không được gán tới cùng một máy chủ, vì mục tiêu là tối đa hóa số máy chủ được dùng cho nút con đó, và đồng thời cả \(K_p\) máy chủ đều được dùng, tức không máy chủ nào rỗng. Để minh họa rõ phép tính, ta chuyển bài toán sang đếm các viên bi màu.

Đếm các viên bi màu

Ta có thể xem danh sách các \(K_c\) như một bộ sưu tập bi với nhiều màu phân biệt. Mỗi phần tử trong danh sách cho biết số viên bi của một màu. Câu hỏi trở thành: có bao nhiêu cách phân phối các viên bi vào \(K\) hộp (tức \(K_p\) máy chủ), sao cho mỗi hộp có ít nhất một viên và không hộp nào chứa hai viên cùng màu? Một hộp tương ứng với một máy chủ trong bài toán. Vì không máy chủ nào được rỗng, mỗi hộp phải có ít nhất một viên.

Điều kiện “mỗi hộp có ít nhất một viên” khá khó xử lý, nên trước hết ta bỏ qua nó và đếm các cách phân phối mà mỗi hộp chứa nhiều nhất một viên của mỗi màu, nhưng có thể có hộp rỗng. Phép đếm này sẽ đếm thừa. Xét riêng một màu có \(x\) viên: chúng phải đi vào \(x\) hộp khác nhau trong tổng số \(K\) hộp, có \(Choose(K,x)\) cách chọn. Với tất cả các màu, nhân \(Choose(K,x)\) cho mọi phần tử \(x\) trong danh sách. Gọi đại lượng đó là \(OC_K\), tức số đếm thừa khi có \(K\) hộp:

\(OC_K\) đếm thừa vì khi phân phối bi màu lên \(K\) máy chủ, một số máy chủ có thể rỗng. Thực ra ta cần tính \(OC_i\) cho mọi \(i\) từ 1 tới \(K\); lý do sẽ xuất hiện ngay sau đây. Cách tính \(OC_i\) giống \(OC_K\), chỉ thay \(K\) bằng \(i\): nhân \(Choose(i,x)\) cho từng phần tử \(x\) trong danh sách.

Hãy xét vài ví dụ về \(OC_i\). Nếu danh sách là {1,2,2,3} và có 4 hộp, thì

Nếu bất kỳ giá trị nào trong danh sách lớn hơn số hộp \(i\), thì \(OC_i=0\). Chẳng hạn, với cùng danh sách nhưng chỉ có 2 hộp,

trong đó \(Choose(2,3)=0\), nên \(OC_2=0\). Về trực giác, ta đang đếm cách đặt 3 viên cùng màu vào 2 hộp sao cho mỗi hộp chứa nhiều nhất một viên màu đó; điều này không thể thực hiện được, vì vậy kết quả bằng 0.

Bây giờ đưa trở lại điều kiện “không có hộp rỗng”. Khi đã có \(OC_i\) cho mọi \(i\), ta biết số cách phân phối vào \(i\) hộp trong đó một số hộp có thể rỗng. Gọi \(Count_i\) là số cách không để hộp nào rỗng; đại lượng cần tìm là \(Count_K\). Trước hết, \(Count_1=OC_1\). Thật vậy, \(OC_1\) đếm số cách đặt tất cả các viên bi màu vào một hộp; vì ngay từ đầu chỉ có một hộp nên không thể có hộp rỗng. Do đó \(Count_1=OC_1\).

Tóm lại, ta đã biết \(OC_i\) và \(Count_1\), còn mục tiêu là tính \(Count_K\). Để tính \(Count_i\), ta dùng \(OC_i\). Hãy tạm hình dung cách tính \(OC_i\) nếu đã biết các \(Count_a\):

OC_i = sum(Count_a * Choose(i, i-a) for a in [1, i])

Giải thích công thức này như sau. \(OC_i\) đếm các phân phối trong đó một số trong \(i\) hộp có thể rỗng. Giả sử có \(a\) hộp không rỗng, nên có \(i-a\) hộp rỗng. Có \(Choose(i,i-a)\) cách chọn \(i-a\) hộp rỗng trong \(i\) hộp. Sau đó, số cách lấp đầy \(a\) hộp không rỗng bằng bi chính là \(Count_a\).

Đổi vế của công thức trên và tách số hạng ứng với \(a=i\) ở vế trái, ta được:

Count_i * Choose(i,0) + sum(Count_a * Choose(i, i-a) for a in [1, i-1]) = OC_i

Vì \(Choose(i,0)=1\), sau khi chuyển các số hạng còn lại sang vế kia, ta có:

Count_i = OC_i - sum(Count_a * Choose(i, i-a) for a in [1, i-1])

Nhờ đó, ta tính \(Count_i\) lần lượt: trước tiên là \(Count_2\), rồi \(Count_3\), và tiếp tục cho tới \(Count_K\). \(Count_K\) là số cách phân phối danh sách bi màu vào \(K\) hộp sao cho mỗi hộp có ít nhất một viên và không hộp nào có hai viên cùng màu.

Bản phân tích chính thức đề nghị tham khảo phần cài đặt của rng..58, phần cài đặt hiện thực đúng ý tưởng đếm vừa trình bày.

Bản chính thức khuyến nghị người đọc luyện gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Dựa trên phân tích chính thức của Google Code Jam 2014, Vòng 2.