Phân tích: Ninjutsu

Biến bài toán thành rời rạc

Một điều lập tức nổi bật là bài toán này không rời rạc. Độ dài dây tạo ra lời giải tối ưu có thể là một số thực, và dường như không có cách nào bảo đảm số đó là số hữu tỉ hoặc rời rạc theo một nghĩa nào khác.

Với bất kỳ độ dài dây thực nào, ta có thể mô phỏng và đếm số khúc uốn, nhưng số lượng này không phải là một hàm lồi theo độ dài dây, nên không thể dùng tìm kiếm tam phân.

Điều ta thực sự muốn làm là quy hoạch động, trong đó trạng thái là một bộ ba: điểm mà ta hiện đang quay quanh, hướng mà đầu dây đang chỉ tới, và độ dài dây. Hai trong ba giá trị này là số thực. Tuy nhiên, hãy xem ta thực sự cần quan tâm đến bao nhiêu giá trị thực khác nhau.

Khi đầu dây đang quay quanh một điểm \(P\), không có điều gì đáng chú ý xảy ra cho đến khi đoạn dây đang chuyển động chạm một điểm khác \(Q\). Tại đúng thời điểm đó, ta phải đưa ra quyết định: hoặc uốn dây và chuyển sang quay quanh điểm \(Q\), hoặc cắt dây chính xác tại \(Q\) rồi tiếp tục quay quanh \(P\). Có nhiều nhất \(N^2\) cặp điểm, nên ta chỉ cần xét nhiều nhất \(N^2\) hướng khác nhau. Như vậy tham số DP thứ hai đã được xử lý.

Còn độ dài dây thì sao? Dùng cùng lập luận trên, ta có thể chỉ ra rằng chỉ có hữu hạn độ dài dây đáng quan tâm. Trước hết, lưu ý rằng uốn dây không làm thay đổi độ dài của nó. Mỗi khi quay quanh điểm \(P\) và chạm điểm \(Q\), ta có một quyết định nhị phân: đoạn dây đang quay dài hơn hay ngắn hơn khoảng cách từ \(P\) tới \(Q\)?

Nói cách khác, khoảng số thực từ \(0\) đến \(R\) có thể được chia thành hữu hạn khoảng con sao cho hàm số-khúc-uốn có giá trị không đổi trên mỗi khoảng con. Nhận xét này gợi ý lời giải quy hoạch động ngây thơ sau đây. Trạng thái DP gồm một cặp điểm \((P,Q)\) và một độ dài dây thực \(r\). Giá trị của trạng thái là số khúc uốn lớn nhất có thể đạt được nếu tiếp tục quay quanh \(P\), trong khi hiện tại dây đang chỉ theo hướng tới \(Q\) và đoạn dây đang quay có độ dài \(r\).

Chính xác hơn một chút, ta thực ra cần số trạng thái gấp đôi: một trạng thái cho trường hợp chỉ theo hướng tới \(Q\), và một trạng thái cho trường hợp chỉ theo hướng ngược \(180\) độ so với \(Q\). Loại thứ hai cần thiết khi ta quyết định uốn dây và tiếp tục quay quanh \(Q\). Tại thời điểm đó, ta sẽ bắt đầu với hướng chỉ ngược \(180\) độ so với \(Q\). Một cách cài đặt lời giải này là đơn giản dùng một điểm, một vectơ hai chiều và một độ dài làm trạng thái, thay vì hai điểm và một độ dài.

Tiếp theo, hãy loại bỏ độ dài thực khỏi tham số DP. Vì độ dài dây chỉ thay đổi khi ta quyết định cắt, ta có thể thay tham số độ dài thực bằng một số nguyên: số khúc uốn kể từ lần gần nhất cắt dây. Đồng thời, hãy thay hai tham số đầu bằng cặp điểm đã gây ra lần cắt. Bây giờ ta quan tâm tới mọi tình huống có dạng sau: ta đang quay quanh điểm \(P\), đầu dây chỉ theo hướng \((dx,dy)\); tại thời điểm đó ta cắt dây, và kể từ đó đã tạo thêm \(K\) khúc uốn. Thông tin này đủ để xác định duy nhất một trạng thái, đồng thời suy ra một độ dài dây còn lại cụ thể. Trạng thái DP giờ trở thành bộ ba \(P\), \((dx,dy)\) và \(K\).

Vấn đề số thực

