Phân tích

Bài toán này đưa ra một chuyến tham quan thú vị vào một số hình ảnh cơ bản trong đại số và hình học, và chắc chắn là cả những kiến thức lập trình cơ bản.

Bài toán yêu cầu tìm công suất nhỏ nhất \(Y_0\) sao cho tồn tại một vị trí mà tại đó công suất \(Y_0\) đủ để tiếp cận tất cả các con tàu. Rõ ràng, bất kỳ công suất nào lớn hơn \(Y_0\) cũng sẽ đủ, trong khi bất kỳ công suất nào nhỏ hơn \(Y_0\) thì không. Vì vậy, bước đầu tiên để giải quyết là sử dụng tìm kiếm nhị phân (binary search). Chuyển bài toán tìm \(Y\) nhỏ nhất thành một chuỗi các bài toán dễ hơn là quyết định xem một giá trị \(Y\) cho trước có đủ lớn hay không. Dưới đây chúng ta sẽ tập trung vào bài toán quyết định cho một giá trị \(Y\) cụ thể thay vì bài toán tối ưu hóa ban đầu.

Với một giá trị \(Y\) cho trước, chúng ta có yêu cầu là mỗi con tàu \(i\) phải thỏa mãn:

(1)     (|xi - x| + |yi - y| + |zi - z|) ≤ piY

Về mặt hình học, điều này có nghĩa là điểm \((x, y, z)\) của tàu tuần dương phải nằm trong khối bát diện (octahedron) tâm tại \((x_i, y_i, z_i)\). Mỗi con tàu trong số \(N\) con tàu tạo ra một khối bát diện, và một vị trí tốt cho tàu tuần dương tồn tại khi và chỉ khi tất cả \(N\) khối bát diện này giao nhau.

Về mặt đại số, bất đẳng thức (1) tương đương với tập hợp các bất đẳng thức sau (hãy tự chứng minh!):

   x + y + z ≤ xi + yi + zi + piY
   x + y + z ≥ xi + yi + zi - piY
   x + y - z ≤ xi + yi - zi + piY
   x + y - z ≥ xi + yi - zi - piY
   x - y + z ≤ xi - yi + zi + piY
   x - y + z ≥ xi - yi + zi - piY
   -x + y + z ≤ -xi + yi + zi + piY
   -x + y + z ≥ -xi + yi + zi - piY

Đối với những người thiên về hình học, mỗi khối bát diện được liên kết với một trong bốn hướng được đưa ra bởi các vectơ \((1, 1, 1), (1, 1, -1), (1, -1, 1)\) và \((-1, 1, 1)\). Mỗi cặp bất đẳng thức phát biểu rằng hình chiếu (tích vô hướng) của \((x, y, z)\) lên một vectơ hướng cho trước phải nằm trong một phạm vi nhất định.

Bây giờ chúng ta có bài toán giải một hệ bất đẳng thức có dạng:

   A ≤ x + y + z ≤ B
   C ≤ x + y - z ≤ D
   E ≤ x - y + z ≤ F
   G ≤ -x + y + z ≤ H

trong đó \(A, B, C, D, E, F, G\) và \(H\) đã biết. Nói chung, đây là một bài toán quy hoạch tuyến tính. Nhưng nó đơn giản đến mức chúng ta không cần sử dụng bất kỳ thuật toán quy hoạch tuyến tính nghiêm túc nào.

Chắc chắn, để nghiệm tồn tại, chúng ta phải có \(A \le B, C \le D, E \le F\), và \(G \le H\). Nhưng những điều kiện này là chưa đủ. Các bất đẳng thức có thể được viết lại thành:

   A - x ≤ y + z ≤ B - x
   G + x ≤ y + z ≤ H + x
   C - x ≤ y - z ≤ D - x
   -F + x ≤ y - z ≤ -E + x

Miễn là \(y + z\) và \(y - z\) có nghiệm, chúng ta có thể tìm được \(y\) và \(z\). Chúng ta muốn xem liệu có tồn tại \(x\) sao cho đoạn \([A - x, B - x]\) giao với \([G + x, H + x]\), và đoạn \([C - x, D - x]\) giao với \([-F + x, -E + x]\).

Dễ dàng thấy rằng để hai đoạn đầu tiên giao nhau, chúng ta phải có:

(2)     x in [(A - H) / 2, (B - G) / 2].

Và đối với hai đoạn còn lại, chúng ta phải có:

(3)     x in [(C + E) / 2, (D + F) / 2].

Bước cuối cùng của giải pháp chỉ đơn giản là quyết định xem hai khoảng trong (2) và (3) có giao điểm khác rỗng hay không.

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