Hướng dẫn giải của Khủng bố
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Xem mỗi quả bom là một đỉnh trong đồ thị, hai đỉnh ~(i, j)~ có cạnh nối nếu kích nổ quả bom ~i~ có thể khiến quả bom ~j~ nổ theo (và ngược lại). Khi đó, một miền liên thông sẽ chặn được đường đi từ điểm ~(0, 0)~ đến ~(n, n)~ nếu:
- ~\min(x_i) - l \le 0~ hoặc ~\max(y_i) + l \ge n~, và
- ~\max(x_i) + l \ge n~ hoặc ~\min(y_i) - l \le 0~.
Từ đây, ta có ý tưởng giải bài toán như sau:
Subtask 2
Ở subtask này, chúng ta có thể xét tất cả các cặp bom và kiểm tra điều kiện tạo cạnh nối, sau đó dựng đồ thị và kiểm tra các miền liên thông bằng cách sử dụng BFS/DFS hoặc DSU. Vì đồ thị của ta có thể có tối đa ~m^2~ cạnh, độ phức tạp của thuật toán này là ~O(m^2)~.
Subtask 3
Xét hai quả bom ~(x_i, y_i)~ và ~(x_j, y_j)~, chúng sẽ có cạnh nối nếu ~x_i - l \le x_j \le x_i + l~ và ~y_i - l \le y_j \le y_i + l~. Vì vậy, ta có thể sử dụng thuật toán đường quét như sau:
- Duyệt qua các quả bom theo chiều ~x~ tăng dần. Giả sử ta đang xét tới quả bom ~(x_i, y_i)~, ta sẽ sử dụng cấu trúc dữ liệu
setđể quản lý các quả bom có tọa độ ~x~ nằm trong khoảng ~[x_i - l, x_i]~. - Ta sẽ nối cạnh từ quả bom ~(x_i, y_i)~ tới ~2~ quả bom bất kì: quả bom thứ nhất có tọa độ ~y~ nằm trong khoảng ~[y_i - l, y_i]~, và quả bom thứ hai có tọa độ ~y~ nằm trong khoảng ~[y_i, y_i + l]~ (vì sao chỉ cần nối ~2~ cạnh là đủ?)
Sau khi dựng được đồ thị, ta có thể làm tương tự subtask 2. Vì đồ thị của ta chỉ có tối đa ~2m~ cạnh, kết hợp với độ phức tạp của set, ta có được độ phức tạp cuối cùng là ~O(m \log m)~.
Bình luận
Nhận xét
Em đang nghĩ chứng minh nhận xét này bằng quy nạp nhưng chưa rõ ràng ý tưởng lắm :)
Edit:
Một cách nối cạnh là đúng khi: với mỗi điểm ~(x,y)~, tất cả những điểm ~(x',y')~ thỏa ~x-L \le x' \le x, \quad y-L \le y' \le y+L~ đều thuộc vào cùng TPLT với nó ~(*)~. Tạm gọi đây là tập những điểm "gần kề" ~(x,y)~.
Trong thuật toán ở trên, ta xét các điểm theo thứ tự ~x~ tăng dần.
Giả sử khi duyệt tới ~(x,y)~, tất cả những điểm trước nó đều thỏa mãn tính chất ~(*)~ ở trên. Ta sẽ chứng minh rằng: Bằng hai cạnh nối từ ~(x,y)~ tới ~(x_1,y_1), (x_2, y_2)~ mà ~x \ge x_1,x_2 \ge x-L~ và ~y_1 \in [y-L,y], y_2 \in [y,y+L]~ thì ~(x,y)~ cũng thỏa mãn tính chất trên.
Theo giả thiết quy nạp, nếu nối ~A \, (x,y)~ với ~B \, (x_1,y_1)~ thì ~A~ sẽ liên thông với "vùng màu xanh lá" (tập những điểm ~(x',y')~ mà ~x_1 \ge x' \ge x_1 - L~ và ~y_1 - L \le y' \le y_1 + L~).
Nếu có tồn tại điểm ~(u,v)~ nào thuộc vùng xanh dương, theo giả thiết quy nạp thì ta cũng có ~B~ thuộc vào cùng TPLT với ~(u,v)~, vì ~B~ thuộc vào tập điểm "gần kề" của ~(u,v)~.
Vậy, tóm lại, mọi điểm ~(u,v)~ thỏa mãn ~\max(|u-x_1|, |v-y_1|) \le L~ đều thuộc vào cùng TPLT với ~B~. Phạm vi này bao phủ hình vuông ~(x-L,y-L); (x-L,y); (x,y-L); (x,y)~.
Lí luận tương tự, nếu nối ~A \, (x,y)~ với ~C \, (x_2,y_2)~ thì ~A~ cũng liên thông với mọi điểm thuộc hình vuông ~(x-L,y+L); (x-L,y); (x,y+L); (x,y)~.
Do đó, chỉ cần hai cạnh nối vào tập những điểm đã thỏa mãn sẵn tính chất ~(*)~, ~A~ cũng sẽ thỏa mãn tính chất ~(*)~. Tức cách nối này sẽ xét đúng & đủ các TPLT.