Phân tích: Hexacoin Jam

Nhiệm vụ chính của bài toán là đếm số cách chọn một hoán vị và một cặp số trong danh sách sao cho tổng (có thể bị cắt bớt) của chúng nằm trong đoạn đã cho. Đây là tử số của phân số biểu diễn xác suất cần tìm. Tổng số cách chọn (mẫu số) đơn giản là

Sau đó, ta có thể dùng một thuật toán quen thuộc (chẳng hạn chia tử số và mẫu số cho ước chung lớn nhất) để rút gọn phân số về dạng yêu cầu. Trong phần phân tích còn lại, ta chỉ tập trung tính tử số chưa rút gọn.

Một điểm chung của mọi lời giải cho tất cả các Test Set là giá trị thực tế của các chữ số trong danh sách không quan trọng. Khi đã cố định một cặp số \(X\) và \(Y\) trong danh sách, chỉ "cấu trúc chữ số" của cặp \((X,Y)\) là quan trọng. Cấu trúc chữ số của một cặp số là một cách duy nhất để biểu diễn sự liên kết giữa các chữ số của chúng. Ta định nghĩa nó là cặp \((P[X],P[Y])\) nhỏ nhất theo thứ tự từ điển trong tất cả các hoán vị chữ số \(P\) có thể, trong đó \(P[X]\) là kết quả thay mỗi chữ số của \(X\) bằng giá trị mà \(P\) gán cho nó. Lưu ý rằng cấu trúc chữ số có độ dài \(2D\).

Tổng số cấu trúc chữ số tăng nhanh khi \(D\) tăng, nhưng chỉ phụ thuộc vào \(D\), mà \(D\) có giới hạn nhỏ. Tổng số cấu trúc là 15 với \(D=2\), 203 với \(D=3\), 4140 với \(D=4\) và 115975 với \(D=5\).

Test Set 1

Trong Test Set 1, số lượng cấu trúc chữ số khác nhau thực sự rất nhỏ. Ngoài ra, với một cấu trúc cố định, ta chỉ quan tâm tới các giá trị mà hoán vị đã chọn gán cho nhiều nhất \(2D\) chữ số. Với mỗi cấu trúc chữ số có \(d\) chữ số phân biệt, ta có thể tính giá trị của tổng bị cắt ứng với một phép gán hợp lệ cho \(d\) chữ số đó, đồng thời lưu ý rằng có \((16-d)!\) cách sinh ra mỗi phép gán.

Số phép gán hợp lệ có thể khá lớn, đạt \(16!/10!\), tức khoảng 6 triệu, khi có 6 chữ số phân biệt; tuy nhiên, trong Test Set 1 chỉ có một cấu trúc chữ số chứa nhiều chữ số phân biệt đến vậy. Có một vài cấu trúc chứa 5 chữ số phân biệt, mỗi cấu trúc có khoảng nửa triệu phép gán, còn hầu hết các cấu trúc có không quá 4 chữ số phân biệt và mỗi cấu trúc có dưới 50 nghìn phép gán. Hơn nữa, phép tính này chỉ phụ thuộc vào \(D\) chứ không phụ thuộc vào phần còn lại của dữ liệu vào, nên ta chỉ phải thực hiện nó một lần cho mỗi cấu trúc có thể có với \(D=2\) và \(D=3\).

Với phần tiền xử lý trên, ta có thể duyệt các cặp số nguyên trong danh sách, tính cấu trúc chữ số của chúng và dùng hai phép tìm kiếm nhị phân để xác định có bao nhiêu số trong danh sách đã tiền xử lý nằm trong đoạn. Sau đó, ta tính số chữ số phân biệt \(d\) trong cấu trúc và nhân tổng vừa đếm với \((16-d)!\), từ đó thu được số tổng nằm trong đoạn có thể được tạo ra bởi cặp đã cho. Cộng kết quả này trên mọi cặp có thể sẽ cho đáp án cần tìm.

Test Set 2

