Test Set 1

Test Set 1 có thể được giải bằng cách mô phỏng cuộc thi:

1. Duyệt qua tất cả các ô của sàn. Với mỗi ô đang có một vũ công:
2. Cộng trình độ của người đó vào mức độ hấp dẫn của cuộc thi.
3. Duyệt hàng và cột của người đó để tìm tất cả các hàng xóm theo hướng la bàn.
4. Đếm số hàng xóm theo hướng la bàn và tính tổng trình độ của họ.
5. Nếu trình độ trung bình của các hàng xóm (tổng trình độ chia cho số hàng xóm) lớn hơn trình độ của vũ công hiện tại, thêm vũ công này vào danh sách bị loại.
6. Duyệt danh sách bị loại và loại các vũ công trong danh sách. Việc lập xong toàn bộ danh sách trước khi loại bảo đảm mọi quyết định của một vòng đều dùng trạng thái của chính vòng đó; một người sắp bị loại vẫn tham gia vào việc xét những người khác.
7. Nếu danh sách bị loại rỗng thì kết thúc. Nếu không, quay lại bước \(1\).

Mỗi lần lặp của thuật toán trên có độ phức tạp thời gian \(O(R \times C \times (R+C))\): ta xét \(R \times C\) ô, và việc tìm hàng xóm của một ô bằng cách quét hàng cùng cột có thể tốn \(O(R+C)\). Số lần lặp bằng số vòng của cuộc thi và không thể lớn hơn tổng số vũ công \(R \times C\): trừ vòng cuối, mỗi vòng đều loại ít nhất một người. Vì vậy, tổng độ phức tạp thời gian là \(O(R^2 \times C^2 \times (R+C))\).

Thuật toán này đủ cho Test Set 1. Nếu lưu trực tiếp trạng thái còn thi đấu của từng ô và danh sách bị loại, độ phức tạp bộ nhớ là \(O(R \times C)\).

Test Set 2

Ta tối ưu lời giải của Test Set 1, cụ thể là hai phần sau:

• Trong mỗi vòng, ta đang duyệt cả \(R \times C\) ô để kiểm tra từng vũ công có bị loại hay không.
• Với mỗi vũ công, ta có thể phải duyệt một phần đáng kể của hàng và cột để tìm các hàng xóm theo hướng la bàn.

Chỉ kiểm tra những ứng viên có thể thay đổi kết quả

Để cải thiện điểm thứ nhất, xét một vòng \(i>1\). Nếu vũ công \(d\) không bị loại ở vòng \(i-1\) nhưng lại bị loại ở vòng \(i\), thì tập hàng xóm theo hướng la bàn của \(d\) hẳn đã thay đổi giữa hai vòng. Muốn có thay đổi đó, ít nhất một hàng xóm theo hướng la bàn của \(d\) phải bị loại ở vòng \(i-1\).

Đây cũng là lý do ta không bỏ sót ai khi chỉ xét các ứng viên nói trên: trình độ của mọi vũ công là cố định; nếu tập hàng xóm của một người không đổi thì số hàng xóm, tổng trình độ hàng xóm và do đó điều kiện bị loại của người đó đều không đổi. Một người đã sống sót ở vòng trước sẽ tiếp tục sống sót.

Vì vậy, thay vì kiểm tra mọi vũ công ở vòng \(i\), ta chỉ cần kiểm tra các hàng xóm theo hướng la bàn của những người bị loại ở vòng \(i-1\). Tại thời điểm bị loại, một vũ công có nhiều nhất \(4\) hàng xóm theo hướng la bàn, nên độ dài danh sách ứng viên cần kiểm tra ở vòng \(i\) không vượt quá \(4\) lần độ dài danh sách bị loại của vòng \(i-1\). Tổng độ dài của mọi danh sách bị loại không vượt quá \(R \times C\), bởi mỗi vũ công chỉ bị loại một lần. Do đó, tổng độ dài của mọi danh sách ứng viên không vượt quá \(4 \times R \times C\). Kể cả lần kiểm tra ban đầu đối với tất cả các vũ công, cải tiến này khiến tổng số lượt kiểm tra chỉ còn \(O(R \times C)\). Nếu một người được đưa vào danh sách ứng viên từ nhiều hàng xóm vừa bị loại, có thể dùng một dấu thời gian hoặc tập hợp để tránh kiểm tra trùng trong cùng vòng.

Tìm và cập nhật hàng xóm trong thời gian hằng số

