Phân tích: Enclosure

Mục tiêu là đặt ít đá nhất có thể để bao quanh ít nhất \(K\) điểm giao cắt trong lưới \(N \times M\). Theo cảm tính, việc tạo ra nhiều hơn một vùng bao quanh là lãng phí vì chúng ta luôn có thể kết hợp các viên đá thành một vùng bao quanh lớn hơn bao phủ cùng số lượng hoặc nhiều điểm giao cắt hơn. Do đó, chúng ta có thể giới hạn tìm kiếm ở các giải pháp chỉ có một vùng bao quanh.

Hình dưới đây cho thấy một vùng bao quanh cho lưới \(N = 5\) và \(M = 5\) bao phủ \(K = 19\) điểm giao cắt với số lượng tối thiểu là 11 viên đá.

-***-   # the first row
*XXX*   # intermediate row
*XXX*   # intermediate row
*XX*-   # intermediate row
-**--   # the last row

Chúng ta sử dụng '-' để biểu thị điểm giao cắt trống, 'X' để biểu thị điểm giao cắt bị bao quanh, và '*' để biểu thị một viên đá được đặt tại điểm giao cắt (điểm này cũng được coi là bị bao quanh). Quan sát thấy rằng:

• Các viên đá ở hàng đầu tiên và hàng cuối cùng được điền vào các vị trí liên tiếp trong hàng.
• Mỗi hàng trung gian (tức là các hàng ngoại trừ hàng đầu và hàng cuối) có chính xác hai viên đá (viên đá bên trái và viên đá bên phải).

Mỗi hàng trung gian luôn chứa hai viên đá. Nếu tồn tại một hàng trung gian chỉ chứa một viên đá, thì nó có thể tạo thành hai vùng bao quanh chạm biên nhau tại hàng đó. Vì chúng ta không quan tâm đến việc tìm kiếm các giải pháp có nhiều hơn một vùng bao quanh, chúng ta có thể giới hạn mỗi hàng trung gian luôn chứa đúng hai viên đá.

Còn việc có nhiều hơn hai viên đá trong một hàng trung gian thì sao? Điều này là lãng phí và chúng ta cũng có thể tránh nó. Để thấy điều này, hãy liệt kê tất cả các cách có thể để di chuyển biên đá bên trái cho hàng tiếp theo, đồng thời giải thích tại sao mỗi hàng trung gian luôn chứa hai viên đá trong cấu hình cuối cùng. Hình dưới đây cho thấy ba cách có thể để di chuyển viên đá biên bên trái:

previous row:  --*XXX     --*XXX      --*XXX
    next row:  -*XXXX     --*XXX      ---*XX
              (expand)  (unchanged)  (shrink)

Lưu ý rằng chúng ta chỉ có thể mở rộng biên thêm một vị trí, nếu không nó sẽ tạo ra một khoảng trống và không còn tạo thành một vùng bao quanh kín. Chúng ta có thể đặt đá ở giữa để lấp đầy khoảng trống không? Ví dụ như (được in đậm):

previous row:  --*XXX      -**XXX
    next row:  **XXXX      *XXXXX
                          (push up)

Có, chúng ta có thể, nhưng nó lãng phí vì chúng ta luôn có thể "đẩy lên" viên đá đã đặt để có thêm một điểm giao cắt bị bao quanh như được hiển thị trong hình bên phải. Hơn nữa, chúng ta có thể thực hiện một lần đẩy lên khác ở hàng trước đó lên hàng trước-trước đó và cứ thế cho đến khi nó được đẩy lên hàng trên cùng (mỗi lần đẩy lên sẽ có thêm một điểm giao cắt bị bao quanh). Vì vậy, cuối cùng, sau tất cả các lần đẩy lên, mỗi hàng trung gian sẽ chứa đúng hai viên đá.

