Phân tích

Gọi \(P_i\) và \(V_i\) lần lượt là vị trí ban đầu và vận tốc của con đom đóm thứ \(i\); vị trí của nó tại thời điểm \(t\) được cho bởi \(P_i + tV_i\). Do đó, tâm khối tại thời điểm \(t\) là:

trong đó \(P_{ave} (= M(0))\) và \(V_{ave}\) lần lượt là vị trí ban đầu trung bình và vận tốc trung bình. Như vậy, chúng ta thấy rằng tâm khối cũng di chuyển trên một tia thẳng (một nửa đường thẳng) với vận tốc không đổi. (Một trường hợp đặc biệt là vận tốc trung bình có thể bằng \(0\), khi đó tâm khối hoàn toàn không di chuyển.)

Vì vậy, bài toán thực chất là tìm khoảng cách gần nhất từ một điểm (gốc tọa độ) đến một tia, một bài toán hình học sơ cấp. Đây là một bài tập dễ với nhiều cách giải ngắn gọn khả thi. Người ta có thể sử dụng các phép biến đổi cơ bản hoặc giải tích để tìm ra công thức chính xác cho các câu trả lời. Người ta cũng có thể nhận thấy rằng hàm khoảng cách \(d(t)\) là một hàm lồi theo \(t\), do đó có thể sử dụng tìm kiếm tam phân (ternary search) để tìm \(t\) tốt nhất.

Ghi chú

Chúng tôi đã thực hiện các tính toán bằng cách sử dụng vector. Nó cũng có thể được thực hiện với tọa độ 3 chiều.

Độ phức tạp

• Thời gian: \(O(N)\) cho mỗi bộ thử nghiệm để tính \(P_{ave}\) và \(V_{ave}\), sau đó là \(O(1)\) để áp dụng công thức hoặc \(O(\log(1/\epsilon))\) nếu dùng tìm kiếm tam phân.
• Bộ nhớ: \(O(N)\) để lưu trữ dữ liệu đầu vào.

Tài liệu tham khảo

Công thức chính xác về khoảng cách từ một điểm đến một đường thẳng trong không gian 3 chiều.

Nguồn

Bản dịch dựa trên phân tích chính thức của Google Code Jam 2009 - Round 1C - Center of Mass, thuộc kho Google Coding Competitions (Apache-2.0).