Phân tích

Bài toán này có thể được xem như một phiên bản sửa đổi của việc tìm chiều rộng tối thiểu của một bao lồi (convex hull), có thể được giải quyết bằng kỹ thuật thước cặp quay (rotating calipers) đã được sửa đổi. Dưới đây là trực giác tại sao bài toán này tương tự như việc tìm chiều rộng tối thiểu sửa đổi của bao lồi.

Đầu tiên, chúng ta có thể biểu diễn chuỗi các lần gõ trống dưới dạng các điểm \((i, T_i)\) trên mặt phẳng 2 chiều. Nếu người đánh trống biểu diễn hoàn hảo, gọi chuỗi đó là \(P_i\), thì các điểm \((i, P_i)\) sẽ nằm trên cùng một đường thẳng \(L\) (xem Hình 1 và Hình 2).

Hình 1

Hình 2

Không may là người đánh trống không biểu diễn hoàn hảo và có sai số \(E_i\) (chính là \(|T_i - P_i|\)) (xem Hình 3).

Hình 3

Trong ví dụ ở Hình 3, chúng ta có đường thẳng \(L\), và rõ ràng là câu trả lời của chúng ta là giá trị lớn nhất trong số tất cả các \(E_i\), trong trường hợp này là \(E_1\) (hoặc \(E_2\) hoặc \(E_4\)). Nếu chúng ta vẽ hai đường thẳng song song với \(L\) và dịch chuyển trên trục y một khoảng \(+E_1\) và \(-E_1\), ký hiệu là \(L_{+E_1}\) và \(L_{-E_1}\) (xem Hình 3), bạn sẽ nhận thấy rằng vùng giữa hai đường thẳng này chứa tất cả các điểm \((i, T_i)\); ví dụ này khớp với định nghĩa của bài toán là một nhịp trống mà mỗi lần gõ khác biệt tối đa \(E\) so với một nhịp điệu hoàn hảo nào đó. Mặt khác, nếu chúng ta chọn \(E_5\) làm sai số ứng viên, vùng giữa hai đường thẳng \(L_{+E_5}\) và \(L_{-E_5}\) sẽ không chứa tất cả các điểm \((i, T_i)\) (xem Hình 4).

Hình 4

Về bản chất, chúng ta muốn tìm một đường thẳng biểu diễn nhịp điệu hoàn hảo và hai đường thẳng song song được dịch chuyển trên trục y một khoảng \(+E\) và \(-E\) sao cho hai đường thẳng song song đó chứa tất cả các điểm \((i, T_i)\) và \(E\) là giá trị nhỏ nhất có thể. Lưu ý rằng thay vì cố gắng tìm đường thẳng nhịp điệu hoàn hảo (vốn có thể là một bài toán khó do sai số liên quan đến mỗi điểm \((i, T_i)\)), chúng ta có thể tập trung vào bài toán tương đương là tìm hai đường thẳng song song. Lưu ý rằng mỗi đường thẳng này phải chạm vào ít nhất một điểm, nếu không chúng ta luôn có thể giảm khoảng cách giữa hai đường thẳng này, và từ đó giảm khoảng cách trên trục y để có sai số \(E\) nhỏ hơn.

Thực tế, tất cả các cặp đường thẳng song song ứng viên đều tiếp xúc (mà không cắt) bao lồi của các điểm \((i, T_i)\). Do đó, chúng ta chuyển đổi bài toán thành việc tìm khoảng cách tối thiểu giữa hai đường thẳng song song theo trục y tiếp xúc (mà không cắt) bao lồi. Ví dụ, bao lồi của các điểm trong Hình 2 được hiển thị trong Hình 5.

Hình 5

Vì vậy, để giải bài toán này, trước tiên chúng ta tính bao lồi của các điểm \((i, T_i)\). Sau đó, chúng ta đi qua tất cả các đoạn thẳng trên biên của bao lồi và tìm đường thẳng song song tương ứng ở phía đối diện của bao lồi (xem Hình 5 cho một số ví dụ), sau đó lấy khoảng cách theo trục y giữa hai đường thẳng song song này, và báo cáo giá trị nhỏ nhất trong số tất cả các khoảng cách y đó.

Lưu ý rằng sai số \(E\) cần tìm sẽ bằng một nửa khoảng cách theo trục y nhỏ nhất này, vì đường thẳng nhịp điệu hoàn hảo \(L\) nằm chính giữa hai đường thẳng song song đó.

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