Phân tích: Twirling Towards Freedom

Tập dữ liệu nhỏ (Small Input)

Trong hầu hết các bài toán Google Code Jam, tập dữ liệu nhỏ có thể được giải quyết mà không cần lo lắng về thời gian chạy. Tuy nhiên, trường hợp này thì khác. Ngay cả khi \(N = 10\) và \(M = 10\), vẫn có \(10^{10}\) kiểu xoay khác nhau mà bạn có thể thử. Đó là một con số rất lớn!

Có nhiều cách để giảm thời gian chạy xuống mức có thể quản lý được, nhưng có một sự thật giúp mọi thứ trở nên dễ dàng:

• Ngôi sao thứ 1, thứ 5 và thứ 9 bạn xoay quanh nên là cùng một ngôi sao.
• Ngôi sao thứ 2, thứ 6 và thứ 10 bạn xoay quanh nên là cùng một ngôi sao.
• Ngôi sao thứ 3 và thứ 7 bạn xoay quanh nên giống nhau.
• Ngôi sao thứ 4 và thứ 8 bạn xoay quanh nên giống nhau.

Nếu bạn nhận ra điều này, chỉ có \(10^4\) khả năng để thử. Nhưng tại sao điều này lại đúng? Hãy đọc tiếp để tìm hiểu!

Hiểu về các phép xoay

Một trong những thách thức lớn nhất ở đây là hiểu được bản chất vấn đề. Làm thế nào bạn có thể hình dung việc xoay một vật gì đó 100.000.000 lần? Cách tốt nhất là viết ra một vài công thức.

Khi xử lý các phép xoay và tịnh tiến các điểm trên mặt phẳng, số phức cung cấp một cách ký hiệu tuyệt vời:

• Một điểm \((x, y)\) có thể được biểu diễn dưới dạng \(x + iy\).
• Số phức có thể được cộng và trừ giống như vectơ.
• Số phức có thể được xoay 90 độ theo chiều kim đồng hồ quanh gốc tọa độ đơn giản bằng cách nhân chúng với \(-i\).

Chính tính chất cuối cùng này làm cho chúng trở nên gọn gàng khi làm việc. Nếu muốn, bạn cũng có thể tưởng tượng việc thay thế mọi thứ bằng ma trận.

Chúng ta biết rằng việc xoay một điểm \(P_0\) đi 90 độ quanh gốc tọa độ sẽ đưa nó đến \(-i \cdot P_0\). Tuy nhiên, điều gì xảy ra nếu chúng ta xoay nó quanh một điểm khác \(Q_0\)? Có một công thức tiêu chuẩn cho tình huống này: điểm kết quả \(P_1\) thỏa mãn:

Đây là công thức trước đó của chúng ta áp dụng cho việc xoay \(P_0 - Q_0\) đi 90 độ quanh gốc tọa độ phải cho bạn \(P_1 - Q_0\). Trong trường hợp của chúng ta, sẽ hữu ích nếu nhóm các thành phần trong công thức hơi khác một chút:

Bây giờ, giả sử chúng ta xoay \(P_1\) đi 90 độ quanh một điểm khác \(Q_1\), sau đó xoay 90 độ quanh một điểm khác \(Q_2\), và cứ tiếp tục như vậy. Điều gì sẽ xảy ra với công thức này? Hãy viết ra một vài ví dụ:

• \(P_2 = -iP_1 + Q_1 \cdot (1 - i) = -P_0 + Q_1 \cdot (1 - i) + Q_0 \cdot (-1 - i)\).
• \(P_3 = -iP_2 + Q_2 \cdot (1 - i) = iP_0 + Q_2 \cdot (1 - i) + Q_1 \cdot (-1 - i) + Q_0 \cdot (-1 + i)\).
• \(P_4 = -iP_3 + Q_3 \cdot (1 - i) = P_0 + Q_3 \cdot (1 - i) + Q_2 \cdot (-1 - i) + Q_1 \cdot (-1 + i) + Q_0 \cdot (1 + i)\).
• \(P_5 = -iP_4 + Q_4 \cdot (1 - i) = -iP_0 + (Q_4 + Q_0) \cdot (1 - i) + Q_3 \cdot (-1 - i) + Q_2 \cdot (-1 + i) + Q_1 \cdot (1 + i)\).
• v.v.

