Cắt bánh quy

Một chiếc bánh có chiều rộng \(W\) và chiều cao \(H\) có chu vi \(2\times(W+H)\). Nếu thực hiện một đường cắt thẳng dài \(C\) chia chiếc bánh làm đôi, mỗi mảnh sẽ có một cạnh dài \(C\), còn các cạnh khác của hai mảnh hợp lại chính là chu vi chiếc bánh ban đầu. Vì vậy, sau khi cắt, tổng chu vi là \(X=2\times(W+H+C)\).

Rõ ràng \(X\) nhỏ nhất khi ta giữ nguyên chiếc bánh. Tuy nhiên, nếu đã quyết định cắt và muốn tối thiểu hóa \(X\), ta phải tối thiểu hóa \(C\); không đường cắt nào có thể ngắn hơn cạnh nhỏ hơn trong \(W\) và \(H\), nên ta cắt qua trung điểm của hai cạnh dài hơn, khiến độ dài đường cắt bằng cạnh ngắn hơn. Khi đó \(X=2\times(W+H+\min(W,H))\). Ngược lại, nếu muốn đường cắt làm \(X\) lớn nhất, ta phải tối đa hóa \(C\) bằng cách cắt qua hai góc đối diện. Khi đó \(C=\sqrt{W^2+H^2}\) và \(X=2\times(W+H+\sqrt{W^2+H^2})\). Nếu bắt đầu đường cắt tại một vị trí nằm giữa một trong các trung điểm của cạnh dài và một góc, ta nhận được một giá trị \(X\) nằm giữa hai cực trị này; vì có thể cắt ở bất kỳ vị trí nào trong khoảng đó, ta có thể đạt mọi giá trị \(X\) trung gian mong muốn.

Vì thế, tùy cách xử lý một chiếc bánh, đóng góp của nó vào tổng chu vi hoặc là \(2\times(W+H)\), hoặc là một giá trị trong

Từ đây, ta viết tắt hai đầu mút của khoảng tăng thêm là \([L,R]\). (Ta cũng có thể chia mọi giá trị trong bài cho 2 để loại bỏ hệ số đó, nhưng phân tích này giữ lại nó cho rõ ràng.)

Test Set 1

Trong Test Set 1, tất cả bánh quy có cùng kích thước, gọi là \(W\) và \(H\). Đặt \(P'\) bằng \(P-2\times(W+H)\) — tức phần chu vi bổ sung cần thêm để đạt mục tiêu \(P\). Như vậy, ta có thể phát biểu lại bài toán là bắt đầu với tổng chu vi 0 và cố đạt \(P'\). Với mỗi chiếc bánh, ta có thể không cắt, khiến tổng chu vi không đổi, hoặc cắt, khiến tổng chu vi tăng thêm một giá trị tùy chọn trong \([L,R]\). Nếu cắt \(K\) chiếc bánh, tổng phần tăng có thể là bất kỳ giá trị nào trong \([K\times L,K\times R]\), tùy cách thực hiện các đường cắt. Ta sẽ suy nghĩ theo khoảng này thay vì từng đường cắt riêng lẻ.

Nên cắt bao nhiêu chiếc bánh? Dĩ nhiên, ta không bao giờ nên cắt nhiều đến mức \(K\times L>P'\). Tuy nhiên, ta cũng nên tiếp tục cắt thêm bánh cho đến ngay trước điểm đó, vì làm vậy vừa đưa khoảng đạt được đến gần mục tiêu hơn, vừa khiến khoảng rộng hơn. Do đó, ta giải \(X\times L=P'\) rồi chọn \(K=\lfloor X\rfloor\), tức \(\lfloor P'/L\rfloor\). (Vì \(L\) là một số nguyên biểu diễn một trong các độ dài cạnh ban đầu và \(P'\) cũng được đảm bảo là số nguyên, ở đây nên dùng phép chia số nguyên để tránh những vấn đề quen thuộc khi lấy phần nguyên của số dấu phẩy động!)

Sau đó, ta kiểm tra liệu \([K\times L,K\times R]\) có chứa \(P'\) hay không. Nếu có, khoảng cách đến mục tiêu là 0; nếu không, khoảng cách là \(P'\) trừ đầu mút phải của khoảng, tức \(P'-K\times R\). Mặc dù \(R\) nói chung không phải số nguyên, ta không cần lo về vấn đề dấu phẩy động; ngay cả khi \(P'\) rất gần \(K\times R\) và ta nhầm rằng nó không nằm trong khoảng, kết quả thu được vẫn đủ gần 0 theo quy tắc sai số của đề.

Test Set 2

