Phân tích

Test set 1

Gọi một cặp \((L, R)\) là công bằng nếu việc chọn nó tạo ra một trận đấu công bằng. Vì chỉ có \(100\) phần tử nên có nhiều nhất \(100 \times 101 / 2 = 5050\) đoạn. Với mỗi đoạn, ta có thể tìm giá trị lớn nhất trong từng mảng bằng cách duyệt tuyến tính rồi kiểm tra xem hai giá trị lớn nhất có đủ gần nhau hay không.

Test set 2

Việc chọn kiếm ngẫu nhiên khi đồng hạng không làm thay đổi việc \((L, R)\) có công bằng hay không. Vì vậy, ta có thể giả sử khi đồng hạng thì kiếm có chỉ số nhỏ nhất được chọn. Để phần trình bày đơn giản hơn, giả sử mọi \(C_i\) đôi một khác nhau.

Xét bài toán con: với mỗi kiếm \(i\) mà Charles có thể chọn, có bao nhiêu đoạn công bằng \((L,R)\) khiến Charles chọn kiếm \(i\)? Gọi giá trị này là \(F_i\). Đáp án ban đầu là tổng các \(F_i\). Với mỗi đoạn \((L,R)\), ta quan tâm ba tính chất:

• (P1) Charles chọn kiếm \(i\): \(L \le i \le R\) và \(\max(C_L,C_{L+1},\ldots,C_R)=C_i\).
• (P2) Kiếm của Charles đủ tốt: \(\max(D_L,D_{L+1},\ldots,D_R) \le C_i+K\).
• (P3) Kiếm của Charles quá tốt: \(\max(D_L,D_{L+1},\ldots,D_R) < C_i-K\).

Do đó, \(F_i =\) (số đoạn thỏa P1 và P2) \(-\) (số đoạn thỏa P1 và P3). Hai đại lượng được tính rất giống nhau vì chỉ khác cận bên phải của bất đẳng thức trong P2 và P3. Dưới đây chỉ trình bày cách tính số đoạn thỏa P1 và P2; cách tính số đoạn thỏa P1 và P3 được dành cho người đọc.

Nếu \((L,R)\) thỏa P2 thì mọi đoạn con của nó cũng thỏa P2. Tương tự, nếu \((L,R)\) thỏa P1 thì mọi đoạn con vẫn chứa \(i\) cũng thỏa P1. Vì thế, ta chỉ cần biết \(L\) có thể đi xa về trái đến đâu khi \(R=i\) (và \(R\) có thể đi xa về phải đến đâu khi \(L=i\)). Duyệt tuyến tính để tìm biên trái là quá chậm. Thay vào đó, ta tìm kiếm nhị phân khoảng cách của đầu mút trái. Đầu mút trái là quá xa nếu P1 hoặc P2 không còn đúng; nếu không, có thể đẩy nó xa hơn về trái. Khi biết biên trái xa nhất \(L_i\) và biên phải xa nhất \(R_i\), ta có

Giá trị lớn nhất trên một đoạn có thể được tính hiệu quả bằng cấu trúc dữ liệu dạng truy vấn cực tiểu (cực đại) trên đoạn, trong \(O(1)\) cho mỗi truy vấn, nên cả phép tìm kiếm nhị phân mất \(O(\log N)\) thời gian.

Với mỗi \(i\), ta thực hiện \(4\) phép tìm kiếm nhị phân, mỗi phép tốn \(O(\log N)\), nên tổng thời gian là \(O(N\log N)\). Xây dựng cấu trúc truy vấn cực đại tốn thêm \(O(N\log N)\), do đó toàn thuật toán vẫn là \(O(N\log N)\). Có những lời giải tính được tất cả \(L_i\) và \(R_i\) cần thiết trong tổng thời gian \(O(N)\) bằng vài lượt quét khéo léo để đếm số đoạn không công bằng, nhưng điều đó không cần thiết cho bài này.

Dữ liệu kiểm thử

Chúng tôi khuyên bạn luyện tập gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2019, Vòng 1B — Fair Fight.