Phân tích: Revenge of the Hot Dogs

Bài toán này thoạt nhìn có vẻ khá khó khăn. Có rất nhiều người bán xúc xích, và mỗi người đều có một lựa chọn quan trọng phải đưa ra. Làm thế nào bạn có thể tính đến tất cả các khả năng cùng một lúc?

Hóa ra có ít nhất hai giải pháp hoàn toàn khác nhau, một trong số đó sử dụng kỹ thuật thuật toán cổ điển, và một giải pháp thuần túy toán học. Chúng tôi sẽ trình bày cả hai cách tiếp cận ở đây.

Giải pháp Thuật toán

Có hai ý tưởng chính thúc đẩy giải pháp thuật toán.

• Không có lý do gì để một người bán xúc xích đi ngang qua một người khác. Thay vì làm điều đó, họ có thể đi bộ đến gặp nhau và sau đó quay lại con đường họ đã đi. Vì mọi người đều di chuyển với cùng một tốc độ, điều này hoàn toàn tương đương với việc hai người đi ngang qua nhau.
• Thay vì cố gắng tính trực tiếp thời gian tối thiểu cần thiết, chỉ cần trả lời câu hỏi dễ hơn một chút sau đây: Với một thời gian \(t\) và khoảng cách \(D\), liệu có thể di chuyển tất cả các người bán xúc xích cách nhau một khoảng \(D\) trong một thời gian cố định \(t\) không? Nếu chúng ta có thể trả lời câu hỏi đó một cách hiệu quả, chúng ta có thể sử dụng tìm kiếm nhị phân để tìm \(t\) tối thiểu:

lower_bound = 0
upper_bound = 1012
while upper_bound - lower_bound > 10-8 * upper_bound:
  t = (lower_bound + upper_bound) / 2
  if t is high_enough:
    upper_bound = t
  else:
    lower_bound = t
return lower_bound

Vì vậy, chúng ta cần quyết định xem \(t\) giây có đủ để di chuyển tất cả các người bán xúc xích ra xa nhau hay không. Hãy coi con đường đi từ trái (giá trị âm) sang phải (giá trị dương) và tập trung vào người ngoài cùng bên trái \(A\). Theo quan sát đầu tiên của chúng ta, anh ta vẫn sẽ là người ngoài cùng bên trái khi mọi người di chuyển xong. Vì vậy, chúng ta cũng có thể di chuyển anh ta sang trái xa nhất có thể. Bằng cách đó, anh ta sẽ ít gây cản trở nhất cho những người còn lại. Vì chúng ta đã cố định \(t\), điều này cho chúng ta biết chính xác vị trí \(A\) sẽ kết thúc.

Bây giờ hãy xem xét người thứ hai từ bên trái \(B\). Anh ta phải đứng bên phải \(A\) ít nhất một khoảng cách \(D\). Tuân theo giới hạn đó, anh ta một lần nữa nên đi sang trái xa nhất có thể. (Tất nhiên một khi bạn đã tính đến người đầu tiên, "sang trái xa nhất có thể" thực tế có thể là sang bên phải!) Lý do để làm điều này cũng giống như trước: người này càng đi xa về phía trái, thì việc sắp xếp tất cả những người còn lại sẽ càng dễ dàng hơn. Trên thực tế, chiến lược tham lam này hiệu quả với tất cả mọi người. Một khi thời gian được cố định, mỗi người nên luôn luôn đi sang trái xa nhất có thể mà không đứng cách người trước đó ít hơn khoảng cách \(D\).

Sử dụng chiến lược tham lam này, chúng ta có thể định vị từng người một. Nếu chúng ta đưa ra được một tập hợp các vị trí hợp lệ theo cách này, thì chúng ta biết \(t\) là đủ thời gian. Nếu không, thì không có gì tốt hơn mà chúng ta có thể đã làm.

Bây giờ chúng ta chỉ cần đưa điều này vào tìm kiếm nhị phân, và bài toán đã được giải quyết!

Giải pháp Toán học

