Test Set 1

Vì chỉ có nhiều nhất mười chiếc bánh, ta có thể liệt kê và kiểm tra mọi tập con gồm \(K\) chiếc, chẳng hạn bằng itertools.combinations của Python. Với mỗi tập con, quy tắc đề bài xác định hoàn toàn cách xếp: bán kính không giảm từ trên xuống dưới. Ta chỉ cần tính diện tích bề mặt lộ ra của chồng đó.

Ngoại trừ chiếc trên cùng, một chiếc bánh không bị chiếc phía trên che hoàn toàn sẽ để lộ một vành khăn trên mặt trên. Có thể tính rồi cộng từng vành khăn, nhưng có một cách đơn giản hơn. Tổng diện tích các phần mặt trên lộ ra của mọi chiếc bánh đúng bằng diện tích mặt trên của chiếc dưới cùng. Thật vậy, nếu nhìn thẳng xuống tâm chồng bánh và bỏ qua chiều cao, hình nhìn thấy không khác gì mặt trên của chiếc đáy.

Do đó, diện tích lộ ra bằng diện tích mặt trên của chiếc đáy cộng tổng diện tích mặt bên của mọi chiếc bánh. Nếu chiếc đáy có bán kính \(R\), giá trị đó là

Giá trị lớn nhất trong tất cả các tập con là đáp án.

Test Set 2

Ở Test Set lớn, không thể xét mọi tập con. Giả sử chọn một chiếc bánh \(P\) làm đáy. Mọi chiếc khác trong chồng phải có bán kính không lớn hơn bán kính của \(P\). Theo phép rút gọn diện tích ở trên, ngoài \(P\) ra các chiếc khác thực chất chỉ đóng góp mặt bên, nên trong các ứng viên hợp lệ ta chọn \(K-1\) chiếc có \(R_iH_i\) lớn nhất.

Vì vậy có thể thử từng chiếc làm đáy; sau khi cố định đáy, tiêu chí trên xác định chính xác các chiếc nên đặt phía trên. Với giới hạn \(N\) nhỏ, mỗi lần có thể quét danh sách để tìm chúng, nhưng còn có thể làm tốt hơn. Chẳng hạn, tạo một danh sách bánh theo diện tích mặt bên giảm dần và một danh sách theo bán kính giảm dần. Duyệt danh sách bán kính, lần lượt coi mỗi chiếc là đáy; với mỗi đáy, chọn \(K-1\) phần tử đầu tiên còn hợp lệ trong danh sách mặt bên.

Khi gặp trong danh sách mặt bên một chiếc đứng trước đáy hiện tại trong danh sách bán kính, có thể xóa vĩnh viễn chiếc đó. Nếu bán kính của nó lớn hơn bán kính đáy thì nó không dùng được lúc này hay về sau, vì các đáy sau chỉ có bán kính nhỏ hơn hoặc bằng. Nếu bán kính bằng nhau, ta đã từng thử chiếc đó làm đáy; đổi thứ tự các bánh cùng bán kính chỉ tạo một chồng tương đương đã xét. Dĩ nhiên cũng phải loại chính chiếc đáy hiện tại khỏi danh sách mặt bên vì không thể dùng một chiếc hai lần.

Cách này có độ phức tạp \(O(N\log N+NK)\), tức \(O(N^2)\) trong trường hợp xấu nhất. Có thể cải thiện thêm bằng cách lưu tập \(K-1\) ứng viên tốt nhất trong min-heap/hàng đợi ưu tiên theo chỉ số trong danh sách bán kính, nhờ đó không phải kiểm tra cả \(K-1\) giá trị mỗi lần xem chúng đã “hết hạn” chưa. Khi ấy độ phức tạp là \(O(N\log N+K\log K)\), tương đương \(O(N\log N)\).

Nguồn

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