Bây giờ ta đã có một bài toán gần như hoàn toàn rời rạc. Nơi duy nhất cần số thực là khi kiểm tra độ dài dây hiện tại có đủ để chạm một điểm cho trước hay đầu dây sẽ đi phía dưới điểm đó. Nhờ bảo đảm rằng lời giải tối ưu đúng trên cả một khoảng độ dài dây dài \(0.999999\), ta có thể tránh rắc rối làm tròn số thực bằng cách thận trọng: chỉ giả sử dây chạm được một điểm nếu độ dài của nó lớn hơn khoảng cách tới điểm đó ít nhất, chẳng hạn, \(0.5\). Nếu ngắn hơn mức đó, chắc chắn lời giải ấy không hoạt động trên một khoảng độ dài đủ lớn, nên theo bảo đảm của đề, nó không phải lời giải tối ưu.

Xử lý vòng lặp

Lời giải ngây thơ quá chậm. Chẳng hạn, xét trường hợp có một sợi dây dài \(10^9\) và hai điểm \((0,0)\) cùng \((0,1)\). Lời giải tối ưu dùng toàn bộ chiều dài dây để tạo ra \(10^9-1\) khúc uốn. Rõ ràng ta chỉ đang đi vòng lặp, nên muốn có cơ hội đạt thời gian đa thức, ta cần một cách phát hiện và xử lý những vòng lặp như vậy.

Trước hết, hãy tổ chức lại lời giải DP ngây thơ một chút để việc phát hiện vòng lặp dễ hơn. Ta sẽ dùng một trạng thái ba tham số đơn giản hơn và một hàm đệ quy có ghi nhớ. Mỗi lời gọi hàm tương ứng với một tình huống như sau: ta đang quay quanh điểm \(P\), đầu dây chỉ theo hướng \((dx,dy)\), và ta vừa cắt dây vì nó chạm một điểm khác \(Q\). Tổng số trạng thái như vậy là \(O(N^3)\), nhưng nhiều trạng thái không thể xảy ra và sẽ không bao giờ được thăm.

Bên trong hàm, ta mô phỏng quá trình quấn dây và gọi đệ quy mỗi khi quyết định cắt dây thêm. Nếu mô phỏng quá trình quấn một cách ngây thơ, có thể phải thực hiện một số lượng khổng lồ lời gọi đệ quy. Thay vào đó, hãy tưởng tượng ta vừa uốn dây quanh một điểm \(A\) và sắp uốn tiếp quanh điểm \(B\). Nếu đây không phải lần đầu nhìn thấy cặp \((A,B)\), thì ta đang lặp quanh cùng một tập điểm. Khi chạm cặp này lần thứ hai, độ dài dây còn lại \(r\) sẽ ngắn hơn; ta có thể tính lượng dây mà một vòng quay tiêu thụ bằng cách lấy giá trị \(r\) ở lần gặp đầu trừ đi giá trị mới.

Sau khi phát hiện một vòng lặp, ta có thể chọn số vòng đầy đủ muốn thực hiện trước khi cắt dây và đi vào bên trong bao lồi của những điểm đang được quấn quanh. Rõ ràng không bao giờ có lợi khi cắt bỏ nhiều hơn một chu vi trọn vẹn của vòng lặp, vì như vậy ta đang vứt bỏ các khúc uốn miễn phí. Do đó, số vòng tối ưu bằng phần nguyên của tổng độ dài dây còn lại chia cho chu vi vòng lặp, rồi trừ đi một:

Ghép thành lời giải hoàn chỉnh

Ta có một lời giải DP với \(O(N^3)\) trạng thái và \(O(N^2)\) công việc cho mỗi trạng thái: số lời gọi đệ quy là tuyến tính, và mỗi lời gọi cần lượng công việc tuyến tính để tìm điểm kế tiếp. Có thể tăng tốc bằng cách tiền xử lý điểm kế tiếp cho mỗi trạng thái, nhưng điều đó không cần thiết. Trên thực tế, số trạng thái có thể đạt tới đủ nhỏ để lời giải này vượt qua giới hạn.

Khó khăn còn lại là xử lý các điểm thẳng hàng. Vì mọi tọa độ đều là số nguyên, việc này cần được thực hiện chính xác, không dùng phép tính số thực.

Nguồn

Bản dịch đầy đủ dựa trên phân tích chính thức của Google Code Jam 2010 - Ninjutsu, thuộc kho Google Coding Competitions (Apache-2.0).