Tại Google Code Jam, chúng tôi mong đợi các thí sinh thử các phương pháp tiếp cận thuật toán trước. Suy cho cùng, các bạn là những chuyên gia về thuật toán! Tuy nhiên, chúng tôi cũng muốn trình bày một giải pháp toán học cho bài toán này. Nó tránh được việc tìm kiếm nhị phân, và do đó nó hiệu quả hơn giải pháp trước đó nếu bạn triển khai đúng cách.

Như trên, hãy sắp xếp mọi người từ trái sang phải. Gọi \(P_i\) là vị trí của người thứ \(i\), và đặt \(x_{i,j} = D \times (j - i) - (P_j - P_i)\). Cuối cùng, định nghĩa \(X = \max_{i < j} x_{i,j}\). Chúng tôi khẳng định \(\max(0, X) / 2\) chính xác là lượng thời gian cần thiết.

Đầu tiên, hãy chứng minh rằng bạn cần ít nhất lượng thời gian này. Tập trung vào hai người bất kỳ: \(i\) và \(j\). Vì không ai được đi ngang qua nhau (như đã lập luận ở trên), vẫn phải có \(j - i - 1\) người ở giữa hai người này khi mọi thứ hoàn tất. Do đó, họ phải kết thúc với khoảng cách ít nhất là \(D \times (j - i)\). Ban đầu họ chỉ cách nhau \(P_j - P_i\), và khoảng cách này có thể tăng thêm tối đa \(2\) mỗi giây, vì vậy chúng ta thực sự cần ít nhất \([D \times (j - i) - (P_j - P_i)] / 2\) giây tổng cộng.

Để chứng minh lượng thời gian này là đủ, chúng ta chỉ ra cách \(X\) luôn có thể giảm với tốc độ \(2\) mét mỗi giây. Hãy tập trung vào một người \(j\) duy nhất. Chúng ta sẽ nói anh ta bị "giới hạn bên trái" nếu tồn tại \(i < j\) sao cho \(x_{i,j} = X\), và anh ta bị "giới hạn bên phải" nếu tồn tại \(k > j\) sao cho \(x_{j,k} = X\). Giả sử chúng ta có thể di chuyển mọi người bị giới hạn bên trái sang trái với tốc độ tối đa, và mọi người bị giới hạn bên phải sang phải với tốc độ tối đa. Khi đó, bất kỳ số hạng \(x_{i,j}\) nào bằng \(X\) sẽ giảm đi trọn vẹn \(2\) mét mỗi giây, và do đó \(X\) cũng sẽ giảm đi \(2\) mét mỗi giây, như yêu cầu.

Vì vậy, chiến lược này hoạt động miễn là không có người nào vừa bị giới hạn bên trái vừa bị giới hạn bên phải. (Nếu điều đó xảy ra, anh ta sẽ không thể đi cả sang trái và sang phải cùng một lúc, và chiến lược này sẽ không khả thi.) Vì vậy, hãy giả sử \(x_{i,j} = X = x_{j,k}\). Nếu bạn chỉ cần viết phương trình ra, bạn sẽ thấy \(x_{i,k}\) chính xác bằng \(x_{i,j} + x_{j,k}\). Nhưng điều này có nghĩa là \(x_{i,k} = 2X > X\), và chúng ta có một mâu thuẫn. Do đó, không có người nào từng bị cả giới hạn bên trái và giới hạn bên phải cùng lúc, và chứng minh đã hoàn tất!

Nhận xét bổ sung

• Hóa ra câu trả lời cho bài toán này luôn là một số nguyên hoặc một số nguyên cộng thêm \(0.5\). Bạn có thấy tại sao không? Cụ thể, nếu bạn nhân tất cả các vị trí với \(2\) ngay từ đầu, bạn chỉ có thể làm việc với các số nguyên. Điều này cho phép bạn tránh lo lắng về các vấn đề làm tròn số dấu phẩy động, điều này luôn tốt!
• Lúc đầu, giải pháp toán học trông giống như \(O(n^2)\), vì bạn đang tính giá trị lớn nhất của \(O(n^2)\) số khác nhau. Bạn có thấy cách để thực hiện nó trong thời gian tuyến tính không?

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