Phân tích

Nếu khu rừng chỉ có một cây thì hiển nhiên không cần chặt gì và đáp án của cây đó là 0.

Nếu đã chặt một số cây sao cho điểm \(P\) nằm trên biên, khi đi theo chiều kim đồng hồ trên biên từ \(P\), ta sẽ tới một điểm biên khác \(Q\). Hãy tưởng tượng đứng tại \(P\) và nhìn dọc theo đường biên về phía \(Q\). Không thể còn cây nào đứng bên trái đường thẳng có hướng này; nếu có thì đây không phải là biên.

Điều đó gợi ý thuật toán tìm số cây ít nhất cần chặt: với mỗi \(P\), thử mọi điểm khác làm ứng viên cho điểm kế tiếp trên biên \(Q\), rồi đếm số điểm nằm bên trái đường thẳng \(PQ\). Kích thước nhỏ nhất trong các tập điểm ấy là đáp án tốt nhất:

For each point P
  Let M = N-1
  For each point Q ≠ P
    Let Temp = 0
    For each point R ≠ P, Q
      If R is to the left of the line PQ
        Temp = Temp + 1
    If Temp < M
      M = Temp
  Output M

Chặt toàn bộ cây bên trái \(PQ\) đối với một lựa chọn \(Q\) nào đó luôn đủ để tạo ra lời giải hợp lệ: bất kể các cây còn lại ở đâu, \(P\) sẽ nằm trên biên. Phương pháp cũng chắc chắn tìm được lời giải tối ưu, vì trong lời giải tối ưu luôn có một điểm \(Q\) kế tiếp trên biên và ta đã thử cách chặt ít cây nhất để điều đó xảy ra.

Hình 1

Xét trường hợp ở Hình 1. Điểm số 4 đã nằm trên biên khi chọn \(Q\) là điểm số 2. Không có điểm nào bên trái \(PQ\) cần chặt, nên đáp án cho điểm số 4 là 0.

Hình 2

Nếu \(P\) là điểm số 5 thì \(P\) chưa nằm trên biên. Chọn \(Q\) là điểm số 3 như Hình 2, ta thấy có hai điểm bên trái \(PQ\): điểm số 2 và số 4. Chặt hai cây đó sẽ đưa \(P\) lên biên.

Tuy nhiên, đây chưa phải lời giải tối ưu. Khi thử điểm số 2 làm \(Q\), ta có lời giải tốt hơn vì chỉ cần chặt điểm số 4.

Thuật toán này mất \(O(N^3)\) thời gian, nhưng ta có thể làm tốt hơn.

Hình 3

Với mỗi điểm mới \(P\), tạo mảng \(S\) chứa tất cả các điểm khác. Sắp xếp \(S\) theo góc của đường nối từ \(P\) tới điểm đó. Sau đó thử từng \(Q\ne P\) bằng cách duyệt \(S\), tức duyệt các điểm theo thứ tự ngược chiều kim đồng hồ quanh \(P\).

Ưu điểm là với mỗi \(Q\), tất cả điểm nằm bên trái \(PQ\) sẽ xuất hiện sau \(Q\) trong \(S\). Ta biểu diễn đồng thời lựa chọn \(Q\) hiện tại và tập điểm bên trái \(PQ\) bằng một “cửa sổ” với hai con trỏ vào \(S\): con trỏ đuôi chỉ vào \(Q\), còn con trỏ đầu chỉ vào điểm cuối cùng sau \(Q\) vẫn nằm bên trái \(PQ\). Trong các hình, điểm này được gọi là \(R\).

Ở Hình 3, cửa sổ có \(P=\) số 1, \(Q=\) số 2, \(R=\) số 6. Đuôi cửa sổ (màu đỏ) ở điểm số 2, đầu cửa sổ (màu xanh) ở điểm số 6. Các điểm số 3, 4, 5, 6 nằm bên trái \(PQ\), nên lựa chọn \(Q\) này cho một lời giải ứng viên cần chặt 4 cây.

Hình 4

Để cập nhật cửa sổ cho lựa chọn \(Q\) kế tiếp, cần làm hai việc: đưa đuôi tiến một điểm tới \(Q\) mới và quét tiếp từ vị trí hiện tại của đầu để tìm \(R\) mới. Trong Hình 4, đuôi đã tới điểm số 3 và đầu tới điểm số 8. Lời giải ứng viên lúc này cần chặt 5 cây: số 4, 5, 6, 7 và 8.

Vì đuôi duyệt mỗi điểm đúng một lần và đầu duyệt mỗi điểm nhiều nhất hai lần, phần này mất \(O(N)\) thời gian cho mỗi lựa chọn \(P\).

Sắp xếp mất \(O(N\log N)\) cho mỗi \(P\), nên tổng độ phức tạp là \(O(N^2\log N)\).

Có một số điểm cần cẩn thận khi cài đặt:

• Đầu cửa sổ sẽ chạm cuối \(S\) trước đuôi. Khi đó đầu phải quay vòng về đầu \(S\) để lấy đủ các điểm bên trái \(PQ\). Chẳng hạn, khi \(Q=\) số 6, đầu là số 11; khi \(Q\) tiến tới số 7, đầu phải vòng về điểm số 2 ở đầu danh sách vì điểm số 2 nằm bên trái \(PQ\).
• Có thể hoàn toàn không có điểm nào bên trái \(PQ\), ví dụ \(P=\) số 4 và \(Q=\) số 2. Có thể xử lý bằng cách đặt đầu bằng đuôi; công thức đếm số cây cần chặt sẽ tự cho 0. Khi tăng đuôi một điểm, cũng tăng đầu nếu hai con trỏ đang trùng nhau.
• Có thể có nhiều điểm cùng góc nhìn từ \(P\). Trường hợp này được xử lý tự động vì chúng liên tiếp trong \(S\). Khi chọn điểm cuối cùng trong nhóm làm \(Q\), ta tính đúng số cây cần chặt. Với các điểm cùng góc trước đó, ta có thể đếm thừa, nhưng vẫn tìm được giá trị nhỏ nhất nên không cần mã riêng.
• Khi cập nhật đầu cửa sổ, phải dừng nếu điểm tiếp theo có góc lớn hơn hoặc bằng góc của \(Q\) cộng \(\pi\). Số thực không chính xác nên cần dùng một epsilon khi so sánh. Chênh lệch góc nhỏ nhất giữa hai điểm xấp xỉ \(1{,}25\times10^{-13}\) radian. Số thực 64 bit đủ chính xác để biểu diễn mức chênh này; dùng epsilon \(10^{-13}\) sẽ hoạt động.

Burunduk1, người thắng Vòng 1A và có thời gian giải bài này nhanh nhất, đã dùng một cài đặt của thuật toán trên.

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