Phân tích

Tập dữ liệu nhỏ (Small dataset)

Các giới hạn trong tập dữ liệu nhỏ rất thấp, cho phép sử dụng các phương pháp duyệt trâu (brute-force). Với một ngôn ngữ đủ nhanh, ngay cả một thuật toán thử mọi lượng năng lượng có thể sử dụng cho mỗi hoạt động (từ 0 đến năng lượng hiện có) cũng sẽ chạy kịp thời gian.

Tập dữ liệu lớn rõ ràng không cho phép giải pháp như vậy — cả số lượng hoạt động và số lượng mức năng lượng có thể cân nhắc đều quá lớn.

Hoạt động có giá trị cao nhất

Chúng ta bắt đầu giải quyết vấn đề này bằng cách xem xét hoạt động có giá trị cao nhất (nếu có nhiều hơn một, hãy chọn bất kỳ hoạt động nào), gọi đây là hoạt động thứ \(a\). Chúng ta sẽ chứng minh rằng tồn tại một giải pháp tối ưu sử dụng toàn bộ \(E\) joules cho hoạt động này.

Xét một giải pháp tối ưu bất kỳ. Đầu tiên giả sử chúng ta có ít hơn \(E\) joules khi bắt đầu hoạt động \(a\). Điều này có nghĩa là chúng ta đã tiêu tốn năng lượng cho một hoạt động nào đó trước đó (vì chúng ta bắt đầu ngày với \(E\) năng lượng), gọi \(b\) là hoạt động cuối cùng mà chúng ta đã tiêu tốn năng lượng khác không trước \(a\). Bây giờ hãy xem xét một giải pháp mà chúng ta tiêu tốn ít hơn một joule cho \(b\). Vì năng lượng của chúng ta không phải là \(E\) trong giải pháp ban đầu khi bắt đầu \(a\), nếu chúng ta tiêu tốn ít hơn một joule cho \(b\), chúng ta vẫn sẽ có tối đa \(E\) năng lượng khi bắt đầu \(a\), và do đó nó sẽ không bị lãng phí. Như vậy, chúng ta có thể tiêu tốn thêm một joule này vào \(a\), và sau đó tiếp tục như trong giải pháp ban đầu, vì sau \(a\) chúng ta có lượng năng lượng chính xác như trong bản gốc. Sự khác biệt về giá trị của hai giải pháp này là \(-v_b + v_a\), là một số không âm (vì \(a\) là một trong những hoạt động có giá trị cao nhất). Chúng ta có thể lặp lại quy trình này cho đến khi thu được một giải pháp không tệ hơn giải pháp ban đầu (và do đó vẫn tối ưu) và có \(E\) joules khi bắt đầu \(a\).

Bây giờ giả sử chúng ta có một giải pháp tối ưu bước vào \(a\) với \(E\) joules, nhưng không sử dụng hết chúng cho \(a\). Chúng ta có thể thay đổi nó theo cách tương tự. Tìm hoạt động đầu tiên sau \(a\) mà chúng ta tiêu tốn năng lượng khác không, gọi là \(c\). Nếu nó không tồn tại, hoặc nếu có bất kỳ năng lượng nào bị lãng phí giữa \(a\) và \(c\), chúng ta chỉ cần tiêu thêm một joule vào \(a\) và thu được một giải pháp tốt hơn hẳn. Ngược lại, chúng ta có thể tiêu ít hơn một joule cho \(c\) và thêm một joule cho \(a\), để thu được một giải pháp không tệ hơn.

Sau khi lặp lại các quy trình này, chúng ta thu được một giải pháp tối ưu mà trong đó, quả thực, chúng ta tiêu tốn trọn \(E\) joules cho \(a\).

Các hoạt động khác

Lưu ý rằng việc chúng ta tiêu tốn \(E\) năng lượng cho \(a\) có một số ảnh hưởng đến các hoạt động lân cận. Ví dụ, chúng ta sẽ có tối đa \(R\) năng lượng tại \(a+1\), tối đa \(2R\) tại \(a+2\), v.v. Đồng thời, chúng ta cần rời khỏi \(a-1\) với ít nhất \(E-R\) năng lượng, rời khỏi \(a-2\) với ít nhất \(E-2R\) năng lượng, và cứ tiếp tục như vậy.

Xét hoạt động \(d\) có giá trị cao thứ hai sau \(a\). Chúng ta có giới hạn về lượng năng lượng tối đa khi bước vào \(d\) (là giá trị nhỏ hơn giữa \(E\) và giới hạn do việc tiêu xài ở \(a\) áp đặt); và chúng ta biết mình phải để lại bao nhiêu năng lượng chưa tiêu (là giá trị lớn hơn giữa 0 và giới hạn do \(a\) áp đặt). Chúng ta sẽ tiêu bất kỳ lượng năng lượng nào nằm giữa hai giới hạn này cho hoạt động \(d\) — một lập luận tương tự như đối với \(a\) chứng minh rằng điều này không ngăn cản chúng ta đạt được giải pháp tối ưu.

Chúng ta sẽ tiếp tục theo cách này. Tại mỗi bước, đối với mỗi hoạt động, chúng ta sẽ có một lượng năng lượng phải để lại sau khi kết thúc nó cho các hoạt động đã xem xét, và lượng năng lượng tối đa có thể có khi bắt đầu hoạt động này. Tại mỗi bước, chúng ta sẽ lấy hoạt động có giá trị cao nhất chưa được xem xét, và gán cho nó tất cả năng lượng có thể, sau đó cập nhật các giới hạn.

