Editorial: Mathematical Algorithms TWK Open Problem #C - Robot Năng Lượng

1.Ý tưởng

Bài toán yêu cầu chọn trạng thái \((X_i, Y_i)\) thuộc bao lồi tập điểm của robot thứ \(i\) sao cho \(\sum X_i = S\) và \(\sum Y_i\) đạt giá trị nhỏ nhất.

1. Nhận xét về bao lồi (Lower Convex Hull):
2. Để tối thiểu hóa điện năng tiêu thụ \(Y_i\) với một lượng linh kiện \(X_i\) cho trước, ta chỉ cần quan tâm đến chuỗi dưới (Lower Hull) của tập điểm thuộc robot \(i\).

3. Chuỗi dưới của một robot gồm các đoạn thẳng nối tiếp có hệ số góc (độ dốc) \(k = \frac{\Delta Y}{\Delta X}\) tăng dần. Hệ số góc này thể hiện "chi phí điện năng tăng thêm cho mỗi đơn vị linh kiện".

4. Tổng Minkowski & Thuật toán Tham lam (Greedy):

5. Tập các cặp \((X, Y)\) có thể tạo thành từ tổng các robot chính là tổng Minkowski của \(n\) chuỗi dưới.
6. Vì chuỗi dưới có tính lồi (hệ số góc tăng dần), ta có thể áp dụng chiến thuật Tham lam:
   • Khởi tạo \(X_{\text{start}} = \sum X_{i, \text{min}}\) và \(Y_{\text{start}} = \sum Y_{i, \text{min}}\) (tổng các điểm xuất phát của chuỗi dưới).
   • Thu thập tất cả các véctơ sự thay đổi \((\Delta X, \Delta Y)\) giữa hai đỉnh liên tiếp trên chuỗi dưới của toàn bộ \(n\) robot.
   • Sắp xếp tất cả các véctơ này theo hệ số góc \(\frac{\Delta Y}{\Delta X}\) tăng dần.
   • Duyệt qua từng véctơ: luôn ưu tiên chọn véctơ có hệ số góc nhỏ nhất để tăng \(X\) lên nhanh nhất với chi phí \(Y\) tăng thêm ít nhất.
   • Khi véctơ hiện tại làm cho tổng \(X\) vượt quá \(S\), ta chỉ lấy một tỷ lệ vừa đủ \(\frac{S - X_{\text{hiện tại}}}{\Delta X}\) của véctơ đó rồi kết thúc.

2.Độ phức tạp

• Tìm chuỗi dưới cho \(n\) robot: \(O(\sum m_i \log m_i)\).
• Sắp xếp tất cả các đoạn véctơ: \(O(M \log M)\) với \(M = \sum m_i \le 2 \cdot 10^5\).
• Duyệt tham lam: \(O(M)\).
• Tổng độ phức tạp thời gian: \(O(M \log M)\), hoạt động mượt mà trong thời gian cho phép.
• Không gian bộ nhớ: \(O(M)\).