Phân tích: Osmos

Chúng ta có thể đơn giản hóa bài toán bằng cách đưa ra nhận xét sau:

Nếu trong một giải pháp, Armin hấp thụ hạt \(X\) trước hạt \(Y\), mà hạt \(X\) lại lớn hơn hạt \(Y\), thì anh ấy có thể thay đổi thứ tự để hấp thụ \(Y\) ngay trước \(X\) mà không cần thực hiện thêm bất kỳ thao tác "thêm" hoặc "loại bỏ" nào. Vì vậy, nếu Armin có một giải pháp tối ưu, chúng ta luôn có thể chuyển nó thành một giải pháp tối ưu hấp thụ các hạt theo thứ tự kích thước tăng dần.

Bây giờ chúng ta có thể giới hạn tìm kiếm trong các giải pháp hấp thụ hạt theo thứ tự kích thước. Chúng ta có thể sử dụng thuật toán quy hoạch động với trạng thái là số lượng hạt đã xem xét và kích thước hiện tại của hạt Armin hoặc số lượng thao tác đã thực hiện, nhưng có một thuật toán đơn giản hơn dựa trên nhận xét sau:

Để thấy điều này, hãy xem xét một giải pháp tồn tại các hạt \(X\) và \(Y\) trong đó \(X\) nhỏ hơn hoặc bằng \(Y\), \(X\) bị loại bỏ, và \(Y\) được hấp thụ. Thay vào đó, \(X\) có thể được hấp thụ ngay trước khi \(Y\) được hấp thụ, điều này sẽ tiết kiệm được một thao tác loại bỏ \(X\). Vì vậy, giải pháp đó không thể là tối ưu.

Do đó, để tìm giải pháp tối ưu, chúng ta chỉ cần xem xét \(N+1\) trường hợp -- đó là những trường hợp chúng ta cố gắng hấp thụ \(0, 1, \dots, N\) hạt đầu tiên (sau khi đã sắp xếp tăng dần) và loại bỏ phần còn lại.

Để tìm xem cần bao nhiêu thao tác cho mỗi trường hợp này, chúng ta mô phỏng việc Armin cố gắng hấp thụ từng hạt một. Nếu hạt của Armin chưa đủ lớn để hấp thụ hạt tiếp theo, chúng ta thêm các hạt có kích thước bằng kích thước hiện tại của hạt Armin trừ đi \(1\) và hấp thụ chúng, cho đến khi hạt của Armin đủ lớn.

Thuật toán này mất thời gian \(O(N^2)\) để chạy như đã mô tả, tốc độ này đủ nhanh so với giới hạn đầu vào. Tuy nhiên, có một sự điều chỉnh nhỏ để khiến nó trở thành tuyến tính.

Một trường hợp cuối cùng cần xử lý là khi hạt của Armin có kích thước bằng \(1\), và do đó không thể hấp thụ bất kỳ hạt nào (ngay cả khi thêm hạt kích thước nhỏ nhất là \(1\) vào thì hạt Armin vẫn không lớn hơn hạt được thêm). Trường hợp này đã được đưa vào ví dụ mẫu.

Dựa trên phân tích chính thức của Google Code Jam.