Phân tích

Hai phương pháp có thể được giải độc lập vì chúng trả lời hai câu hỏi khác nhau.

Phương pháp thứ nhất

Theo phương pháp thứ nhất, Kaylin có thể ăn bất kỳ số miếng nấm nào vào bất kỳ lúc nào. Vì nấm chỉ có thể rời đĩa do Kaylin ăn, mỗi khi quan sát thấy số nấm giảm trong một khoảng thì phần giảm đó bắt buộc đã bị Kaylin ăn. Do đó, số nấm ít nhất cô có thể đã ăn là tổng các mức giảm quan sát được:

Ta chỉ quan tâm Kaylin đã ăn bao nhiêu nên không cần tính Bartholomew đã thêm bao nhiêu nấm.

Phương pháp thứ hai

Theo phương pháp thứ hai, Kaylin luôn ăn với một tốc độ không đổi khi trên đĩa còn nấm. Trong mỗi khoảng, ta có thể quan sát một cận dưới cho tốc độ ăn, tức mức giảm số nấm trong khoảng đó. Vì muốn tối thiểu hóa số nấm đã ăn, ta cần tốc độ ăn nhỏ nhất có thể. Nhưng tốc độ phải không đổi từ đầu tới cuối, nên chỉ tốc độ quan sát được lớn nhất mới thỏa mãn mọi khoảng:

Trong một số khoảng, có vẻ Kaylin ăn ít hơn lượng tương ứng với tốc độ này: hoặc đĩa đã rỗng giữa khoảng khiến cô ngừng ăn, hoặc Bartholomew đã thêm nấm trong khoảng.

Số nấm Kaylin có thể đã ăn theo phương pháp thứ hai là

Ở đầu khoảng \(i\), nếu có nhiều hơn max_rate miếng thì cô chỉ ăn max_rate miếng trong khoảng; nếu không, cô chỉ có thể ăn \(m_i\) miếng rồi đĩa rỗng cho tới cuối khoảng. Lưu ý rằng ta không cần quan tâm số nấm ở cuối khoảng khi tính lượng ăn. Để tốc độ cần thiết là nhỏ nhất và thời gian Kaylin phải ngừng ăn là lớn nhất, có thể giả sử Bartholomew đặt thêm nấm tức thời vào đúng cuối khoảng.

Cả hai phép tính đều mất \(O(N)\) thời gian và \(O(1)\) bộ nhớ phụ.

Dưới đây là cài đặt mẫu bằng Python:

def first_method(M, N):
  min_eat = 0
  for i in range(1, N):
    min_eat += max(0, M[i - 1] - M[i])
  return min_eat

def second_method(M, N):
  max_rate = 0
  for i in range(1, N):
    max_rate = max(max_rate, M[i - 1] - M[i])

  min_eat = 0
  # exclude the last mushroom
  for i in range(0, N - 1):
    min_eat += min(M[i], max_rate)
  return min_eat

for tc in range(int(input())):
  N = int(input())
  M = map(int, raw_input().split())
  print "Case #%d: %d %d" % (tc + 1,
    first_method(M, N), second_method(M, N))

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