Phân tích: What are Birds?

Giải pháp đơn giản

Hãy trực quan hóa bài toán này. Mỗi con vật được đặc trưng bởi một cặp \((H, W)\), có thể được xem như một điểm trong hệ tọa độ Descartes hai chiều. Đối với mỗi con vật được biết là chim, chúng ta tô màu đỏ cho nó. Đối với mỗi con vật được biết không phải là chim, chúng ta tô màu xanh. Bài toán phát biểu rằng tồn tại một hình chữ nhật sao cho một điểm là màu đỏ nếu và chỉ nếu nó nằm trong hình chữ nhật đó. Bài toán trở nên tầm thường nếu không có điểm đỏ nào. Từ đây trở đi, chúng ta giả định rằng có các điểm đỏ.

Đối với bất kỳ hai điểm phân biệt \(U\) và \(V\) nào, tự nhiên có một hình chữ nhật được xác định bởi \(U\) và \(V\). Đó là hình chữ nhật nhỏ nhất chứa cả \(U\) và \(V\), với bốn góc là \(U, V, (H_U, W_V)\), và \((H_V, W_U)\). Khi \(U\) và \(V\) nằm trên cùng một đường nằm ngang hoặc thẳng đứng, hình chữ nhật sẽ suy biến thành một đoạn thẳng. Một cách chính thức, hình chữ nhật chứa tất cả các điểm \((H, W)\) sao cho:

Chúng ta có mệnh đề sau:

Nếu \(U\) và \(V\) là hai điểm đỏ và \(R\) là hình chữ nhật do \(U\) và \(V\) xác định, thì mọi điểm trong \(R\) cũng phải là điểm đỏ, vì mọi hình chữ nhật chứa cả \(U\) và \(V\) đều phải chứa \(R\).

Đối với tập hợp tất cả các điểm đỏ trong dữ liệu vào, cũng tự nhiên có một hình chữ nhật nhỏ nhất, \(R_0\), chứa tất cả chúng. Có nhiều cách khác nhau để định nghĩa hình chữ nhật này:

• (a) Giao của tất cả các hình chữ nhật chứa tất cả các điểm đỏ.
• (b) Hợp của tất cả các hình chữ nhật được xác định bởi \(U\) và \(V\), trong đó \((U, V)\) chạy qua tất cả các cặp điểm đỏ.
• (c) Hình chữ nhật với bốn góc \(A=(H_{min}, W_{min}), B=(H_{min}, W_{max}), C=(H_{max}, W_{min})\), và \(D=(H_{max}, W_{max})\), trong đó \(min\) và \(max\) được lấy trên tất cả các điểm đỏ.

Độc giả quan tâm có thể kiểm tra tính tương đương của các định nghĩa trên.

Bây giờ, cho một điểm \(X\), chúng ta muốn biết nó là chim hay không. Rõ ràng, nếu \(X\) nằm trong \(R_0\), thì nó phải là chim. Ngược lại, chúng ta có thể giả vờ nó là màu đỏ, và tính toán hình chữ nhật mới \(R'\) dựa trên định nghĩa (c). Việc này có thể được thực hiện bằng một số phép so sánh hằng số. Nếu có một điểm xanh nào từ dữ liệu vào nằm trong \(R'\), thì \(X\) chắc chắn không phải là chim. Ngược lại, \(X\) có thể (nếu lấy \(R'\) làm hình chữ nhật đỏ) hoặc không thể (nếu lấy \(R_0\) làm hình chữ nhật đỏ) là chim.

Với giới hạn của bài toán này, thuật toán \(\Theta(NM)\) là đủ nhanh. Nghĩa là, chúng ta chỉ cần lấy bất kỳ điểm xanh nào trong dữ liệu vào và kiểm tra xem nó có nằm trong \(R'\) hay không.

Thảo luận thêm

Một cách khác để xem xét bước cuối cùng của giải pháp, khi cho trước điểm truy vấn \(X\), là xem liệu có một điểm đỏ \(Y\) đã biết nào sao cho hình chữ nhật được xác định bởi \(X\) và \(Y\) chứa bất kỳ điểm xanh nào hay không. Chỉ cần kiểm tra \(Y = A, B, C\), hoặc \(D\) như trong (c) là đủ. Để kiểm tra điều này, chúng ta không cần phải duyệt qua tất cả các điểm xanh. Có các kỹ thuật tiền xử lý tiêu chuẩn có thể giảm thời gian truy vấn từ \(N\) xuống \(\log N\).

Ví dụ, đối với \(A\), chúng ta có thể định nghĩa hai tập hợp dựa trên các điểm xanh: những điểm cao hơn (dọc theo trục \(W\)) so với \(A\) (gọi chúng là \(A_1\)) và các điểm còn lại (\(A_2 = A - A_1\)). Nhiệm vụ xác định xem có điểm xanh nào giữa \(X\) và \(A\) hay không trở thành truy vấn điểm thấp nhất hoặc cao nhất trong phạm vi giữa \(H_X\) và \(H_A\).

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