Test Set 1

Test Set này có thể được giải bằng vét cạn. Ta thử mọi cách phân hoạch \(N\) cử tri vào \(N\) ngôn ngữ. Hai phân hoạch chỉ khác thứ tự các ngôn ngữ được xem là tương đương.

Vì thế, có thể biểu diễn một phân hoạch bằng bộ \(N\) phần tử \((x_1,x_2,\ldots,x_N)\) thỏa \(x_i\ge x_{i+1}\) và \(\sum_i x_i=N\). Ngay cả khi \(N=25\), số phân hoạch khác nhau cũng không quá 2.000.

Với mỗi phân hoạch, dùng cách tham lam sau để kiểm tra liệu có thể đạt được nó chỉ bằng cách thêm phiếu hay không. Sắp các \(C_i\) theo thứ tự không tăng, tức \(C_i\ge C_{i+1}\). Phân hoạch đạt được khi và chỉ khi \(x_i\ge C_i\) với mọi \(1\le i\le L\). Trong tất cả các phân hoạch đạt được, lấy tổng phần trăm đã làm tròn lớn nhất; đó là đáp án.

Test Set 2

Ở Test Set này, ta bỏ yêu cầu phân hoạch và dãy \(C\) phải được sắp không tăng. Xét một cách phân phối \(N\) cử tri vào \(N\) ngôn ngữ là \((x_1,x_2,\ldots,x_N)\) với \(\sum_i x_i=N\).

Dùng quy hoạch động. Định nghĩa \(f(a,b)\) là giá trị lớn nhất của

trên mọi bộ \((x_1,\ldots,x_a)\) thỏa \(\sum_{i=1}^{a}x_i=b\) và \(x_i\ge C_i\) với mọi \(1\le i\le a\). Nếu không có bộ thỏa mãn thì \(f(a,b)=-\infty\). Ta quy ước \(C_i=0\) khi \(i>L\).

Trường hợp cơ sở có nhiều nhất một cách phân phối:

Để tính \(f(a,b)\) với \(a>1\), thử mọi giá trị \(i=x_a\). Ngôn ngữ thứ \(a\) đóng góp \(\operatorname{round}(i/N\cdot100)\), còn \(b-i\) phiếu được phân cho \(a-1\) ngôn ngữ trước:

Cần phân phối \(N\) cử tri vào \(N\) ngôn ngữ, nên đáp án là \(f(N,N)\). Có \(O(N^2)\) trạng thái, mỗi trạng thái tốn \(O(N)\) để chuyển, tổng thời gian \(O(N^3)\).

Test Set 3

Với mỗi ngôn ngữ, tỷ lệ của nó hoặc được làm tròn lên hoặc được làm tròn xuống. Tổng đạt lớn nhất khi có nhiều tỷ lệ được làm tròn lên nhất có thể.

Ta có thể bỏ qua các ngôn ngữ hiện đã được làm tròn lên. Vì có thể tạo tùy ý nhiều ngôn ngữ mới, không điều gì buộc ta phải làm xấu một ngôn ngữ như vậy bằng cách thêm phiếu vào nó; thêm phiếu đó cho một ngôn ngữ mới không tệ hơn. Với mỗi ngôn ngữ hiện có, cũng như với một ngôn ngữ hoàn toàn mới có số phiếu ban đầu bằng 0, tính số phiếu ít nhất cần thêm để tỷ lệ của nó được làm tròn lên.

Sau đó tham lam thỏa càng nhiều ngưỡng càng tốt, bắt đầu từ ngưỡng cần ít phiếu bổ sung nhất. Có thể duy trì các chi phí kế tiếp bằng hàng đợi ưu tiên: lấy chi phí nhỏ nhất còn vừa số phiếu chưa phân, thêm số phiếu ấy vào nhóm tương ứng, rồi tính ngưỡng kế tiếp của nhóm; với lựa chọn mới, sau khi dùng một lựa chọn mới vẫn có thể xét thêm một lựa chọn mới khác. Khi không đủ phiếu để vượt bất kỳ ngưỡng nào, phân phối phần còn lại tùy ý.

Mỗi ngưỡng làm tròn vượt qua làm mục tiêu tăng đúng 1, nên luôn chọn ngưỡng rẻ nhất sẽ tối đa hóa số lần tăng. Thuật toán chạy trong \(O(N\log N)\).

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2018, Round 1B, bài Rounding Error; kho Google Coding Competitions (Apache-2.0).