Phân tích: Data Packing

Cho một danh sách các kích thước tệp tin, Adam muốn đóng gói các tệp này vào số lượng đĩa compact tối thiểu, trong đó mỗi đĩa có thể chứa tối đa 2 tệp và một tệp đơn lẻ không thể bị chia nhỏ vào nhiều đĩa. Tất cả các đĩa compact đều có cùng dung lượng \(X\) MB.

Có một vài cách tiếp cận tham lam có thể giải quyết bài toán này. Chúng tôi mô tả một cách và chỉ ra cách cài đặt nó hiệu quả. Đầu tiên, chúng ta sắp xếp tất cả các kích thước tệp tin. Sau đó, chúng ta quét tuyến tính danh sách đã sắp xếp từ nhỏ nhất đến lớn nhất. Đối với mỗi tệp, chúng ta cố gắng "ghép đôi" nó với tệp lớn nhất có thể sao cho cả hai đều vừa trong dung lượng \(X\). Nếu không tìm thấy tệp lớn nhất như vậy, chúng ta đặt tệp đó vào một đĩa riêng. Cuối cùng, chúng ta báo cáo số lượng đĩa đã sử dụng.

Hãy phân tích thời gian chạy cho giải pháp này. Việc sắp xếp mất \(O(N \log N)\), và việc quét tuyến tính kết hợp với tìm kiếm tệp lớn nhất có thể mất \(O(N^2)\). Do đó, thời gian chạy cho thuật toán này là \(O(N^2)\), đủ để giải quyết bộ dữ liệu lớn (Large dataset).

Chúng ta có thể tối ưu hóa thêm giải pháp này bằng cách tránh tính toán \(O(N^2)\). Để làm như vậy, chúng ta sử dụng một ý tưởng phổ biến trong các cuộc thi lập trình. Đầu tiên, như trước, chúng ta sắp xếp các kích thước tệp tin. Sau đó, chúng ta theo dõi hai con trỏ (hoặc chỉ số) A và B: A ban đầu trỏ đến chỉ số nhỏ nhất (tức là chỉ số 0), và B ban đầu trỏ đến chỉ số lớn nhất (tức là chỉ số \(N-1\)). Ý tưởng là tại bất kỳ thời điểm nào, hai con trỏ A và B trỏ đến hai tệp ứng viên có thể được ghép đôi và đặt vào một đĩa. Nếu tổng kích thước của chúng vừa với \(X\), thì chúng ta đặt chúng vào một đĩa và sau đó "tiến" cả hai con trỏ đồng thời, tức là tăng A thêm 1 và giảm B đi 1. Nếu tổng kích thước tệp không vừa với \(X\), thì chúng ta lặp lại quá trình giảm B đi 1 -- điều này có nghĩa là tệp lớn tại chỉ số B trước đó sẽ cần được đặt vào một đĩa riêng -- cho đến khi tổng kích thước tệp tại A và B vừa với \(X\). Trong quá trình lặp này, chúng ta nên xử lý trường hợp khi A và B trỏ cùng một chỉ số, tức là đảm bảo chúng ta không đếm trùng tệp đó. Sau khi tìm thấy một tệp khớp tại B, chúng ta đồng thời tiến A và B như trước. Chúng ta chỉ nên lặp lại quá trình này khi B lớn hơn hoặc bằng A. Về thời gian chạy, việc di chuyển các con trỏ lớn nhất và nhỏ nhất mất thời gian \(O(N)\), do đó thời gian chạy bị chi phối bởi việc sắp xếp là \(O(N \log N)\).

Bên lề, chúng tôi muốn chỉ ra rằng đối với giải pháp đầu tiên, việc sắp xếp thực sự không bắt buộc. Thay vào đó, chúng ta có thể chọn bất kỳ tệp nào, sau đó tìm tệp lớn nhất phù hợp với nó trong một đĩa. Nếu không có tệp lớn nhất như vậy, chúng ta có thể đặt tệp đó một mình. Về mặt trực giác, lý do tại sao nó hoạt động là vì chúng ta cố gắng "ghép đôi" mỗi tệp một cách tham lam với tệp lớn nhất có thể tốt nhất. Thuật toán này vẫn có thời gian chạy \(O(N^2)\).

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