Phân tích: RPI

Đề bài đã giải thích chính xác những gì cần làm ở đây. Bạn chỉ cần làm theo các hướng dẫn và đừng để bị nhầm lẫn! Chúng tôi muốn đưa ra một bài khởi động trước hai bài toán tiếp theo, cả hai đều khá hóc búa.

Đầu tiên, tỉ lệ thắng (WP) của mỗi đội cần được tính toán. Điều này khá đơn giản vì WP của đội \(i\) chỉ phụ thuộc vào thành tích của đội \(i\). Để thực hiện phần này, chúng ta cần biết tổng số trận thắng của mỗi đội, cũng như tổng số trận đã đấu. Sau đó, chúng ta có thể tính \(WP[i] = Wins[i] / Total[i]\).

Tiếp theo, OWP của mỗi đội cần được tính toán, nhưng OWP yêu cầu một WP đã được sửa đổi cho mỗi đối thủ. Hãy xem xét \(WP'[i][j]\), tỉ lệ thắng của đội \(i\) nếu bạn loại trừ các trận đấu với đội \(j\). Để tính \(WP'[i][j]\), chúng ta phải xem xét ba trường hợp có thể xảy ra:

1. Nếu đội \(i\) chưa bao giờ đấu với đội \(j\), thì \(WP'\) không có ý nghĩa và có thể bỏ qua.
2. Nếu đội \(i\) có đấu với đội \(j\) và đã thắng trận đó, thì \(WP'[i][j] = (Wins[i] - 1) / (Total[i] - 1)\).
3. Nếu đội \(i\) có đấu với đội \(j\) và đã thua trận đó, thì \(WP'[i][j] = (Wins[i]) / (Total[i] - 1)\).

Tất cả những gì cần làm để tính \(WP'\) là thử tất cả các cặp đội và tính giá trị nếu hai đội đó đã đấu với nhau.

Bây giờ chúng ta đã có \(WP'\) cho mọi cặp đội, chúng ta có thể tính các giá trị OWP. Gọi \(S[i]\) là tập hợp các đội mà đội \(i\) đã đấu. Sau đó, chúng ta có thể tính \(OWP[i]\) như sau:

OWPSum[i] = 0
cho mỗi đội j trong S[i]:
    OWPSum[i] += WP'[j][i]
OWP[i] = OWPSum[i] / size(S[i])

Cuối cùng, chúng ta cần tính OOWP cho mọi đội \(i\). OOWP sử dụng OWP mà chúng ta đã tính toán:

OOWPSum[i] = 0
cho mỗi đội j trong S[i]:
    OOWPSum[i] += OWP[j]
OOWP[i] = OOWPSum[i] / size(S[i])

Sau cùng, chúng ta có thể kết hợp mọi thứ bằng công thức:
\(RPI[i] = WP[i] \times 0.25 + OWP[i] \times 0.5 + OOWP[i] \times 0.25\).

Nhân tiện, công thức này thực sự đang được sử dụng trong thực tế. Tuy nhiên, nó không phải lúc nào cũng tốt trong việc xếp hạng các đội!

Độ phức tạp

Với \(N\) là số lượng đội:

• Tính WP cho tất cả các đội: \(O(N^2)\) để duyệt qua bảng lịch thi đấu.
• Tính \(WP'[i][j]\) cho mọi cặp: \(O(N^2)\).
• Tính OWP cho tất cả các đội: \(O(N^2)\).
• Tính OOWP cho tất cả các đội: \(O(N^2)\).
• Tổng độ phức tạp: \(O(N^2)\) mỗi bộ test, hoàn toàn phù hợp với \(N \le 100\).

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