Test Set 1

Trong Test Set đầu tiên, ta chỉ được yêu cầu tạo ra \(2\) hoặc \(3\) miếng bằng nhau. Hãy xét riêng hai trường hợp này.

Với \(D=2\), nếu đã có hai miếng bằng nhau thì ta không cần nhát cắt nào. Nếu không có hai miếng nào bằng nhau, ta có thể cắt một miếng bất kỳ thành hai nửa bằng nhau bằng một nhát cắt.

Tương tự, với \(D=3\), nếu đã có ba miếng bằng nhau thì ta không cần nhát cắt nào. Ta cũng có thể cắt một miếng bất kỳ thành ba miếng bằng nhau bằng hai nhát cắt. Trường hợp bổ sung cần xét là liệu ta có thể làm được bằng đúng một nhát cắt hay không.

Nếu chỉ thực hiện \(1\) nhát cắt, cuối cùng ta có \(N+1\) miếng: \(N-1\) miếng ban đầu và hai miếng mới. Ba trong số đó phải có cùng kích thước, vì vậy kích thước này phải bằng kích thước của ít nhất một miếng không bị cắt. Ta có thể thử mọi khả năng (tối đa \(N\)) cho kích thước đích và mọi khả năng (tối đa \(N\)) cho miếng sẽ cắt. Nếu miếng \(p\) cần cắt không lớn hơn kích thước đích \(s\), ta bỏ qua trường hợp đó. Nếu không, ta cắt \(p\) thành một phần kích thước \(s\) và một phần kích thước \(A_p-s\). Sau đó, nếu trong tập \(N+1\) miếng có \(3\) miếng kích thước \(s\), ta có thể thực hiện bằng một nhát cắt. Nếu điều đó không xảy ra với bất kỳ khả năng nào đã xét, chắc chắn ta cần hai nhát cắt.

Test Set 2

Hãy định nghĩa một miếng dùng được trọn vẹn là một miếng mà ta có thể dùng toàn bộ để tạo ra các miếng cần thiết, bằng cách cắt nó thành từ \(2\) đến \(D\) miếng bằng nhau hoặc chỉ đơn giản là dùng nguyên miếng. Nói cách khác, một miếng dùng được trọn vẹn sẽ không để lại phần thừa nào.

Sau đây là một quan sát then chốt: với mỗi miếng mà ta tạo ra, ta sẽ cần dùng một nhát cắt, ngoại trừ việc có thể bớt đi một nhát cho mỗi miếng dùng được trọn vẹn mà ta sử dụng. Nghĩa là, ta sẽ cần \(D-K\) nhát cắt để tạo ra \(D\) miếng bằng nhau, trong đó \(K\) là số miếng ban đầu được dùng trọn vẹn.

Ví dụ:

• Luôn có thể tạo ra \(D\) miếng bằng nhau bằng cách cắt một miếng ban đầu bất kỳ với \(D-1\) nhát cắt (\(K=1\)).
• Trường hợp tốt nhất có thể là ta đã có sẵn \(D\) miếng ban đầu bằng nhau, vì khi đó ta thực hiện \(0\) nhát cắt (\(K=D\)).

Cũng lưu ý rằng ta không bao giờ phải xét \(K=0\), vì luôn có thể đạt \(K=1\) bằng cách cắt một miếng ban đầu thành các phần bằng nhau, và ta muốn \(K\) lớn nhất có thể.

Theo quan sát trên, kích thước cuối cùng của các miếng được tạo ra (từ đây gọi là kích thước đích) sẽ bằng một trong các kích thước ban đầu (của một miếng được dùng trọn vẹn) chia cho một số nguyên từ \(1\) đến \(D\). Do đó, ta phải kiểm tra nhiều nhất \(N\times D\) kích thước đích có thể có. Với bất kỳ kích thước nào khác, ta sẽ có \(0\) miếng dùng được trọn vẹn.

Với mỗi kích thước miếng đích như vậy, ta làm như sau:

• Trước tiên, bảo đảm rằng ta thực sự có thể dùng kích thước đó: nếu tổng số miếng có kích thước này có thể tạo ra bằng cách cắt tất cả các miếng ban đầu nhỏ hơn \(D\), thì hiển nhiên kích thước này không hữu ích. Một miếng kích thước \(A_i\) có thể tạo ra tối đa \(\lfloor A_i/s\rfloor\) miếng có kích thước đích \(s\).
• Tiếp theo, ta cần tìm tất cả các miếng dùng được trọn vẹn: kích thước của chúng chia hết cho kích thước miếng đích, không có số dư.
• Bây giờ, vì cần tối đa hóa số miếng ban đầu được dùng trọn vẹn, ta có thể áp dụng chiến lược tham lam và lấy từng miếng đó theo thứ tự kích thước không giảm, cho đến khi có nhiều miếng ban đầu dùng được trọn vẹn nhất có thể (tức là lấy thêm miếng kế tiếp sẽ khiến ta tạo ra nhiều hơn \(D\) miếng đích). Nếu dùng hết mọi miếng ban đầu dùng được trọn vẹn, ta có thể dùng các miếng ban đầu không dùng được trọn vẹn khác theo thứ tự bất kỳ.
• Theo quan sát trước đó, mỗi miếng ban đầu dùng được trọn vẹn cho ta một miếng đích "miễn phí"; mỗi miếng đích còn lại đều cần một nhát cắt để tạo ra. Do đó, tổng số nhát cắt đối với kích thước miếng đích hiện tại là \(D-K\), trong đó \(K\) là số miếng ban đầu dùng được trọn vẹn mà ta sử dụng.

Phần trên có thể thực hiện trong thời gian \(O(N)\) nếu ta sắp xếp các \(A_i\) một lần (theo thứ tự không giảm) ngay từ đầu, nên độ phức tạp thời gian của toàn bộ thuật toán là \(O(D\times N^2)\).

Test Set 3

Trước hết, lưu ý rằng ta có thể tính trước kích thước miếng đích lớn nhất có thể trong thời gian \(O(\log(\max(A_i))\times N)\) bằng cách tìm kiếm nhị phân trên kích thước đích. Sau đó, ta có thể tiết kiệm thời gian bằng cách không xét bất kỳ kích thước miếng đích nào lớn hơn giới hạn đã tính.

Bây giờ, giống như lời giải cho Test Set 2, ta duyệt các \(A_i\) (theo thứ tự không giảm) và mọi số nhát cắt \(c\) (từ \(1\) đến \(D\)). Thay vì duyệt thêm một lượt qua \(N\) miếng ban đầu như trong lời giải cho Test Set 2, ta chỉ cần đánh dấu miếng ban đầu này là một miếng dùng được trọn vẹn đối với kích thước đích \(A_i/c\). Để làm việc đó hiệu quả, ta dùng một từ điển (lý tưởng nhất là được cài đặt bằng bảng băm), trong đó khóa là các kích thước đích hợp lệ, còn giá trị là các bộ gồm số miếng dùng được trọn vẹn đã tìm thấy cho kích thước đích đó và số miếng đích được tạo ra từ chúng. Lưu ý rằng các khóa là phân số; để bảo đảm không biểu diễn cùng một phân số theo nhiều cách, ta có thể dùng một thuật toán tìm ước chung lớn nhất và bảo đảm mọi phân số đều được rút gọn.

Với mỗi kích thước đích \(A_i/c\), ta cộng lần lượt \(1\) và \(c\) vào các giá trị tương ứng trong từ điển tại khóa \(A_i/c\) (giả sử giá trị mặc định của một khóa chưa được đặt là không). Nếu sau thao tác này, số miếng đích kích thước \(A_i/c\) được tạo ra sẽ vượt quá \(D\), ta đơn giản là không xét miếng đó như một miếng dùng được trọn vẹn trong trường hợp này.

Sau đó, ta có thể chọn số lượng lớn nhất có thể \(M\) của các miếng được dùng trọn vẹn trên mọi kích thước đích hợp lệ, và kết quả là \(D-M\). Điều này cải thiện độ phức tạp thời gian của thuật toán thành \(O(D\times N)\).

Dữ liệu kiểm thử

Bạn nê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, Vòng 1C — Oversized Pancake Choppers.