Để việc tìm kiếm đơn giản, chúng ta không muốn bất kỳ lần đẩy lên nào xảy ra. Trong quá trình tìm kiếm, chúng ta cố định số lượng đá ở hàng trên cùng, tạo hàng tiếp theo và không muốn hàng tiếp theo làm thay đổi hàng trước đó ("đẩy lên" làm thay đổi hàng trước đó). Điều này giải thích tại sao chúng ta không muốn mở rộng biên trái quá một vị trí (đơn giản hơn là chỉ cần thay đổi số lượng đá ở hàng trên cùng và thực hiện một tìm kiếm riêng biệt).

Đối với trường hợp thu hẹp, quan sát thấy rằng chúng ta chỉ cần thu hẹp tối đa một vị trí vì thu hẹp nhiều hơn một là lãng phí do chúng ta sẽ cần nhiều đá hơn để lấp đầy các khoảng trống (để duy trì vùng bao quanh). Xem các ví dụ sau:

previous row:   --*XXX     --**XX
    next row:   ---**X     ----*X
               (case 1)   (case 2)

Trong trường hợp thu hẹp 1, viên đá in đậm '*' (viên đá ngoài cùng bên phải) là không cần thiết vì nó đã bị bao quanh. Trường hợp thu hẹp 2 là lãng phí vì viên đá in đậm '*' (viên đá ở giữa) có thể được đẩy xuống để bao quanh thêm một điểm giao cắt (điều này vẫn sẽ lãng phí vì sau đó nó sẽ trở thành trường hợp 1).

Nhìn vào tất cả các cách có thể để di chuyển biên trái, chúng ta có thể kết luận rằng chỉ cần đặt đúng hai viên đá trong mỗi hàng trung gian là đủ.

Đối với hàng cuối cùng, chúng ta đóng vùng bao quanh bằng cách kết nối biên đá trái và phải của hàng trước đó bằng cách đặt các viên đá liên tiếp. Ví dụ:

previous row:  --*XXXXX*--
    last row:  ---*****---

Lưu ý rằng chúng ta chỉ đóng vùng bao quanh nếu chắc chắn rằng các điểm giao cắt bị bao quanh bởi tất cả các hàng trước đó và hàng cuối cùng ít nhất là \(K\).

Tóm lại, thuật toán tìm kiếm của chúng ta như sau:

• Đầu tiên đặt một số lượng đá liên tiếp từ trái sang phải trên hàng trên cùng.
• Đặt hai viên đá cho các hàng (trung gian) tiếp theo bằng cách mở rộng / thu hẹp / không đổi biên trái và phải so với hàng trước đó.
• Cuối cùng, nếu chúng ta đã bao quanh đủ số điểm giao cắt, hãy đóng vùng bao quanh bằng cách đặt các viên đá liên tiếp ở hàng cuối cùng.

Chúng ta sẽ thảo luận về hai cách phổ biến để giải quyết bài toán này. Đầu tiên là giải pháp quy hoạch động (DP) và thứ hai là giải pháp tham lam.

Quy hoạch động (DP)

Vì chúng ta duyệt vét cạn hàng đầu tiên, chúng ta chỉ cần thực hiện DP cho các hàng trung gian và hàng cuối cùng. Đối với mỗi hàng, chúng ta cần biết:

• Số hàng còn lại.
• Vị trí biên đá bên trái.
• Vị trí biên đá bên phải.
• Số điểm giao cắt còn lại cần bao quanh.

Để giảm thiểu vị trí biên đá trái / phải, chúng ta chuyển vị lưới (nếu cần thiết) sao cho lưới có số cột nhỏ hơn số hàng mà không ảnh hưởng đến tính tối ưu. Với phép biến đổi này, giờ đây vị trí biên trái / phải tối đa là \(\sqrt{N \times M}\). Điều này dẫn đến giải pháp \(O(N \times \sqrt{N \times M} \times \sqrt{N \times M} \times N \times M)\). Mặc dù chi phí khấu hao có thể ít hơn, nhưng nó vẫn có vẻ lớn và có khả năng chạy quá giới hạn thời gian. Chúng ta có thể làm tốt hơn không?

