Hồi quy đơn điệu (Isotonic Regression, PAVA)
Tìm dãy không giảm gần một dãy cho trước nhất theo tổng sai số bình phương (có trọng số) bằng thuật toán gộp khối PAVA trong O(n). Kèm biến thể chuẩn L1 (trị tuyệt đối) giải bằng slope trick.
Hồi quy đơn điệu (isotonic regression) là bài toán: cho dãy và trọng số dương , tìm dãy không giảm (số thực) làm nhỏ nhất tổng sai số bình phương
Thuật toán gộp các khối liền kề vi phạm (Pool Adjacent Violators Algorithm, viết tắt PAVA) giải bài này trong bằng một ngăn xếp, đủ cho tới . Trong lập trình thi đấu, bài toán thường xuất hiện dưới dạng "chỉnh dãy thành dãy không giảm (hoặc không tăng) với chi phí bình phương nhỏ nhất", hoặc được che giấu sau một phép đổi biến (ví dụ là hồi quy đơn điệu với , ).
Biến thể với chi phí trị tuyệt đối (chuẩn ) cũng là hồi quy đơn điệu, nhưng giá trị của mỗi khối là trung vị thay vì trung bình. Bài viết trình bày cả hai.
Ý tưởng / Trực giác
Lời giải là các khối hằng. Lời giải tối ưu chia dãy thành các khối liên tiếp, trong mỗi khối mọi bằng nhau. Nếu một khối có chung giá trị thì
nên giá trị tốt nhất của khối là trung bình có trọng số . Quan trọng hơn: với mọi phần còn lại của bài toán, một khối hành xử y như một phần tử duy nhất có giá trị và trọng số .
Bổ đề gộp. Nếu hai phần tử (hay hai khối) liền kề vi phạm, tức , thì mọi lời giải tối ưu có .
Chứng minh. Giả sử . Nếu thì . Vậy luôn có hoặc . Trường hợp đầu, tăng thêm một lượng rất nhỏ: dãy vẫn không giảm (vì ) và sai số tại giảm. Trường hợp sau, giảm tương tự. Cả hai đều mâu thuẫn với tính tối ưu.
Thuật toán. Bổ đề cho phép gộp hai phần tử vi phạm thành một phần tử mới (trung bình, tổng trọng số), rồi lặp lại cho tới khi dãy các khối có trung bình tăng dần. Khi đó đặt là lời giải, vì nó không giảm và mỗi khối đã đạt cực tiểu riêng. Cài đặt bằng ngăn xếp: duyệt từ trái sang phải, đẩy phần tử mới thành một khối; chừng nào khối ở đỉnh có trung bình khối mới thì gộp. Một lần gộp có thể làm trung bình khối mới giảm xuống và lại vi phạm với khối bên dưới, nên phải gộp dây chuyền.
Hàm mục tiêu lồi chặt nên lời giải tối ưu là duy nhất, thứ tự gộp không ảnh hưởng kết quả. Gộp cả khi hai trung bình bằng nhau là vô hại (giá trị chung vẫn vậy) và giữ cho ngăn xếp tăng ngặt.
Chuẩn . Với , giá trị tốt nhất của một khối là trung vị có trọng số, và bổ đề gộp vẫn đúng với cùng chứng minh. Có thể cài PAVA với cấu trúc gộp được để lấy trung vị, nhưng cách ngắn nhất là slope trick với một max-heap: duyệt từng , đẩy vào heap; nếu phần tử lớn nhất trong heap lớn hơn thì cộng chênh lệch vào đáp án, lấy nó ra và đẩy thêm lần nữa.
Ví dụ chạy tay
Dãy , mọi trọng số bằng . Mỗi khối ghi dưới dạng (trung bình, số phần tử):
| Bước | Gộp với | Ngăn xếp sau bước (đáy bên trái) | |
|---|---|---|---|
| 1 | 1 | ||
| 2 | 4 | ||
| 3 | 2 | vì | |
| 4 | 3 | vì | |
| 5 | 6 | ||
| 6 | 0 | rồi : dây chuyền | |
| 7 | 5 |
Ở bước 6, khối mới gộp với thành trung bình , vẫn khối bên dưới nên gộp tiếp thành có trung bình .
khối: [1] [ 4 2 3 6 0 ] [5]
y : 1 4 2 3 6 0 5
b : 1 3 3 3 3 3 5
Chi phí: . Với chuẩn (cùng dãy), slope trick cho đáp án , đạt tại ví dụ : .
Cài đặt
PAVA cho chuẩn có trọng số
Dữ liệu: , dãy số nguyên , dãy trọng số nguyên dương . In chi phí nhỏ nhất và dãy . Mọi tổng được giữ bằng số nguyên, phép so sánh trung bình dùng nhân chéo, và chi phí mỗi khối có tử số tính chính xác bằng __int128 (giả sử vừa long long).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 i128;
// Một khối liên tiếp: W = tổng trọng số, S = tổng w*y, Q = tổng w*y^2, cnt = số phần tử
struct Block {
ll W, S, Q;
int cnt;
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> y(n), w(n);
for (auto& v : y) cin >> v;
for (auto& v : w) cin >> v;
vector<Block> st; // ngăn xếp khối, trung bình S/W tăng ngặt từ đáy lên đỉnh
for (int i = 0; i < n; i++) {
Block cur{w[i], w[i] * y[i], w[i] * y[i] * y[i], 1};
// đỉnh có trung bình >= khối mới: vi phạm (hoặc bằng), gộp lại
// so sánh S_top / W_top >= S_cur / W_cur bằng nhân chéo (W > 0)
while (!st.empty() && (i128)st.back().S * cur.W >= (i128)cur.S * st.back().W) {
Block& t = st.back();
cur = {cur.W + t.W, cur.S + t.S, cur.Q + t.Q, cur.cnt + t.cnt};
st.pop_back();
}
st.push_back(cur);
}
// chi phí một khối = Q - S^2/W = (Q*W - S^2) / W, tử số tính chính xác bằng __int128
long double cost = 0;
for (auto& b : st) cost += (long double)((i128)b.Q * b.W - (i128)b.S * b.S) / b.W;
cout << fixed << setprecision(6) << (double)cost << '\n';
// dãy b: mỗi phần tử trong khối nhận trung bình của khối
for (auto& b : st)
for (int k = 0; k < b.cnt; k++) cout << (double)((long double)b.S / b.W) << ' ';
cout << '\n';
}
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
y = [int(x) for x in data[1 : 1 + n]]
w = [int(x) for x in data[1 + n : 1 + 2 * n]]
# Ngăn xếp khối, mỗi khối [W, S, Q, cnt]: tổng w, tổng w*y, tổng w*y^2, số phần tử
st = []
for i in range(n):
cW, cS, cQ, cc = w[i], w[i] * y[i], w[i] * y[i] * y[i], 1
# đỉnh có trung bình >= khối mới: gộp (so sánh nhân chéo, số nguyên chính xác)
while st and st[-1][1] * cW >= cS * st[-1][0]:
tW, tS, tQ, tc = st.pop()
cW, cS, cQ, cc = cW + tW, cS + tS, cQ + tQ, cc + tc
st.append((cW, cS, cQ, cc))
# chi phí khối = (Q*W - S^2) / W, tử số là số nguyên chính xác
cost = sum((Q * W - S * S) / W for W, S, Q, _ in st)
b = []
for W, S, Q, c in st:
b += ["%.6f" % (S / W)] * c
sys.stdout.write("%.6f\n%s\n" % (cost, " ".join(b)))
main()
Chuẩn : số thao tác ít nhất để dãy không giảm
Dữ liệu: rồi dãy số nguyên . In chi phí nhỏ nhất và một dãy tối ưu. Đỉnh heap sau bước là giá trị cuối tối ưu khi chỉ xét phần tử đầu; dãy các đỉnh này không đơn điệu, nên khôi phục bằng cách đi ngược và lấy min.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n), top(n);
priority_queue<long long> pq; // các điểm gãy bên trái điểm cực tiểu (max-heap)
long long ans = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
pq.push(a[i]);
if (pq.top() > a[i]) { // phần tử lớn nhất đứng trước lớn hơn a[i]: vi phạm
ans += pq.top() - a[i]; // trả chi phí kéo hai giá trị về cùng một mức
pq.pop();
pq.push(a[i]);
}
top[i] = pq.top(); // giá trị cuối tối ưu khi chỉ xét i+1 phần tử đầu
}
// khôi phục: đi ngược, b[i] = min(top[i], b[i+1])
vector<long long> b(n);
b[n - 1] = top[n - 1];
for (int i = n - 2; i >= 0; i--) b[i] = min(top[i], b[i + 1]);
cout << ans << '\n';
for (int i = 0; i < n; i++) cout << b[i] << (i + 1 < n ? ' ' : '\n');
}
import heapq
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = [int(x) for x in data[1 : 1 + n]]
pq = [] # max-heap bằng cách lưu số đối
top = [0] * n
ans = 0
for i in range(n):
heapq.heappush(pq, -a[i])
if -pq[0] > a[i]: # phần tử lớn nhất đứng trước lớn hơn a[i]: vi phạm
ans += -pq[0] - a[i] # trả chi phí kéo hai giá trị về cùng một mức
heapq.heapreplace(pq, -a[i])
top[i] = -pq[0] # giá trị cuối tối ưu khi chỉ xét i+1 phần tử đầu
# khôi phục: đi ngược, b[i] = min(top[i], b[i+1])
b = [0] * n
b[n - 1] = top[n - 1]
for i in range(n - 2, -1, -1):
b[i] = min(top[i], b[i + 1])
print(ans)
print(" ".join(map(str, b)))
main()
Muốn dãy tăng ngặt (với nguyên) thì đặt rồi giải bài không giảm: . Muốn dãy không tăng thì đảo ngược dãy (hoặc đổi dấu).
Độ phức tạp
| Phiên bản | Thời gian | Bộ nhớ |
|---|---|---|
| PAVA, chuẩn (có trọng số) | ||
| Slope trick, chuẩn |
Vì sao PAVA là ? Mỗi phần tử được đẩy vào ngăn xếp đúng một lần như một khối mới, và mỗi lần gộp làm số khối giảm đi một. Tổng số lần gộp không quá , dù một bước có thể gộp dây chuyền nhiều lần. Trên máy thử, chạy khoảng giây với C++ và giây với Python.
Chuẩn : mỗi phần tử gây tối đa hai thao tác heap .
⚠️ Lỗi thường gặp
- Không gộp dây chuyền: chỉ gộp khối mới với đỉnh một lần là sai. Ở bước 6 của ví dụ, khối có trung bình vẫn vi phạm (hoặc bằng) với khối bên dưới; phải dùng
while, không phảiif. - Lấy max tiền tố thay vì trung bình: đặt cho dãy không giảm nhưng không tối ưu (ví dụ : max tiền tố cho chi phí , còn tối ưu là với chi phí ).
- Mất chính xác khi tính chi phí: công thức bằng số thực trừ hai số rất lớn gần bằng nhau, đáp án nhỏ sẽ mất hết chữ số có nghĩa. Tính tử số chính xác bằng số nguyên (
__int128nếu cần) cho từng khối rồi mới chia. Với dữ liệu thập phân (ví dụ 3 chữ số sau dấu phẩy) thì nhân lên thành số nguyên trước. - So sánh trung bình bằng phép chia:
S1 / W1 >= S2 / W2với số thực có thể sai khi hai trung bình bằng nhau hoặc rất gần nhau. Dùng nhân chéoS1 * W2 >= S2 * W1(trọng số dương nên không đổi chiều). - Sai chiều đơn điệu: đề yêu cầu dãy không tăng () thì điều kiện gộp đảo thành "đỉnh có trung bình khối mới", hoặc đảo ngược dãy rồi giải bài không giảm.
- Dùng trung bình cho chuẩn : với giá trị của khối là trung vị, không phải trung bình. Dùng nhầm PAVA trung bình sẽ cho đáp án sai (và thường không nguyên).
Biến thể / Mở rộng
- Chuẩn và tăng ngặt: xử lý bằng slope trick như phần cài đặt; phép đổi biến chuyển tăng ngặt về không giảm.
- Mọi phải nằm trong cùng một đoạn : chạy PAVA rồi cắt giá trị mỗi khối vào ; kết quả vẫn tối ưu.
- Ràng buộc trên cây (cha con) hay trên thứ tự bộ phận tổng quát: không còn ngăn xếp đơn giản; trên cây có thể gộp các khối bằng heap gộp được hoặc DSU theo kiểu nhỏ vào lớn.
- Liên hệ: ngăn xếp các khối có trung bình tăng dần là một dạng ngăn xếp đơn điệu; tư tưởng "gộp hai phần tử phải bằng nhau" là một lập luận tham lam đổi chỗ.
Bài tập luyện
- Dãy số (dhbb26dx0710_b): (Hard) Chi phí nhỏ nhất để dãy thành không giảm: hồi quy đơn điệu chuẩn , quy hoạch động trên giá trị hoặc slope trick.
- Dãy không giảm (dhbb25dx0511_seq): (Very Hard) Cùng mô hình chuẩn với dãy dài hơn; nghiệm tối ưu chỉ dùng giá trị có trong dãy, giải bằng slope trick với max-heap.
- Dãy số không giảm (thhv19cpt10_b): (Very Hard) Số thao tác ít nhất để dãy thành không giảm, chính là hồi quy đơn điệu chuẩn , giải bằng slope trick với max-heap.
- Đồng hiđroxit (icpc21mtc): (Very Hard) Tìm dãy không giảm gần nhất theo khoảng cách Euclid với tới : PAVA chuẩn không trọng số, nhân dữ liệu lên và tính chi phí khối bằng số nguyên 128 bit.
- Làm dãy tăng nghiêm ngặt (ck04inc): (Very Hard) Dãy tăng ngặt gần nhất theo chuẩn : đổi biến để bỏ chữ "ngặt", rồi hồi quy đơn điệu chuẩn bằng slope trick.
- Tổng bình phương (icpc22mne): (Very Hard) Cực tiểu với không tăng: đổi biến thành hồi quy đơn điệu có trọng số , mỗi khối lưu ba tổng .
- Dãy xấp xỉ tăng (voi18_seq): (Very Hard) Dãy nguyên tăng ngặt gần nhất theo chuẩn , kèm in dãy: đổi biến rồi hồi quy đơn điệu chuẩn , khôi phục dãy bằng đỉnh heap sau từng bước như phần cài đặt.
Bình luận