Phân tích: Cắt bánh

Một mảng kem duy nhất

Trước tiên, hãy xét trường hợp chỉ có một mảng kem với cạnh thẳng đứng ở bên phải và có các giá trị thưởng thức \(\mathbf{A}\) và \(\mathbf{B}\). Nếu đường cắt thẳng đứng nằm hoàn toàn bên trái tam giác, ta nhận được \(0\) giá trị thưởng thức và người sinh đôi nhận được \(\mathbf{B}\). Nếu đường cắt nằm bên phải tam giác, ta nhận được \(\mathbf{A}\) và người sinh đôi nhận được \(0\).

Trong trường hợp còn lại, đường cắt nằm đâu đó ở giữa tam giác. Khi ấy, ta nhận được \(\mathbf{A} \cdot P(X)\) giá trị thưởng thức và người sinh đôi nhận được \(\mathbf{B} \cdot (1 - P(X))\), trong đó \(P(X)\) là một giá trị từ 0 đến 1, biểu thị tỉ lệ diện tích tam giác nằm bên trái đường cắt tại vị trí \(X\).

Ta có thể tính \(P(X)\) bằng cách xét các tam giác đồng dạng. Gọi \(T_X\) là tam giác nằm bên trái đường cắt khi cắt tại \(X\). Có thể nhận thấy \(T_X\) và tam giác đầy đủ là hai tam giác đồng dạng. Điều này có nghĩa là tỉ số giữa chiều rộng và chiều cao của \(T_X\) giống với tỉ số tương ứng của tam giác đầy đủ. Vì vậy, với vị trí cắt \(X\), chiều rộng và chiều cao của \(T_X\) lần lượt đều bằng \(\frac{X - \text{left}}{\text{width}}\) lần chiều rộng và chiều cao của tam giác đầy đủ. Do đó, ta tính được \(P(X)\) bằng công thức sau:

Lưu ý rằng \(P(X)\) là một hàm bậc hai (đa thức bậc 2). Từ đó, ta có thể viết công thức giá trị thưởng thức của ta và của người sinh đôi dưới dạng các đa thức theo \(X\):

Giá trị ta quan tâm là hiệu giữa hai giá trị thưởng thức này. Vì vậy, ta có thể lấy hiệu của chúng rồi tìm trị tuyệt đối nhỏ nhất trong một khoảng hoành độ đường cắt \(X\) cho trước (từ cạnh trái đến cạnh phải của tam giác). Ta thực hiện điều này bằng cách kiểm tra:

• Giá trị tại điểm cực trị của hàm bậc hai, nếu điểm đó nằm trong khoảng.
• Giá trị tại mỗi đầu mút của khoảng.
• Hàm bậc hai có cắt trục tại \(0\) trong khoảng hay không.

Ta có thể biết hàm có cắt \(0\) hay không bằng cách kiểm tra xem dấu tại hai đầu mút có khác nhau không. Nếu điểm cực trị nằm trong khoảng, ta cũng cần kiểm tra xem dấu tại đó có khác dấu tại các đầu mút hay không.

Lưu ý rằng khuôn tam giác có thể không có cạnh thẳng đứng. Trong trường hợp này, ta có thể chia tam giác thành hai phần rồi giải riêng cho phía trái và phía phải.

Công thức cho phía phải hơi khác nhưng rất giống công thức dùng cho phía trái. Vì vậy, đối với một tam giác có cạnh thẳng đứng ở bên trái, ta có thể tính tỉ lệ \(P(X)\) như sau:

Nhiều mảng kem

Trong bài toán đầy đủ, ta có nhiều mảng kem. Nếu xét tất cả các hoành độ phân biệt của những đỉnh tạo nên các mảng kem hình tam giác, ta nhận thấy rằng khi cắt tại một vị trí nằm giữa hai hoành độ kề nhau, mỗi tam giác luôn thuộc đúng một trong các trường hợp sau:

• Nằm hoàn toàn bên trái đường cắt (đóng góp vào giá trị thưởng thức của ta).
• Nằm hoàn toàn bên phải đường cắt (đóng góp vào giá trị thưởng thức của người sinh đôi).
• Bị đường cắt chia thành hai phần (đóng góp vào giá trị thưởng thức của cả ta lẫn người sinh đôi).

Do đó, với mỗi cặp hoành độ kề nhau, ta có thể cộng các giá trị thưởng thức hằng số từ những tam giác luôn nằm hoàn toàn bên trái hoặc hoàn toàn bên phải đường cắt vào các hàm bậc hai của những tam giác đang bị cắt. Điều này có nghĩa là hàm \(D(X)\) biểu diễn hiệu giữa hai giá trị thưởng thức khi cắt tại \(X\) là một đa thức từng đoạn có bậc không quá hai. Giữa mỗi cặp hoành độ kề nhau, ta có thể tìm trị tuyệt đối nhỏ nhất của hiệu giữa giá trị thưởng thức của ta và của người sinh đôi. Đáp án cuối cùng là giá trị nhỏ nhất trên tất cả các khoảng hoành độ.

Bằng kỹ thuật đường quét, ta có thể duy trì các đa thức biểu diễn giá trị thưởng thức của ta và của người sinh đôi. Vì cần sắp xếp các điểm theo hoành độ, lời giải tổng thể cần \(O(\mathbf{N} \log \mathbf{N})\) phép toán để sắp xếp và \(O(\mathbf{N})\) phép toán trên phân số. Hãy lưu ý rằng tử số và mẫu số có thể không vừa trong số nguyên 64 bit. Kích thước của các số này tăng theo lôgarit của kích thước dữ liệu vào, nên \(O(\mathbf{N} \log \mathbf{N})\) phép toán là một xấp xỉ hợp lý cho độ phức tạp thời gian tổng thể của thuật toán.

Một vài chuyện bên lề

Do độ phức tạp \(O(\mathbf{N} \log \mathbf{N})\) đã nêu ở đoạn trước, ban đầu bài này có cùng đề bài nhưng được dự định giải bằng số thực dấu phẩy động. Tuy nhiên, như việc đáp án cần các phân số với số nguyên không vừa trong 128 bit đã cho thấy, độ chính xác là một vấn đề lớn. Để các vấn đề độ chính xác còn xử lý được, các biến sẽ phải chịu nhiều giới hạn đến mức một lời giải chỉ đơn giản lặp qua mọi tam giác cho từng khoảng rồi tìm kiếm tam phân cũng có thể dùng được. Một lời giải như vậy có thể được đoán ra mà không cần hiểu các đa thức đã giải thích ở trên. Việc sử dụng phân số là cách buộc lời giải phải hiểu những đa thức đó. Đặt \(\mathbf{N}\) nhỏ cho phép sử dụng số nguyên có độ dài tùy ý mà không phải lo về thời gian chạy tăng thêm. Việc cho tất cả tam giác có cùng hình dạng cũng giúp ích: nó giữ cho kích thước các phân số không trở nên quá lớn.

Chúng tôi khuyên 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 2021, Chung kết thế giới — Cutting Cake.