Test Set 1 (Visible)

Vì số học sinh và kích thước lưới trong Test Set 1 đều nhỏ, ta chỉ cần xây dựng một chiến lược tham lam đúng để quyết định giáo viên nên di chuyển tới đâu, rồi mô phỏng cho đến khi mọi người tập trung xong.

Nhận xét đầu tiên là có thể giải bài toán độc lập trên từng chiều (\(x\) và \(y\)). Ở mỗi thời điểm, học sinh \(i\) luôn tiến đúng \(1\) bước lại gần người \(i-1\) trên cả hai chiều cho tới khi hai người có cùng tọa độ trên chiều đang xét. Chuyển động là đường chéo khi hai người khác tọa độ trên cả hai chiều; là ngang hoặc dọc khi họ cùng tọa độ trên một chiều nhưng khác nhau trên chiều kia; và không có chuyển động khi họ cùng tọa độ trên cả hai chiều.

Nhận xét thứ hai là khi nhìn bài toán theo một chiều, thời gian chỉ bị chi phối bởi những học sinh xa giáo viên nhất trên từng chiều và từng hướng. Gọi \(K\) là số thứ tự của học sinh xa nhất theo một chiều và một hướng nào đó; nếu nhiều học sinh cùng ở vị trí xa nhất ấy, chọn người có số thứ tự nhỏ nhất. Theo cách chọn, mọi học sinh có số thứ tự nhỏ hơn \(K\) — trong đó có học sinh \(K-1\) — hoặc gần giáo viên hơn học sinh \(K\), hoặc nằm về phía đối diện so với giáo viên. Vì thế học sinh \(K\) sẽ đi một bước về phía giáo viên. Hiệu ứng này tiếp tục quy nạp tới những học sinh có số thứ tự lớn hơn \(K\): sau khi học sinh \(K\) tiến gần giáo viên hơn, học sinh đầu tiên có số thứ tự lớn hơn \(K\) và có khoảng cách tới giáo viên bằng khoảng cách ban đầu của học sinh \(K\) sẽ trở thành học sinh xa nhất và chắc chắn cũng tiến về phía giáo viên.

Do đó, chiến lược đúng là làm nhỏ nhất khoảng cách giữa giáo viên và học sinh xa nhất, xét độc lập trên từng chiều. Ta tìm học sinh xa nhất trên mỗi chiều rồi cho giáo viên đi về phía những học sinh đó trên chiều tương ứng. Nếu có hai học sinh xa bằng nhau nhưng ở hai hướng đối diện, giáo viên không di chuyển trên chiều ấy.

Một cách phát biểu tương đương là giáo viên luôn đi về phía trung điểm của tọa độ nhỏ nhất và tọa độ lớn nhất trên mỗi chiều, và không đi trên chiều đó nếu đã ở trung tâm. Nếu hiệu giữa tọa độ lớn nhất và nhỏ nhất trên một chiều là số lẻ, giáo viên có thể dao động giữa hai ô trung tâm trên chiều ấy; điều này không ảnh hưởng đến tính đúng đắn của chiến lược.

Sau đây là một số chiến lược tham lam sai:

1. Cho giáo viên đi về phía một học sinh xa nhất duy nhất. Cách này sai vì hai chiều \(x\) và \(y\) phải được xử lý độc lập.
2. Cho giáo viên đi về phía tọa độ trung bình hoặc trung vị của các học sinh. Cách này sai vì nó thiên về một cụm học sinh thay vì xử lý các điểm ngoại lai.
3. Cho giáo viên đi về phía học sinh đầu tiên không ở cùng ô với mình. Cách này sai vì giáo viên có thể lãng phí thời gian thu nhỏ một cụm trước khi bắt đầu đi về phía các điểm ngoại lai.

Test Set 2 (Hidden)

Với giới hạn lớn hơn, rõ ràng không thể chạy mô phỏng cho tới khi kết thúc.

Theo chiến lược tham lam ở trên, tại mỗi bước thời gian, học sinh xa nhất trên mỗi hướng và mỗi chiều đều tiến một bước về phía giáo viên. Vì thế trên mỗi chiều, tọa độ nhỏ nhất tăng \(1\) và tọa độ lớn nhất giảm \(1\). Bài toán trên một chiều được giải quyết khi tọa độ nhỏ nhất và lớn nhất bằng nhau. Do đó, ta tính thời gian trên mỗi chiều bằng cách lấy hiệu giữa tọa độ lớn nhất và nhỏ nhất, chia cho \(2\) và làm tròn lên; đáp án là giá trị lớn hơn giữa hai chiều \(x\) và \(y\).

Ta chỉ cần xét mỗi người một lần, nên thuật toán có độ phức tạp thời gian \(O(N)\) và dùng \(O(1)\) bộ nhớ phụ.

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