Giảm độ phức tạp của thuật toán khi giải bài MVECTOR

[ntmtmn (Nguyen Tuan)]

Link đề bài: https://vn.spoj.com/problems/MVECTOR/
Tóm tắt: Trong mp Oxy, khối lượng của 1 vector là tổng của x^2+y^2. Tìm 1 tập con mà tổng của chúng có khối lượng là lớn nhất.
Bài này m sắp xếp các vector hợp với tia Ox 1 góc từ [0,360]. Rồi duyệt các vector liên tiếp sau khi đã sắp xếp để tìm tổng có khối lượng lớn nhất. Nhưng lại vướng đpt duyệt là O(N^2), làm sao để giảm đpt xuống O(N) vậy a?

[nitro2 (Nhím)]

Giả sử bạn đã sắp xếp các vector hợp với tia Ox 1 góc từ [0,360]. Tập hợp này gồm các vector [V1, V2, … Vn]. Với góc tương ứng Ox là [A1, A2, … An]
Không dễ dàng nhận thấy:

• Xét vector V1, thì tập hợp các vector làm tăng khối lượng chung khi và chỉ khi các vector đó hợp với vector V1 một góc từ -90 độ đến 90 độ. Hay nói cách khác, tập hợp các vector nằm chung một nửa mặt phẳng vuông góc với V1 và bờ chứa vector V1.
• Để dễ hình dung hơn, ta có thể lấy tất cả các vector có tọa độ x dương làm ví dụ. Nếu chen thêm một vector có tọa độ x âm thì sẽ làm giảm khối lượng chung của tập hợp. Ở đây là tập hợp các vector nằm trên nửa mặt phẳng chia bởi tia Oy có giá trị x dương.

Như vậy, bạn có thể giảm độ phức tạp bằng cách, tính tổng các vector từ V1 với góc A1 tới Vt với góc At thỏa điều kiện At <= A1+180
Nếu bạn thực hiện duyệt động, thì có thể chỉ cần duyệt qua 1 lần để tìm ra đáp án. Duyệt theo kiểu cuốn chiếu, thêm đầu bớt đuôi.

Bonus ví dụ hình vẽ:

Ở đây bạn sẽ duyệt lần lượt các tập sau:

• Tập 1: Vector B, C , D
• Tập 2: Vector C, D, E
• Tập 3: Vector D, E, F
• Tập 4: Vector E, F, B
• Tập 5: Vector F, B, C
  Vì góc hợp giữa vector cuối và đầu trong các tập hợp trên bé hơn hoặc bằng 180 độ.

[rogp10]

Như trên định nghĩa khối lượng v là v\bullet v
vậy khối lượng của u + v là
\ u\bullet u + v \bullet v + 2 \cdot u \bullet v
=u \bullet u + v \bullet v + 2\sqrt{u \bullet u \cdot v \bullet v}\cdot cos(u, v)