Từ đây, không quá khó để đoán công thức tổng quát. Nếu gốc tọa độ được xoay 90 độ quanh \(Q_0\), sau đó là \(Q_1\), và cứ thế cho đến \(Q_{m-1}\), thì điểm kết quả cuối cùng \(P_m\) được cho bởi:

Khi công thức đã được viết ra, việc kiểm tra xem nó có luôn đúng hay không không quá khó. Dù sao thì, điều này có đơn giản hơn cách phát biểu bài toán ban đầu không? Nó có vẻ khá phức tạp, nhưng về cơ bản, bây giờ bạn chỉ đang cộng các điểm lại với nhau, và phép cộng thì dễ hơn phép xoay!

Chọn một hướng

Chúng ta muốn chọn các ngôi sao \(Q_0, Q_1, \dots, Q_{m-1}\) sao cho điểm sau đây càng xa gốc tọa độ càng tốt:

Có nhiều cách suy nghĩ khác nhau từ đây, nhưng chìa khóa luôn là bao lồi (convex hull).

Gọi \(X\) là điểm xa gốc tọa độ nhất mà chúng ta có thể đạt được, và tổng quát hơn, gọi \(X_v\) là điểm xa nhất theo hướng \(v\) mà chúng ta có thể đạt được. Chắc chắn \(X = X_v\) đối với một \(v\) nào đó. Do đó, chỉ cần tính \(X_v\) cho mọi \(v\), và sau đó chúng ta có thể đo xem điểm nào trong số này xa gốc tọa độ nhất để có câu trả lời cuối cùng.

Vậy làm thế nào để tính \(X_v\) cho một \(v\) nhất định? Chúng ta muốn \((1 - i) \cdot Q_{m-1}\) càng xa càng tốt theo hướng \(v\), hoặc tương đương, chúng ta muốn \(Q_{m-1}\) là ngôi sao xa nhất theo hướng \((1 + i) \cdot v\). Tất nhiên, điều tương tự cũng đúng cho \(Q_{m-5}, Q_{m-9}\), v.v. Chúng ta nên chọn cùng một ngôi sao cho tất cả chúng. Tương tự, đối với \(Q_{m-2}, Q_{m-6}\), v.v., chúng ta muốn chọn ngôi sao xa nhất theo hướng \((-1 + i) \cdot v\). Nói chung, chúng ta muốn chọn các ngôi sao từ tập hợp ban đầu xa nhất theo các hướng sau: \((1 + i) \cdot v, (-1 + i) \cdot v, (-1 - i) \cdot v, (1 - i) \cdot v\).

Đến đây chúng ta gần như đã hoàn thành. Đầu tiên, chúng ta tìm bao lồi của các ngôi sao và giải cho một \(v\) cụ thể. Bây giờ điều gì xảy ra khi chúng ta xoay \(v\)? Trong một thời gian, sẽ không có gì thay đổi, nhưng cuối cùng, một trong bốn hướng chúng ta đang cố gắng tối ưu hóa sẽ vuông góc với một cạnh của bao lồi, và kết quả là, ngôi sao tối ưu sẽ chuyển sang điểm tiếp theo trên bao lồi. Việc mô phỏng này có thể được thực hiện trong thời gian không đổi ở mỗi bước, và sẽ chỉ có \(O(N)\) bước vì mỗi lựa chọn ngôi sao sẽ xoay một vòng quanh bao lồi.

Tại thời điểm này, chúng ta đã xong! Chúng ta đã tìm thấy mọi \(X_v\), và chúng ta có thể kiểm tra thủ công từng điểm để xem điểm nào là tốt nhất. Việc cài đặt ở đây khá lắt léo, nhưng nó là một ví dụ của kỹ thuật tổng quát gọi là thước cặp xoay (rotating calipers).

Câu hỏi phụ!

Khi chúng tôi tạo dữ liệu thử nghiệm cho bài toán này, chúng tôi đã ngạc nhiên khi thấy rằng mình không thể đưa ra một trường hợp nào để làm sai các giải pháp đọc nhầm "theo chiều kim đồng hồ" thành "ngược chiều kim đồng hồ" trong đề bài. Trên thực tế, không có trường hợp như vậy! Bạn có biết tại sao không?

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