Giải pháp cơ bản

Hầu như bất kỳ giải pháp nào cho bài toán này cuối cùng cũng sẽ dựa trên việc xây dựng một mảng đã được làm mượt bằng cách giải các bài toán con nhỏ hơn trước. Thách thức có hai phần: (1) Các bài toán con bạn muốn giải là gì? Và (2) Làm thế nào bạn có thể xử lý tất cả chúng một cách hiệu quả?

Một cách tự nhiên là bắt đầu bằng việc làm mượt \(N-1\) điểm ảnh đầu tiên, sau đó tính toán xem nên làm gì với điểm ảnh cuối cùng. Vấn đề là những gì chúng ta làm với điểm ảnh cuối cùng \(q\) phụ thuộc vào \(p\), điểm ảnh cuối cùng mà chúng ta đã thiết lập trước đó. Nếu \(p\) và \(q\) chênh lệch nhau không quá \(M\), thì chúng ta đã hoàn thành! Nếu không, chúng ta có hai lựa chọn:

• Xóa \(q\) với chi phí \(D\), giữ cho điểm ảnh cuối cùng của hình ảnh đã mượt là \(p\).
• Thay đổi \(q\) thành một giá trị \(q'\) nào đó với chi phí \(|q - q'|\). Nếu \(|q' - p| > M\), chúng ta sẽ cần thêm một số điểm ảnh vào trước đó để quá trình chuyển đổi được mượt. Thực tế, chúng ta sẽ cần thêm chính xác \((|q' - p| - 1) / M\) điểm ảnh như vậy.

May mắn thay, cả hai trường hợp này đều dễ phân tích, miễn là chúng ta sẵn sàng lặp qua mọi giá trị có thể của \(q'\).

Có lẽ phần khó léo nhất của thiết lập này là hiểu về các thao tác chèn. Sau cùng, khi quyết định các bước cần thực hiện để làm mượt quá trình chuyển đổi từ một điểm ảnh trong hình ảnh ban đầu sang điểm ảnh tiếp theo, có rất nhiều lựa chọn: chúng ta có thể thay đổi một trong hai điểm ảnh và có thể chèn bất kỳ số lượng điểm ảnh nào giữa chúng. Điểm mấu chốt là một khi chúng ta đã quyết định di chuyển cả hai điểm ảnh đến đâu, số lượng điểm ảnh cần chèn sẽ trở nên rõ ràng.

Mã giả dưới đây tìm kiếm đệ quy chi phí tối thiểu để làm mượt mảng pixels[], với điều kiện điểm ảnh cuối cùng trong phiên bản đã mượt phải bằng final_value:

  int Solve(pixels[], final_value) {
    if (pixels is empty) return 0

    // Try deleting
    best = Solve(pixels[1 to N-1], final_value) + D

    // Try all values for the previous pixel value
    for (all prev_value) {
      prev_cost = Solve(pixels[1 to N-1], prev_value)
      move_cost = |final_value - pixels[N]|
      num_inserts = (|final_value - prev_value| - 1) / M
      insert_cost = num_inserts * I
      best = min(best, prev_cost + move_cost + insert_cost)
    }
    return best
  }

Để trả lời bài toán ban đầu, chúng ta chỉ cần lấy giá trị nhỏ nhất từ hàm Solve trên tất cả các lựa chọn có thể của final_value.

Rất tiếc, thuật toán này sẽ quá chậm nếu được triển khai chính xác như thế này. Trong mỗi lần gọi Solve, chúng ta thực hiện 257 lần gọi đệ quy và có thể đi sâu tới 100 cấp. Nó sẽ không thể kết thúc trong thời gian giới hạn! May mắn thay, lý do duy nhất khiến nó chậm là vì chúng ta đang lặp lại công việc. Chỉ có \(256 \times N\) bộ tham số khác nhau mà chúng ta từng thấy cho hàm Solve, vì vậy miễn là chúng ta lưu trữ kết quả trong bộ nhớ đệm (cache) và sử dụng lại khi gặp cùng một bộ tham số, mọi thứ sẽ nhanh hơn nhiều. Kỹ thuật này được gọi là Quy hoạch động hoặc cụ thể hơn là Ghi nhớ (Memoization).

Giải pháp nâng cao

Thời gian chạy của giải pháp trước đó là \(O(256 \times 256 \times N)\), tốc độ này là đủ nhanh trong một ngôn ngữ biên dịch. Hệ số 256 bổ sung đến từ việc chúng ta cần thử 256 khả năng trong mỗi lần gọi hàm. Thực tế có thể giải bài toán này chỉ trong thời gian \(O(256 \times N)\). Dưới đây là một số gợi ý nếu bạn quan tâm:

• Như trước, bạn muốn tính Cost[n][p], chi phí để làm mượt \(n\) điểm ảnh đầu tiên trong khi đặt điểm ảnh cuối cùng thành giá trị \(p\). Khác với trước, bạn muốn thực hiện cập nhật hàng loạt. Cụ thể, bạn muốn tính toán đồng thời tất cả các giá trị cho \(n+1\) dựa trên các giá trị của \(n\).
• Vậy làm thế nào để thực hiện cập nhật hàng loạt này? Đầu tiên, hãy thực hiện một bước trung gian để tính Cost'[n][p], chi phí tối thiểu cho mỗi giá trị sau khi thực hiện tất cả các lần chèn giữa điểm ảnh \(n\) và điểm ảnh \(n+1\). Để việc này dễ dàng hơn, hãy lưu ý rằng không bao giờ cần chèn một điểm ảnh có khoảng cách nhỏ hơn \(M\) so với điểm ảnh trước đó. (Bạn có thấy tại sao không?)
• Thách thức thực sự là khi tính Cost[n][] từ Cost'[n][], bạn sẽ muốn lấy giá trị nhỏ nhất trên nhiều phần tử. Ví dụ, Cost[n][q] = min(Cost[n-1][q], {Cost'[n][q-M], Cost'[n][q-M+1], Cost'[n][q-M+2], ..., Cost'[n][q+M]}). Nói cách khác, cho mảng Cost'[n][], bạn sẽ cần tính toán trong thời gian tuyến tính phần tử nhỏ nhất trong mỗi cửa sổ trượt có độ dài \(2M+1\). Đây là một bài toán thú vị và đầy thử thách, và chúng tôi khuyến khích bạn suy nghĩ kỹ về nó! Để thảo luận kỹ hơn về bài toán con này, hãy xem tại đây.

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