Phân tích: Zombie Smash

Đầu tiên, đáng chú ý là tập dữ liệu nhỏ chỉ với 8 zombie có thể được giải quyết đơn giản bằng cách đánh giá mọi hoán vị có thể có của thứ tự đập zombie và giữ lại kết quả tốt nhất. Với mỗi hoán vị, chỉ cần cố gắng đập các zombie theo thứ tự đã cho, bỏ qua bất kỳ zombie nào không thể đến kịp lúc. Cách tiếp cận đơn giản này có độ phức tạp thời gian theo hàm mũ và rõ ràng sẽ không thể mở rộng cho tập dữ liệu lớn.

Để có cách tiếp cận hiệu quả hơn, hãy bắt đầu bằng việc xem xét trạng thái trò chơi được biểu diễn theo cách chưa tối ưu và xem làm thế nào để nó hiệu quả hơn. Chúng ta có thể biểu diễn trạng thái trò chơi tại bất kỳ thời điểm nào bằng bộ giá trị sau:

• (Thời gian, Vị trí, Tập hợp các zombie đã đập)

Cách này chắc chắn hoạt động - với trạng thái này, về cơ bản chúng ta có ảnh chụp nhanh của trò chơi tại bất kỳ thời điểm nào, nhưng nó rất rườm rà. Vì chúng ta muốn đập càng nhiều zombie càng tốt, chúng ta muốn đập zombie càng sớm càng tốt, tức là chúng ta muốn đến mộ nơi chúng hiện ra càng sớm càng tốt. Với ý nghĩ đó, chúng ta có thể đưa ra giả định sau: chúng ta sẽ đến mộ của con zombie tiếp theo càng sớm càng tốt, và có khả năng đứng chờ cho đến khi con zombie đó có thể bị đập. Sau khi đập xong, chúng ta sẽ di chuyển đến ngôi mộ tiếp theo nhanh nhất có thể và lặp lại quá trình. Bằng cách đó, việc theo dõi bất kỳ trạng thái nào khi chúng ta đang di chuyển giữa hai ngôi mộ là không cần thiết vì những trạng thái đó có thể được suy ra từ các trạng thái tại mộ nguồn và mộ đích. Chúng ta có thể thay đổi trạng thái thành:

• (Thời điểm con zombie cuối cùng bị đập, Con zombie cuối cùng bị đập, Tập hợp các zombie đã đập)

Đây là một sự cải tiến, nhưng bây giờ vấn đề là chúng ta phải theo dõi tất cả các tập hợp zombie đã đập có thể có. Hãy xem chúng ta có thể làm gì với điều đó.

Xét trạng thái (\(T_1\), \(Z_1\), {\(Z_1\) …}) nơi chúng ta vừa đập zombie \(Z_1\) tại thời điểm \(T_1\). Tập hợp các zombie đã đập chứa \(Z_1\), và có thể là một loạt các zombie khác. Giả sử \(Z_0\) là một zombie mà chúng ta đã đập trước đó. Có hai trường hợp: hoặc \(Z_0\) xuất hiện trong một khoảng thời gian chồng lấp với \(Z_1\), hoặc nó đã xuất hiện trước \(Z_1\).

1. Nếu \(Z_0\) đã xuất hiện trước \(Z_1\) thì đến \(T_1\) nó không còn ở mộ của nó nữa (ngay cả khi chúng ta chưa đập nó) và việc theo dõi rõ ràng rằng nó đã bị đập là không cần thiết.
2. Ngược lại, nếu \(Z_0\) xuất hiện trong một khoảng thời gian chồng lấp với \(Z_1\), liệu có khả năng chúng ta sẽ cố gắng đập lại \(Z_0\) nếu chúng ta không theo dõi nó không? Giả sử \(Z_0\) đã bị đập tại \(T_0\), vì Búa Đập Zombie cần sạc lại hai lần, \(Z_0\) sẽ biến mất vì nó chỉ đứng yên trong \(1000\) ms và phải mất \(1500\) ms để búa sạc lại hai lần. Một lần nữa, không cần thiết phải theo dõi rõ ràng tập hợp các zombie đã đập để tránh đập cùng một con zombie hai lần.

Dựa trên những quan sát trên, chúng ta có thể đơn giản hóa trạng thái thành:

• (Thời điểm con zombie cuối cùng bị đập, Con zombie cuối cùng bị đập, Số lượng zombie đã đập)

Dễ dàng thấy rằng chúng ta ưu tiên thời điểm sớm hơn để đập một con zombie - đập zombie càng sớm, chúng ta càng sớm có thể chuyển sang con tiếp theo, vì vậy chúng ta chỉ quan tâm đến các trạng thái có thời gian tối thiểu có thể. Hãy mô hình hóa các chuyển trạng thái dưới dạng một đồ thị và tối thiểu hóa thời gian.

Trò chơi bắt đầu tại thời điểm 0 và vị trí \((0, 0)\). Dựa trên thông tin này, chúng ta có thể tạo ra biên (frontier) ban đầu gồm các zombie có thể đến và đập kịp lúc. Với biên này, thời gian và vị trí mà các zombie sẽ xuất hiện, chúng ta có thể áp dụng thuật toán Dijkstra sửa đổi để tìm tập hợp các trạng thái trò chơi có thể đạt được. Khi đã biết những trạng thái đó, chúng ta chỉ cần trả về số lượng zombie tối đa bị đập trong một trạng thái có thể đạt được. Đây là mã giả:

solve():
  all_states = Q = generateStates()
  while Q is not empty:
    s = Q.popMin()
    if s.time = infinity:
      break;

    for each zombie z such that z ≠ s.zombie:
      earliest_arrival_time = s.time + max(750,
                                           dist(s.zombie, z))
      if earliest_arrival_time ≤ z.appearance + 1000:
        earliest_smash_time = max(z.appearance,
                                  earliest_arrival_time)
        Q.update(earliest_smash_time, z, s.smashed + 1)

  // Scan for states with time < infinity, keeping the maximum
  // number of zombies smashed to get the final answer.
  return best_reachable_state(all_states)


generateStates():
  states = {}
  states.Add(0, nil, 0) // Include the initial state.
  for each zombie z:
    for zombies_killed from 1 to Z:
      // For other reachable states this will be revised later.
      earliest_smash_time = infinity
      if zombiles_killed = 1:
        earliest_arrival_time = dist((0, 0), z)
        if earliest_arrival_time ≤ z.appearance + 1000:
          earliest_smash_time = max(z.appearance,
                                    earliest_arrival_time)
      states.Add(earliest_smash_time, z, zombies_killed)
  return states

Phân tích độ phức tạp trường hợp xấu nhất sơ bộ của thuật toán trên: generateStates() sẽ tạo ra \(O(Z^2)\) trạng thái vì mỗi phần tử của cặp (Con zombie cuối cùng bị đập, Số lượng zombie đã đập) có thể thay đổi độc lập từ \(0\) đến \(Z\). Mỗi trạng thái sẽ được lặp qua tối đa một lần bởi vòng lặp while bên ngoài của solve(), và vòng lặp for bên trong của solve() sẽ chạy qua tất cả các zombie, tốn thêm \(O(Z)\), giả sử sử dụng một heap hiệu quả, cho kết quả \(O(Z^3)\), tốc độ này đủ nhanh cho tập dữ liệu lớn với \(Z = 100\). Cuối cùng, một vài thí sinh đã giải bài này bằng quy hoạch động, giữ một bảng 2D với chỉ số zombie ở một chiều và thời gian kể từ khi zombie đó hiện ra ở chiều kia, tối đa hóa tổng số zombie bị đập.

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