Phần tiền xử lý ở trên có thể chậm trong Test Set 2. Ta không chỉ phải xử lý thêm 4140 cấu trúc chữ số, mà quan trọng hơn, một vài cấu trúc trong số đó có 7 hoặc 8 chữ số phân biệt. Mỗi chữ số được thêm vào làm số phép gán có thể tăng thêm một bậc độ lớn. Có nhiều cách xử lý vấn đề này và ta chỉ cần dùng một vài thủ thuật dưới đây để lời giải chạy được.

Vấn đề đầu tiên là các danh sách cần lưu giờ đã quá dài để vừa bộ nhớ. Vì chỉ có tối đa \(16^4\) kết quả khác nhau, nhiều kết quả sẽ lặp lại, nên ta có thể nén chúng dựa trên số lần lặp. Cách này vẫn khó triển khai hiệu quả, do đó tốt nhất là không lưu toàn bộ danh sách. Ta biết rằng mình chỉ quan tâm có bao nhiêu phần tử của danh sách nằm trong đoạn đối với nhiều nhất \(T\) đoạn khác nhau. Vì vậy, ta có thể đọc tất cả các bộ test trước khi bắt đầu tính toán, chia toàn bộ miền kết quả tổng tại mọi giá trị \(A\) và \(B\) đã đọc thành nhiều nhất \(2T+1\) đoạn tối tiểu, rồi nén chung mọi số nằm trong cùng một đoạn. Dữ liệu này chắc chắn vừa bộ nhớ.

Ta cũng có thể chọn không ghi nhớ kết quả giữa các bộ test khác nhau và xử lý từng bộ test một. Khi đó, ta có \(A\) và \(B\) cố định nên không cần danh sách, chỉ cần một bộ đếm. Ta có thể xử lý riêng từng cặp số (đồng thời tăng tốc quá trình duyệt các phép gán — xem bên dưới), hoặc thử ghi nhớ các cấu trúc chữ số nếu có cấu trúc lặp lại trong cùng bộ test. Dĩ nhiên, gần như mọi cặp đều có thể mang một cấu trúc chữ số khác nhau, nhưng chỉ có ít cấu trúc đạt số chữ số phân biệt tối đa. Điều này có nghĩa việc ghi nhớ sẽ giảm tổng thời gian chạy trong trường hợp trước đây là trường hợp xấu nhất của ta; còn trường hợp xấu nhất mới (mọi cấu trúc đều khác nhau) không quá tệ vì nhiều cấu trúc trong đó sẽ có ít chữ số phân biệt hơn.

Ta có thể giảm thêm số cấu trúc chữ số bằng cách nhận ra rằng các cấu trúc như (011, 022) và (012, 021) là tương đương, theo nghĩa là với mọi phép gán, tổng của chúng giống nhau: cả hai đều bằng \(11 × (P[2]+P[3])+100 × P[0]\), trong đó 11 và 100 được viết ở hệ 16. Cách này chỉ hữu ích khi kết hợp với một hình thức ghi nhớ kết quả nào đó.

Khi tại thời điểm xử lý các phép gán ta đã cố định một đoạn \([A,B]\) hoặc một danh sách nhỏ các đoạn, ta có thể dùng chúng để cắt nhánh. Giả sử ta gán giá trị cho các chữ số ở những vị trí có trọng số lớn nhất trước. Sau khi thực hiện một phép gán một phần, ta có thể tính hoặc ước lượng đoạn giá trị mà tổng có thể nhận khi hoàn tất phép gán. Càng nhiều chữ số có trọng số lớn được gán, đoạn đó càng thu hẹp. Nếu đoạn này nằm hoàn toàn bên trong đoạn đích (hoặc một trong các đoạn đích), ta có thể dừng và biết rằng mọi cách gán tiếp theo đều hợp lệ, rồi đếm chúng bằng một phép nhân đơn giản. Nếu đoạn này nằm hoàn toàn bên ngoài đoạn đích (hoặc mọi đoạn đích), ta cũng có thể dừng và không đếm thêm gì cả.

Như đã nói ở trên, ta chỉ cần một vài trong số các tối ưu trên để vượt qua Test Set 2. Dĩ nhiên, tìm ra và cài đặt càng nhiều tối ưu thì ta càng có thể tự tin vào tốc độ của lời giải.

