Từ vét cạn đến bài toán độ dốc

Chiến lược vét cạn \(O(N^2)\) đủ cho bộ nhỏ: tính số lượng số 1 tích lũy tại mỗi vị trí rồi thử mọi cặp điểm đầu và cuối. Nhưng ở bộ lớn, \(N\) có thể tới nửa triệu.

Đọc chuỗi từ trái sang phải và gọi \(O_i\) là số chữ số 1 đã thấy sau \(i\) chữ số đầu. Xét mọi \(i\) từ 0 tới \(N\), bao gồm cả tiền tố rỗng và toàn bộ chuỗi. Duy trì một tập điểm, ban đầu rỗng, và thêm

Tỉ lệ số 1 trong đoạn con bắt đầu tại vị trí \(i+1\) và kết thúc tại \(j\) là \((O_j-O_i)/(j-i)\). Sai lệch so với \(F\) là

chính là độ dốc giữa \(p_i\) và \(p_j\). Vì vậy, tìm \(p_i,p_j\) làm trị tuyệt đối của độ dốc nhỏ nhất tương đương với giải bài toán ban đầu.

Chỉ cần hai điểm kề theo tung độ

Không dễ nhận ra nhưng dễ chứng minh rằng độ dốc có trị tuyệt đối nhỏ nhất xuất hiện giữa hai điểm liên tiếp sau khi sắp theo tung độ. Nếu một điểm \(r\) có tung độ nằm giữa tung độ của hai điểm \(p,q\), gọi độ dốc giữa \(p,q\) là \(s\). Độ dốc \(s\) là trung bình có trọng số của các độ dốc giữa \(p,r\) và giữa \(q,r\); hoặc cả hai cùng bằng \(s\), hoặc một trong hai phải nhỏ hơn \(s\).

Có thể hình dung bằng cách vẽ đoạn \(pq\) và đặt \(r\) trên đoạn ấy: cả ba độ dốc bằng nhau. Khi dịch \(r\) theo phương ngang, rõ ràng độ dốc của một trong hai đoạn \(pr,qr\) tăng còn độ dốc kia giảm.

Nhận xét này loại bỏ việc thử mọi cặp điểm. Chỉ cần một lần sắp xếp rồi xét các cặp kề theo tung độ.

Độ phức tạp

Thời gian \(O(N\log N)\), do duy nhất thao tác sắp xếp.

Nguồn

Bản dịch dựa trên phân tích chính thức Google Code Jam 2015 - World Finals - Pretty Good Proportion, kho Google Coding Competitions (Apache-2.0).