Để tối ưu việc tìm hàng xóm theo hướng la bàn, hãy quan sát điều gì xảy ra khi xóa một vũ công. Hàng xóm phía đông của người bị xóa trở thành hàng xóm phía đông của hàng xóm phía tây, và ngược lại. Tương tự, hàng xóm phía nam và phía bắc được nối lại với nhau.

Vì thế, thay vì tìm lại hàng xóm mỗi khi cần, với mỗi vũ công ta lưu vị trí cụ thể của hàng xóm gần nhất ở từng hướng: bắc, nam, tây và đông. Ban đầu, bốn liên kết này trỏ tới các ô kề trực tiếp nếu chúng tồn tại. Các liên kết theo mỗi hàng tạo thành một danh sách liên kết kép, và các liên kết theo mỗi cột tạo thành một danh sách liên kết kép khác.

Khi loại một ô \(d\), ta nối trực tiếp hai đầu còn sống ở mỗi trục:

• Nếu tồn tại hàng xóm tây \(w\) và hàng xóm đông \(e\), đặt hàng xóm đông của \(w\) thành \(e\) và hàng xóm tây của \(e\) thành \(w\); nếu thiếu một đầu, liên kết tương ứng trở thành rỗng.
• Làm hoàn toàn tương tự với hàng xóm bắc và nam.

Mỗi thao tác xóa và tìm các hàng xóm hiện tại vì vậy chỉ tốn \(O(1)\). Cần lưu ý rằng trước tiên phải xác định toàn bộ danh sách bị loại của vòng hiện tại, sau đó mới cập nhật các liên kết cho những người bị loại. Nhờ đó, mọi phép kiểm tra trong một vòng đều nhìn thấy cùng một trạng thái, đúng với yêu cầu loại đồng thời. Sau khi cập nhật, các hàng xóm còn sống của những người vừa bị loại trở thành danh sách ứng viên cho vòng kế tiếp.

Ta cũng duy trì current_sum, tổng trình độ của tất cả vũ công còn thi đấu. Ở đầu mỗi vòng, cộng current_sum vào đáp án. Sau khi đã chốt danh sách bị loại của vòng ấy, trừ trình độ của từng người bị loại khỏi current_sum, cập nhật các liên kết, rồi chuyển sang vòng tiếp theo. Nếu danh sách bị loại rỗng, giá trị của vòng cuối đã được cộng và thuật toán dừng. Để tránh số thực, một vũ công có trình độ \(s\), có \(k\) hàng xóm với tổng trình độ \(q\), bị loại khi và chỉ khi \(k>0\) và \(s \times k < q\).

Tính đúng đắn

Ở vòng đầu, mọi vũ công đều được kiểm tra nên danh sách bị loại được xác định đúng theo đề bài. Giả sử đến một vòng nào đó, các liên kết đang trỏ đúng tới bốn hàng xóm theo hướng la bàn hiện tại. Khi xóa đồng thời một tập vũ công, việc nối mỗi hàng xóm còn sống qua các ô bị xóa sẽ bỏ qua chính xác những người không còn thi đấu; vì vậy sau mọi cập nhật, các liên kết tiếp tục trỏ tới người còn sống gần nhất ở từng hướng.

Theo quan sát ở trên, giữa hai vòng, điều kiện của một người chỉ có thể thay đổi nếu ít nhất một hàng xóm của họ vừa bị loại. Mọi người như vậy đều được thêm vào danh sách ứng viên, còn những người không được thêm có nguyên tập hàng xóm và vẫn giữ kết quả “không bị loại” của vòng trước. Do đó, ta xác định đúng và đầy đủ danh sách bị loại ở từng vòng. current_sum đúng bằng tổng trình độ người đang thi đấu, nên lượng cộng vào đáp án ở mỗi vòng chính là mức độ hấp dẫn của vòng đó. Vì thuật toán dừng đúng khi không còn ai bị loại, tổng thu được là mức độ hấp dẫn của toàn bộ cuộc thi.

Độ phức tạp

Nhờ tối ưu thứ nhất, có tổng cộng \(O(R \times C)\) lượt kiểm tra. Nhờ tối ưu thứ hai, mỗi lượt kiểm tra và mỗi cập nhật liên kết tốn \(O(1)\). Vì thế, độ phức tạp thời gian là \(O(R \times C)\) và độ phức tạp bộ nhớ là \(O(R \times C)\), đủ nhanh cho Test Set 2.

Phân tích dựa trên lời giải chính thức của Google Code Jam 2020.