Test Set 3

Để đơn giản hóa bài toán, ta có thể dùng một kỹ thuật phổ biến khi đếm các số trong đoạn đóng \([A,B]\). Ta viết hàm \(f(U)\) chỉ tính giá trị cho đoạn đóng \([0,U-1]\). Khi đó, kết quả cho đoạn \([A,B]\) là \(f(B+1)-f(A)\). Trong bài này, ta cũng có thể dùng kỹ thuật đó để xử lý phần tràn bằng cách bỏ qua việc cắt chữ số tràn và đếm số lần rơi vào đoạn \([A,B]\) cộng với số lần rơi vào đoạn \([16^D+A,16^D+B]\); đây là những tổng duy nhất mà sau khi cắt sẽ cho kết quả thuộc \([A,B]\). Sau khi viết hàm \(f\), biểu thức kết quả trở thành

Bây giờ ta tập trung tính \(f(U)\), tức số cách chọn một hoán vị và một cặp số sao cho tổng (chưa cắt) của chúng nhỏ hơn nghiêm ngặt \(U\).

Cả số giá trị mà một tổng có thể nhận lẫn số cặp có thể có đều nhỏ (đối với máy tính). Ta có thể dùng một phương pháp "gặp nhau ở giữa" bất đối xứng để tận dụng cả hai điều đó. Ta thực hiện tương tự như với Test Set 1 và có thể cả Test Set 2: lưu một bộ đếm cho mỗi cấu trúc chữ số, rồi duyệt các cặp số trong danh sách để xác định cần sử dụng mỗi bộ đếm bao nhiêu lần.

Trước tiên, hãy xét mọi cách cộng ra một giá trị nhỏ hơn \(U\). Cố định số thứ nhất có giá trị \(x\), khi đó số thứ hai có thể nhận mọi giá trị nhỏ hơn \(U-x\). Một số \(y\) nhỏ hơn \(U-x\) khi và chỉ khi tại vị trí đầu tiên mà hai số khác nhau, nó có chữ số nhỏ hơn chữ số của \(U-x\). Ta có thể biểu diễn tập các số \(y\) này như sau: chúng bắt đầu bằng \(i\) chữ số đầu của \(U-x\), tiếp theo là một chữ số \(d\) nhỏ hơn chữ số thứ \((i+1)\) của \(U-x\), còn mọi chữ số còn lại có thể tùy ý.

Ví dụ, nếu \(U=2345\) và \(x=1122\) thì \(U-x=1223\), và \(y\) có thể có một trong các dạng 0***, 10**, 11**, 120*, 121*, 1220, 1221, 1222, trong đó * biểu diễn một chữ số tùy ý.

Với mỗi cặp gồm một giá trị \(x\) và một tiền tố của \(y\), ta có thể biểu diễn tất cả các cặp số trong danh sách khớp với chúng bằng cách đối chiếu với một cấu trúc chữ số cho phép có các dấu * ở cuối. Theo cách này, một cặp số \(X\) và \(Y\) trong danh sách có thể được một hoán vị ánh xạ thành \(x\) và \(y\) nếu chúng có cùng cấu trúc chữ số, không xét giá trị thực tế của các chữ số. Để biểu diễn điều đó, ta chuẩn hóa cấu trúc chữ số như trước: không chữ số nào xuất hiện lần đầu trước một chữ số nhỏ hơn nó. Vì vậy, cấu trúc \(x=1122\) và \(y=10**\) được biểu diễn thành \(x=0011\) và \(y=02**\). Như trước, số hoán vị có thể ánh xạ một cặp số vào cấu trúc chữ số này là \((16-d)!\), trong đó \(d\) là số chữ số phân biệt xuất hiện trong cấu trúc.

Lưu ý rằng các giá trị \(x\) khác nhau có thể tạo ra cùng một cấu trúc. Ví dụ, \(x=1133\) cho \(U-x=1212\), và với \(y=10**\), cấu trúc thu được giống cấu trúc của \(x=1122\) và \(y=10**\).