Hóa ra vị trí chính xác của biên đá trái và phải không thực sự quan trọng miễn là khoảng cách giữa chúng không lớn hơn kích thước cột. Điều này cũng áp dụng cho các viên đá ở hàng trên cùng. Điều quan trọng là số lượng đá được đặt liên tiếp ở hàng trên cùng. Các viên đá được đặt chính xác ở đâu không quan trọng miễn là số lượng đá tối đa bằng kích thước cột.

Với trực giác này, chúng ta có thể làm cho trạng thái DP nhỏ hơn. Thay vì duy trì vị trí biên đá trái và phải, chúng ta chỉ cần duy trì khoảng cách giữa hai viên đá. Ba khả năng di chuyển các biên đá ở hàng tiếp theo (mở rộng, thu hẹp, không đổi) giờ đây chuyển thành năm khả năng thêm vào khoảng cách đá: -2, -1, 0, 1, hoặc 2 như trong các ví dụ sau.

prev row:  -*XXX*-  -*XXX*-  -*XXX*-  -*XXX*-  -*XXX*-
next row:  --*X*--  --*XX*-  -*XXX*-  -*XXXX*  *XXXXX*
            (-2)     (-1)      (0)      (1)      (2)

Lưu ý rằng đối với (-1) và (1) có một khả năng khác cho hàng tiếp theo, nhưng cả hai đều có cùng khoảng cách giữa biên đá trái và phải.

Bằng cách chuyển vị trí biên trái và phải sang khoảng cách giữa viên đá trái và phải, chúng ta có thể giảm các trạng thái DP xuống còn ba trạng thái (số hàng còn lại, khoảng cách đá của hàng trước, số điểm giao cắt còn lại cần bao quanh). Điều này làm giảm độ phức tạp xuống \(O(N \times \sqrt{N \times M} \times N \times M)\). Chi phí khấu hao ít hơn 32 triệu thao tác cho mỗi bộ thử nghiệm, đủ nhanh để trả lời 100 bộ thử nghiệm. Dưới đây là một ví dụ cài đặt bằng Python 3:

from functools import lru_cache
import sys

@lru_cache(maxsize = None)  # Memoization.
def rec(rem_rows, prev_dist, rem_points, M):
  if rem_points <= 0:  # If the remaining area is non positive,
    return 0  # then no stone is needed.

  ret = 1000000  # Infinity.
  if rem_rows <= 0:  # No more row but rem_points is still > 0.
    return ret  # Return infinity.

  if M == 1:  # Special case where each row only has one stone.
    return rem_points  #  rem_rows >= rem_points is guaranteed.

  min_dist = max(prev_dist - 2, 1)
  max_dist = min(prev_dist + 2, M)
  for next_dist in range(min_dist, max_dist + 1):
    if next_dist >= rem_points:
      # Close the enclosure for the last row.
      ret = min(ret, next_dist)
    elif next_dist > 1:
      # Cover this row using 2 stones.
      next_rem_points = rem_points - next_dist
      ret = min(ret, \
        2 + rec(rem_rows - 1, next_dist, next_rem_points, M))

  return ret


def min_stones(N, M, K):
  if N < M:  # If the row size is smaller than the column size
    (N, M) = (M, N)  # Transpose the grid

  res = 1000000
  # Try all possible number of stones for the top row.
  for stones in range(1, min(K, M) + 1):
    # The stones needed to cover the top row + the next rows.
    stones = stones + rec(N - 1, stones, K - stones, M)
    res = min(res, stones)

  return res

sys.setrecursionlimit(5000)
for tc in range(int(input())):
  print("Case #%d: %d" % (tc+1, \
    min_stones(*map(int, input().split()))))

Tham lam

Theo cảm tính, hai viên đá trong mỗi hàng trung gian có thể được đặt tham lam càng xa nhau càng tốt để tối đa hóa diện tích được bao quanh mà không cần thêm bất kỳ viên đá nào. Hãy xem xét ví dụ sau:

---------      ---------      ----*----
---------      ---------      ---*X*---
--*****--      --*****--      --*XXX*--
--*XXX*--      -*XXXXX*-      -*XXXXX*-
--*XXX*--  ->  *XXXXXXX*  ->  *XXXXXXX*
--*XXX*--      -*XXXXX*-      -*XXXXX*-
--*****--      --*****--      --*XXX*--
---------      ---------      ---*X*---
---------      ---------      ----*----
   (a)            (b)            (c)

Vùng bao quanh trong Hình (a) có thể được cải thiện bằng cách di chuyển hai viên đá (trong mỗi hàng trong số ba hàng trung gian) càng xa nhau càng tốt như trong Hình (b). Lập luận tương tự có thể được đưa ra cho mỗi cột chỉ chứa hai viên đá: di chuyển các viên đá trên và dưới càng xa nhau càng tốt trong cột đó. Vùng bao quanh trong Hình (b) có thể được cải thiện theo cách tương tự, dẫn đến vùng bao quanh như trong Hình (c).

Biết rằng hình dạng tối ưu giống như một hình kim cương, cách tiếp cận tham lam là cố gắng xây dựng một vùng bao quanh hình kim cương với diện tích ít nhất là \(K\). Tuy nhiên, điều này không phải lúc nào cũng khả thi nếu lưới không đủ lớn. Trong trường hợp đó, hình kim cương có thể bị "cắt cụt" ở các cạnh trên / trái / phải / dưới như được hiển thị bên dưới cho vùng bao quanh tốt nhất cho \(N = 6, M = 7, K = 27\)

--***--
-*XXX*-
*XXXXX*
-*XXXX*
--*XX*-
---**--

Một quan sát hữu ích khác là các điểm giao cắt trống ở các góc luôn tạo thành một tam giác vuông. Điều này cho phép chúng ta tạo ra tất cả các hình kim cương bị cắt cụt (và hoàn hảo) có thể bằng cách đặt các tam giác trống ở các góc. Lưu ý rằng kích thước (độ dài cạnh) của các tam giác trống ở các góc có thể khác nhau tối đa một đơn vị.

May mắn thay, dữ liệu lớn đủ nhỏ để chúng ta có thể duyệt vét cạn tất cả các hình dạng kim cương bị cắt cụt (và hoàn hảo) có thể. Đầu tiên chúng ta thử tất cả các kích thước lưới có thể, và đối với mỗi kích thước lưới có thể, chúng ta thử đặt các tam giác trống ở các góc và tính toán kích thước vùng bao quanh cùng số lượng đá cần thiết. Chúng ta ghi lại và trả về số lượng đá tối thiểu cần thiết để xây dựng hình dạng có diện tích ít nhất là \(K\). Dưới đây là một ví dụ cài đặt bằng Python 3:

def empty_triangle(size):
  return size * (size + 1) / 2

def min_stones(N, M, K):
  if N > M:
    (N, M) = (M, N)

  best = K
  for R in range(2, N + 1):
    for C in range(R, M + 1):
      if R * C >= K:
        for i in range(2 * R):
          cover = R * C
          cover -= empty_triangle(i // 4)
          cover -= empty_triangle((i + 1) // 4)
          cover -= empty_triangle((i + 2) // 4)
          cover -= empty_triangle((i + 3) // 4)
          if cover < K:
            break
          stones = 2 * (R + C) - 4 - i
          best = min(best, stones)

  return best

Độ phức tạp của giải pháp trên là \(O(N^2 \times M)\). Tuy nhiên, nếu bạn giỏi Toán, bạn có thể cải thiện thêm việc tìm kiếm lên \(O(\log(K))\) bằng cách thực hiện tìm kiếm nhị phân trên số lượng đá cần thiết để tạo thành hình kim cương bị cắt cụt và tính toán số lượng điểm giao cắt bị bao quanh trong \(O(1)\) để đưa ra quyết định tìm kiếm nhị phân.

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