Trong Test Set 2, các bánh có thể có kích thước khác nhau, nên ta nhận được các khoảng tổng khác nhau tùy vào tập bánh được cắt. Không có cơ sở tiên nghiệm để quyết định nên cắt chiếc nào, và ta không thể trực tiếp kiểm tra cả \(2^{100}\) khả năng, nhưng có thể dùng quy hoạch động để chắc chắn tìm được khả năng tốt nhất mà không liệt kê tường minh tất cả; bài toán rất giống bài toán cái túi. Với mỗi chiếc bánh, ta quyết định giữ nguyên hay cắt nó; nếu cắt, ta cộng \(L\) vào tổng chu vi và có thêm tối đa \(R-L\) đơn vị “độ co giãn”. Sau khi quyết định xong những chiếc bánh cần cắt, ta có thể dùng nhiều hay ít phần “co giãn” này tùy ý. Khi các yếu tố khác như nhau, có nhiều độ co giãn hơn luôn tốt hơn. Giới hạn lớn của \(P\) có vẻ đáng ngại, nhưng có thể tự kiểm chứng rằng không gian bài toán thực sự đủ nhỏ để những phương pháp như vậy hoạt động.

Tuy nhiên, bài toán cũng có thể được giải theo một cách khác. Như trong lời giải trước, mỗi chiếc bánh tương ứng với một khoảng \([L,R]\) mà ta có thể tăng tổng chu vi nếu quyết định cắt chiếc bánh đó. Gọi \(S(K)\) là danh sách các khoảng có thể đạt được sau khi xử lý \(K\) chiếc bánh đầu tiên. Ban đầu, \(S(0)=\{[0,0]\}\).

Khi xét chiếc bánh thứ \(K\), ta có thể cắt hoặc không. Giả sử chiếc bánh này tương ứng với khoảng \([L,R]\). Nếu không cắt, ta có thể đạt bất kỳ chu vi nào vốn đã nằm trong một khoảng của \(S(K-1)\). Nếu cắt, ta có thể đạt mọi khoảng trong tập

Để thu được \(S(K)\), trước hết lấy hợp của \(S(K-1)\) và \(S'\), rồi gộp các khoảng chồng lấn. Ví dụ, nếu \(S(K-1)=\{[0,0],[3,6]\}\) và ta thêm \([L,R]=[1,2]\), thì \(S'=\{[1,2],[4,8]\}\) và \(S(K)=\{[0,0],[1,2],[3,8]\}\). Lưu ý rằng khoảng \([3,6]\) từ \(S(K-1)\) và \([4,8]\) từ \(S'\) được gộp thành một khoảng \([3,8]\).

Ta có thể loại mọi khoảng bắt đầu sau \(P'\), để sau khi xử lý đủ \(N\) chiếc bánh, đáp án cho câu hỏi sẽ là khoảng cách từ \(P'\) đến khoảng cuối cùng.

Nếu chưa phân tích thêm, ta có thể dự đoán kích thước \(S(N)\) là \(2^N\), vì nó có thể tăng gấp đôi ở mỗi bước. Hóa ra ta có thể đưa ra cận mạnh hơn nhiều: \(\log(P')/\log(\sqrt2)+1\).

Trước hết cần quan sát rằng mọi khoảng \([L,R]\) ứng với một chiếc bánh đều thỏa \(R\ge\sqrt2\times L\), với dấu bằng khi chiếc bánh là hình vuông. Bằng quy nạp, ta suy ra mọi khoảng \([l,r]\) trong mỗi \(S(K)\) cũng thỏa \(r\ge\sqrt2\times l\).

Quan sát thứ hai là tất cả khoảng trong \(S(N)\) đều rời nhau. Bây giờ, sắp xếp các khoảng trong \(S(N)\) và đánh số từ \([l_0,r_0]=[0,0]\). Hai quan sát trên cho

Vì cận dưới của mỗi khoảng là số nguyên, ta còn có \(l_1\ge1\). Do đó \(l_i\ge(\sqrt2)^{i-1}\). Vì có thể bỏ mọi khoảng bắt đầu sau \(P'\), ta giả sử \(l_i\le P'\). Suy ra \(S(N)\) có nhiều nhất \(\log(P')/\log(\sqrt2)+1\) khoảng.

Lời giải này chạy trong \(O(N\log P')\) thời gian: với mỗi trong số \(N\) chiếc bánh, ta thực hiện một bước gộp mất \(O(|S(K)|)\) thời gian.

Cũng có thể chứng minh \(|S(K)|\le2K+1\). Xin dành chứng minh này làm bài tập cho bạn đọc!

Nguồn

Dịch đầy đủ từ phân tích chính thức của Google Code Jam 2018, Round 1A, bài Edgy Baking.