Với mỗi cấu trúc chữ số có tổng cộng \(2D\) chữ số và có từ 0 đến \(D-1\) dấu sao ở phần cuối bên phải, ta đếm số hoán vị làm cho hai phần của cấu trúc cộng lại thành một giá trị nhỏ hơn \(U\).

Bây giờ ta xử lý các cặp số trong danh sách. Với mỗi cặp, ta xây dựng cấu trúc chữ số chuẩn hóa như trước và cộng bộ đếm của cấu trúc đó vào tổng đang tính. Ta cũng cộng bộ đếm của các cấu trúc thu được khi thay tối đa \(D-1\) chữ số ngoài cùng bên phải bằng các dấu *.

Ta có thể biểu diễn độ phức tạp của thuật toán theo cơ số \(B\), số chữ số \(D\) của mỗi số và kích thước \(N\) của danh sách số. Giai đoạn đầu duyệt tối đa \(O(B^D)\) giá trị có thể có của \(x\) và với mỗi giá trị, xét tối đa \(O(B × D)\) cấu trúc chữ số cho \(y\). Nếu đã tiền xử lý các giai thừa đến \(B\) và lưu kết quả trong bảng băm hoặc trong một mảng với cách băm khéo léo dành cho cấu trúc chữ số để các giá trị băm vừa duy nhất vừa nhỏ, mỗi cặp chỉ cần thời gian hằng số; vì vậy, tổng thời gian là \(O(B^{D+1} × D)\). Giai đoạn thứ hai cần xử lý tối đa \(O(D)\) cấu trúc chữ số cho mỗi cặp, nên tổng thời gian là \(O(N^2 × D)\). Cộng hai giai đoạn, thời gian tổng thể để tính \(f\) là

Vì ta chỉ cần số lần gọi \(f\) là hằng số, đây cũng là độ phức tạp thời gian tổng thể của thuật toán.

Một lời giải khác là sử dụng hiệu quả tất cả các thủ thuật của Test Set 2. Đặc biệt, hãy xét thủ thuật cuối cùng: khi xét cặp chữ số có trọng số lớn thứ \(i\), chỉ những cặp có tổng gần với chữ số ở vị trí đó của \(A\) hoặc của \(B\) mới tạo ra một đoạn tổng có thể vừa không nằm hoàn toàn trong \([A,B]\), vừa không nằm hoàn toàn ngoài đoạn này. Điều đó có nghĩa ở vị trí chữ số thứ \(i\), chỉ có số lượng tuyến tính các cặp chữ số có thể được gán mà không làm quá trình dừng ngay, thay vì số lượng bậc hai.

Điều này làm số phép gán giảm xuống xấp xỉ căn bậc hai của giá trị trước đó, khiến nó tăng giống hàm mũ theo \(D\) hơn là hàm mũ theo \(2D\). Nhờ vậy, ta thu được độ phức tạp thời gian tương đương với lời giải trình bày ở trên. Mặc dù độ phức tạp thời gian tổng thể vẫn cao hơn, hai lời giải có thể chạy khá tương đương trong các giới hạn của bài: cận trên của số phép gán thực ra nhỏ hơn \(B^D\) vì nó có dạng gần với \(B!/(B-D)!\). Phần tiết kiệm đó, cộng với việc không cần các thừa số \(D\) bổ sung, bù lại cho việc độ phức tạp của lời giải quay lui có một số hạng mang tính chất giống \(B^D\) và một số hạng mang tính chất giống \(N^2\) được nhân với nhau thay vì cộng với nhau.

Lưu ý rằng các nhận xét nền tảng của hai lời giải có liên hệ chặt chẽ. Việc cắt nhánh đem lại mức tăng tốc lớn như vậy cũng chính vì lý do ta có thể sử dụng phương pháp "gặp nhau ở giữa" dựa trên các cấu trúc chữ số.

Dữ liệu kiểm thử

Chúng tôi khuyến nghị bạn luyện tập gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2020, Chung kết thế giới trực tuyến — Hexacoin Jam.