Độ phức tạp thời gian của giải pháp này là \(O(N^2)\) — trong mỗi bước trong số \(N\) bước, chúng ta tìm hoạt động có giá trị cao nhất chưa được xem xét, gán năng lượng cho nó và cập nhật giới hạn cho tất cả các hoạt động khác. Với các ràng buộc về kích thước đầu vào, cách này sẽ đủ nhanh (nếu được cài đặt hiệu quả). Tuy nhiên, có thể làm tốt hơn.

Giải pháp \(O(N \log N)\)

Đầu tiên, lưu ý rằng việc tìm hoạt động có giá trị cao nhất chưa được xem xét có thể được thực hiện nhanh hơn — chỉ cần sắp xếp các hoạt động theo giá trị ngay từ đầu, sau đó xem xét chúng theo thứ tự giảm dần.

Phần khó hơn là cập nhật các giới hạn. Để làm điều này, chúng ta xem xét lại cách các giới hạn được thiết lập. Mỗi hoạt động chúng ta gán năng lượng sẽ áp đặt một giới hạn về lượng năng lượng chúng ta có ở các hoạt động sau đó, và lượng năng lượng chúng ta phải để lại ở các hoạt động trước đó. Có thể chứng minh rằng đối với mỗi hoạt động \(a\), giới hạn năng lượng hiện có đến từ hoạt động gần nhất trước đó đã được xem xét, và giới hạn năng lượng phải để lại đến từ hoạt động gần nhất sau đó đã được xem xét.

Điều này không gây ngạc nhiên. Ví dụ, xét hoạt động \(b\) là hoạt động gần nhất được xem xét trước \(a\), và một hoạt động \(c\) nào đó diễn ra sớm hơn nữa. Nếu chúng ta xem xét \(c\) trước \(b\), sự mất mát năng lượng ở hoạt động \(c\) đã được tính đến khi chúng ta xem xét \(b\), vì vậy giới hạn do \(b\) áp đặt sẽ không kém phần chặt chẽ. Mặt khác, nếu chúng ta xem xét \(c\) sau \(b\), điều đó có nghĩa là năng lượng tiêu tốn cho \(c\) đã được giới hạn sao cho tất cả sẽ được hồi phục khi đến \(b\) — và do đó nó không ảnh hưởng đến lượng năng lượng khả dụng tại \(a\). Lập luận tương tự cho các hoạt động diễn ra sau \(a\).

Một giải pháp mà mỗi bước mất thời gian logarit sẽ lấy mỗi hoạt động đã xem xét và chèn nó (cùng với các giới hạn mà nó áp đặt) vào một cây tìm kiếm nhị phân (như cấu trúc set trong nhiều ngôn ngữ). Sau đó, tại mỗi hoạt động tiếp theo, chúng ta tìm các hoạt động gần nhất đã được xem xét trước và sau nó, tính toán các giới hạn mà chúng áp đặt lên hoạt động hiện tại, tiêu tất cả năng lượng có thể (cập nhật tổng giá trị) và chèn hoạt động này (cùng với các giới hạn mới) vào cây.

Lưu ý rằng nếu \(R \ge E\), bạn có thể giả định \(R = E\), vì bất kỳ năng lượng nào bạn hồi phục vượt quá \(E\) chắc chắn sẽ bị lãng phí.

Giải pháp \(O(N)\)

Chìa khóa của giải pháp này là quan sát thấy rằng chúng ta thực sự có thể biết trước mình muốn tiêu bao nhiêu năng lượng vào một ngày nhất định. Như đã thấy ở trên, nếu không còn hoạt động nào có giá trị cao hơn ở phía trước, chúng ta nên tiêu hết năng lượng đang có. Mặt khác, nếu có hoạt động nào đó có giá trị cao hơn, tiết kiệm năng lượng luôn là ý hay nếu chúng ta có thể sử dụng nó cho hoạt động có giá trị cao hơn đó. Để tận dụng điều này, chúng ta cần biết, đối với mỗi hoạt động, hoạt động gần nhất trong tương lai có giá trị cao hơn.

Việc tính toán một mảng như vậy là một bài toán kinh điển, được mô tả là "Bài toán nhịp chứng khoán" (Stock Span Problem). Khi đã có mảng này, đối với mỗi hoạt động theo thứ tự thời gian, chúng ta có thể làm như sau:

• Nếu không có hoạt động nào giá trị hơn ở phía trước, hãy tiêu tất cả năng lượng đang có.
• Xét hoạt động giá trị hơn gần nhất \(X\). Nếu chúng ta có thể tiêu bất kỳ năng lượng nào mà vẫn có \(E\) năng lượng khi \(X\) đến (giả sử không tiêu gì từ giờ đến \(X\)), hãy tiêu nhiều nhất có thể trong khi vẫn đảm bảo có \(E\) khi đến \(X\). Lưu ý rằng phương án thay thế cho việc tiêu ngay bây giờ sẽ là tiêu trong khoảng thời gian từ nay đến \(X\) — nhưng không có hoạt động nào giá trị hơn hoạt động hiện tại trong khoảng đó để làm điều đó trở nên xứng đáng.
• Nếu chúng ta không thể tiêu bất kỳ năng lượng nào mà vẫn có \(E\) khi \(X\) đến, chúng ta không nên tiêu gì cả — toàn bộ năng lượng sẽ được sử dụng tốt hơn tại \(X\).

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