Dựng một dãy nhiệt độ ban đầu

Một hướng giải là dựng dãy nhiệt độ bắt đầu bằng \(K-1\) số 0, rồi duyệt một lần qua cả \(N-K+1\) tổng cửa sổ làm mượt để điền phần còn lại. Chẳng hạn, với dãy tổng 0 12 0 12 0 và \(K=3\) trong ví dụ thứ ba, cách dựng này cho dãy 0 0 0 12 -12 12 0, có chênh lệch giữa nhiệt độ lớn nhất và nhỏ nhất là 24. Để thu được dãy có chênh lệch nhỏ nhất, ta sẽ điều chỉnh một số giá trị như sau.

Với \(0\le i<K\), định nghĩa \(\operatorname{GROUP}(i)\) là nhóm chứa các nhiệt độ ở những vị trí có chỉ số đồng dư \(i\) modulo \(K\). Dãy 0 0 0 12 -12 12 0 ở trên được chia thành:

1. 0 12 0, từ các nhiệt độ thứ nhất, thứ tư và thứ bảy;
2. 0 -12, từ các nhiệt độ thứ hai và thứ năm;
3. 0 12, từ các nhiệt độ thứ ba và thứ sáu.

Thay đổi nhiệt độ thứ \(i\) thêm \(Z\) độ đòi hỏi bù lại ở các nhiệt độ khác. Một cách là cộng \(Z\) cho tất cả nhiệt độ khác trong cùng nhóm và trừ \(Z\) khỏi tất cả nhiệt độ trong một nhóm khác. Ví dụ, để tăng nhiệt độ đầu tiên thêm 3 độ, ta cũng tăng nhiệt độ thứ tư và thứ bảy thêm 3, đồng thời giảm các nhiệt độ trong nhóm thứ hai (hoặc thứ ba) đi 3. Dãy mới là 3 -3 0 15 -15 12 3; dãy tổng cửa sổ vẫn là 0 12 0 12 0.

Định nghĩa:

• \(lo(i)\) là phần tử nhỏ nhất trong \(\operatorname{GROUP}(i)\);
• \(hi(i)\) là phần tử lớn nhất trong \(\operatorname{GROUP}(i)\);
• \(interval(i)\) là đoạn \([lo(i),hi(i)]\);
• \(\operatorname{SHIFT}(i,y)\) là thao tác cộng \(y\) vào mọi phần tử của \(\operatorname{GROUP}(i)\).

Mô hình các đoạn

Ta có thể phát biểu lại bài toán như sau. Cho \(K\) đoạn, đoạn thứ \(i\) kéo dài từ \(lo(i)\) đến \(hi(i)\). Được thực hiện tùy ý các phép điều chỉnh bằng cách chọn \(i,j,y\) với \(0\le i,j<K\), dịch đoạn \(i\) đi \(y\) (tức \(\operatorname{SHIFT}(i,y)\)) và dịch đoạn \(j\) đi \(-y\) (tức \(\operatorname{SHIFT}(j,-y)\)). Hãy tối thiểu hóa độ dài đoạn bao phủ tất cả các đoạn:

Giá trị nhỏ nhất này chính là chênh lệch nhỏ nhất có thể giữa nhiệt độ lớn nhất và nhỏ nhất của bài toán ban đầu. Thứ tự các phép điều chỉnh không quan trọng.

Các phép dịch có thể thực hiện độc lập và gộp lại: ta có thể cộng dồn mọi dịch chuyển dương để làm một lần, và tương tự với dịch chuyển âm. Vì thế, chuẩn hóa mọi đoạn bằng cách dịch chúng sao cho cận dưới đều bằng 0. Gọi

là tổng độ dịch phải phân phối trả lại. Ví dụ, hai đoạn \([-10,-8]\) và \([333,777]\) sau chuẩn hóa trở thành \([0,2]\) và \([0,444]\), với \(Q=-10+333=323\). Cuối cùng phải dịch trả tổng cộng \(Q\) độ cho các đoạn đã chuẩn hóa, nhưng được tùy ý phân phối số dịch này để độ phủ nhỏ nhất.

Nếu tăng hoặc giảm tất cả các đoạn cùng 1 đơn vị, vị trí tương đối của chúng không đổi nên độ phủ cũng không đổi. Do đó, có thể rút gọn \(Q\) thành \(Q\bmod K\) bằng cách phân phối đều phần bội của \(K\) cho mọi đoạn. Nếu \(Q\) âm, tiếp tục cộng \(K\) cho đến khi \(Q\) không âm.

Ví dụ, giả sử có ba đoạn chuẩn hóa \([0,4]\), \([0,9]\), \([0,7]\) và tổng độ dịch \(Q=40\). Có thể phân phối đều 39 đơn vị: mỗi đoạn dịch 13, trở thành \([13,17]\), \([13,22]\), \([13,20]\). Sau đó dịch tất cả trở lại lần lượt thành \([0,4]\), \([0,9]\), \([0,7]\) mà không đổi vị trí tương đối, và chỉ còn \(Q=1\) cần phân phối.

Phân phối phần dịch còn lại

Gọi \(L\) là độ dài của đoạn dài nhất. Nếu \(Q=0\), không còn độ dịch dư và độ phủ nhỏ nhất là \(L\).

Nếu \(Q>0\), có thể cấp cho đoạn \(i\) tối đa

đơn vị dịch mà chưa làm tăng đáp án. Trong ví dụ trên, độ phủ hiện tại là \(L=9\). Ta có thể cấp 1 đơn vị dịch cho đoạn \([0,4]\) để được \([1,5]\) mà không làm thay đổi độ phủ nhỏ nhất.

Nếu sau khi tận dụng tất cả sức chứa này vẫn còn độ dịch dư, ta không thể phân phối thêm mà giữ nguyên độ phủ. Tăng độ phủ thêm 1 tạo thêm chỗ cho \(K\) đơn vị dịch, đủ cho toàn bộ phần còn lại vì \(Q\) đã được lấy modulo \(K\) nên \(Q<K\). Vì vậy đáp án chỉ có thể là \(L\) hoặc \(L+1\) theo phép kiểm tra sức chứa trên.

Toàn bộ cách giải có độ phức tạp \(O(N)\).

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