Chia nhóm (Đề tự luyện HSG Tin quốc gia – Bài 1) – QHĐ kết hợp cây phân đoạn và hai ngăn xếp đơn điệu

Nguồn: Đề tự luyện HSG Tin học quốc gia – Bài 1 (đề tự soạn) Độ khó: Khó Quy hoạch động Cây phân đoạn (lazy) Ngăn xếp đơn điệu

Đề bài

Chia nhóm

Thầy Sơn có $N$ học sinh đứng thành hàng, học sinh thứ $i$ có điểm $a_i$. Thầy chia cả hàng thành các nhóm gồm các bạn đứng liên tiếp (không đổi chỗ). Mỗi nhóm tốn chi phí $C + (\max - \min)$, trong đó $\max, \min$ là điểm lớn nhất, nhỏ nhất trong nhóm. Tìm tổng chi phí nhỏ nhất.

Giới hạn: $1 \le N \le 2 \cdot 10^5$, $0 \le C \le 10^9$, $0 \le a_i \le 10^9$.

Subtask:

• Subtask 1 (30%): $N \le 5000$.
• Subtask 2 (20%): $a_1 \le a_2 \le \dots \le a_N$.
• Subtask 3 (50%): không có ràng buộc gì thêm.

Input

9 5
1 3 2 20 21 20 5 4 6

Output

20

Giải thích

[1 3 2] [20 21 20] [5 4 6]
(5+2) + (5+1) + (5+2) = 20

Dành cho học viênNộp bài trên ClueOJ

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.

Nộp bài Chia nhóm

Lời mở đầu

Bài này nhìn thì giống bài tham lam ("cứ gom tới khi chênh lệch quá lớn thì cắt"), nhưng tham lam sai. Ví dụ của đề cho thấy cách chia tốt nhất:

Ba nhóm, mỗi nhóm có điểm gần nhau. Gom cả 9 bạn vào một nhóm thì tốn $5 + (21 - 1) = 25$; để mỗi bạn một nhóm thì tốn $9 \times 5 = 45$.

Gọi $f[i]$ là chi phí nhỏ nhất để chia $i$ bạn đầu hàng. Nhóm cuối cùng là đoạn $a[j+1..i]$ với $0 \le j < i$ nào đó, phần còn lại $a[1..j]$ được chia tối ưu với chi phí $f[j]$:

$$f[i] = C + \min_{0 \le j < i} \Big( f[j] + \max(a_{j+1..i}) - \min(a_{j+1..i}) \Big), \qquad f[0] = 0.$$

Đáp án là $f[N]$. Cả bài chỉ xoay quanh việc tính công thức này nhanh tới đâu.

Một nhận xét nhỏ mà hay

Gom cả hàng vào một nhóm thì tốn $C + (\max - \min) \le 10^9 + 10^9$, nên đáp án luôn không vượt quá $2 \cdot 10^9$. Tuy vậy, khi cài đặt các giá trị trung gian như $f[j] + \max - \min$ vẫn có thể vượt int, nên cứ dùng long long cho an toàn.

Cách 1QHĐ O(N²) · 30%Cách 2+ dãy không giảm · 50%Cách 3Cây phân đoạn + ngăn xếp · 100%

Cách 1QHĐ trực tiếp – O(N²) · 30%

Với mỗi $i$, duyệt $j$ lùi từ $i - 1$ về $0$: mỗi lần lùi thì nhóm cuối có thêm phần tử $a[j+1]$, ta cập nhật $\max, \min$ trong $O(1)$ thay vì tính lại cả đoạn. Tổng cộng $\frac{N(N+1)}{2}$ phép thử, với $N = 5000$ là khoảng $1{,}25 \cdot 10^7$ – rất nhanh.

Các bạn bấm từng bước ở khung dưới để xem bảng $f$ được điền và cách chia tối ưu được truy vết ra sao:

C = Dãy a:

Ví dụ nhanh:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// Cach 1: QHD O(N^2) - f[i] = chi phi nho nhat de chia i hoc sinh dau tien
int main(){
    int n; ll C;
    cin >> n >> C;
    vector<ll> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    vector<ll> f(n + 1, LLONG_MAX);
    f[0] = 0;
    for(int i = 1; i <= n; i++){
        ll mx = a[i], mn = a[i];
        for(int j = i - 1; j >= 0; j--){      // nhom cuoi cung la a[j+1..i]
            mx = max(mx, a[j + 1]);
            mn = min(mn, a[j + 1]);
            f[i] = min(f[i], f[j] + C + mx - mn);
        }
    }
    cout << f[n];
    return 0;
}

import sys

# Cach 1: QHD O(N^2) - f[i] = chi phi nho nhat de chia i hoc sinh dau tien
def main():
    data = sys.stdin.buffer.read().split()
    n, C = int(data[0]), int(data[1])
    a = [0] + [int(v) for v in data[2:2 + n]]
    f = [0] * (n + 1)
    for i in range(1, n + 1):
        mx = mn = a[i]
        best = None
        for j in range(i - 1, -1, -1):        # nhom cuoi cung la a[j+1..i]
            if a[j + 1] > mx: mx = a[j + 1]
            if a[j + 1] < mn: mn = a[j + 1]
            v = f[j] + C + mx - mn
            if best is None or v < best: best = v
        f[i] = best
    print(f[n])

main()

Không gian$O(N)$

Thời gian$O(N^2)$

Cách 2Thêm trường hợp dãy không giảm – O(N) · 50%

Khi $a_1 \le a_2 \le \dots \le a_N$ thì nhóm $a[j+1..i]$ có $\max = a_i$ và $\min = a_{j+1}$, công thức tách được thành hai phần độc lập:

$$f[i] = a_i + C + \min_{0 \le j < i} \big( f[j] - a_{j+1} \big).$$

Phần $\min$ chỉ phụ thuộc $j$, nên ta giữ một biến best là giá trị nhỏ nhất của $f[j] - a_{j+1}$ tới hiện tại – mỗi $i$ chỉ tốn $O(1)$. Ghép với Cách 1 (dùng khi dãy không đơn điệu) là được 50%.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// Cach 2: Cach 1 + truong hop day khong giam (subtask 2) giai O(N)
int main(){
    int n; ll C;
    cin >> n >> C;
    vector<ll> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    vector<ll> f(n + 1, LLONG_MAX);
    f[0] = 0;
    bool khongGiam = true;
    for(int i = 2; i <= n; i++) if(a[i] < a[i - 1]) khongGiam = false;
    if(khongGiam){
        // nhom a[j+1..i] co max - min = a[i] - a[j+1]
        // f[i] = a[i] + C + min_{j < i} (f[j] - a[j+1])
        ll best = f[0] - a[1];
        for(int i = 1; i <= n; i++){
            f[i] = a[i] + C + best;
            if(i < n) best = min(best, f[i] - a[i + 1]);
        }
    } else {
        for(int i = 1; i <= n; i++){
            ll mx = a[i], mn = a[i];
            for(int j = i - 1; j >= 0; j--){
                mx = max(mx, a[j + 1]);
                mn = min(mn, a[j + 1]);
                f[i] = min(f[i], f[j] + C + mx - mn);
            }
        }
    }
    cout << f[n];
    return 0;
}

import sys

# Cach 2: Cach 1 + truong hop day khong giam (subtask 2) giai O(N)
def main():
    data = sys.stdin.buffer.read().split()
    n, C = int(data[0]), int(data[1])
    a = [0] + [int(v) for v in data[2:2 + n]]
    f = [0] * (n + 1)
    if all(a[i] >= a[i - 1] for i in range(2, n + 1)):
        # nhom a[j+1..i] co max - min = a[i] - a[j+1]
        best = f[0] - a[1]
        for i in range(1, n + 1):
            f[i] = a[i] + C + best
            if i < n:
                best = min(best, f[i] - a[i + 1])
    else:
        for i in range(1, n + 1):
            mx = mn = a[i]
            best = None
            for j in range(i - 1, -1, -1):
                if a[j + 1] > mx: mx = a[j + 1]
                if a[j + 1] < mn: mn = a[j + 1]
                v = f[j] + C + mx - mn
                if best is None or v < best: best = v
            f[i] = best
    print(f[n])

main()

Không gian$O(N)$

Thời gian$O(N)$ với dãy không giảm, $O(N^2)$ với trường hợp còn lại

Cách 3Cây phân đoạn + hai ngăn xếp đơn điệu – O(N log N) · 100%

Ý tưởng của Cách 2 dùng được vì $\max$ và $\min$ "đứng yên". Trong trường hợp tổng quát, ta không tính lại từng $j$ mà duy trì cả mảng

$$val[j] = f[j] + \max(a_{j+1..i}) - \min(a_{j+1..i}) \qquad (0 \le j < i)$$

trên một cây phân đoạn hỗ trợ cộng một đoạn và lấy min một đoạn. Khi đó $f[i] = C + \min(val[0..i-1])$. Vấn đề là khi $i$ tăng lên 1 thì $val[j]$ thay đổi thế nào?

• Thêm một $j$ mới là $j = i - 1$: nhóm cuối chỉ có $a_i$ nên $val[i-1] = f[i-1]$.
• Với các $j$ cũ, $\max(a_{j+1..i})$ có thể tăng lên thành $a_i$. Ta nhóm các $j$ có cùng giá trị max thành từng khối liên tiếp – các khối này chính là các phần tử của một ngăn xếp đơn điệu giảm smax. Phần tử $k$ trong ngăn xếp đại diện cho khối $j \in [k', k-1]$ ($k'$ là phần tử nằm dưới $k$) có max bằng $a_k$.
• Khi thêm $a_i$, mọi khối có $a_k \le a_i$ bị "nuốt": max của cả khối đổi từ $a_k$ thành $a_i$, tức là cộng $a_i - a_k$ cho cả đoạn $[k', k-1]$. Phần $\min$ làm y hệt với ngăn xếp tăng smin (và cộng $a_k - a_i$, vì min giảm thì $-\min$ tăng).

Mỗi chỉ số được đẩy vào và lấy ra khỏi mỗi ngăn xếp nhiều nhất một lần, nên tổng số lần "cộng đoạn" là $O(N)$, mỗi lần tốn $O(\log N)$ trên cây phân đoạn.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// Cach 3: QHD + cay phan doan (cong doan, min doan) + 2 ngan xep don dieu - O(N log N)
// val[j] = f[j] + max(a[j+1..i]) - min(a[j+1..i]),  f[i] = C + min(val[0..i-1])
int n;
vector<ll> t, lz;
void add(int o, int l, int r, int ql, int qr, ll v){        // cong v vao val[ql..qr]
    if(qr < l || r < ql) return;
    if(ql <= l && r <= qr){ t[o] += v; lz[o] += v; return; }
    int m = (l + r) / 2;
    add(2 * o, l, m, ql, qr, v); add(2 * o + 1, m + 1, r, ql, qr, v);
    t[o] = min(t[2 * o], t[2 * o + 1]) + lz[o];
}
void setv(int o, int l, int r, int p, ll v){                // gan val[p] = v
    if(l == r){ t[o] = v; lz[o] = 0; return; }
    int m = (l + r) / 2; v -= lz[o];
    if(p <= m) setv(2 * o, l, m, p, v); else setv(2 * o + 1, m + 1, r, p, v);
    t[o] = min(t[2 * o], t[2 * o + 1]) + lz[o];
}
ll getmin(int o, int l, int r, int ql, int qr){             // min val[ql..qr]
    if(qr < l || r < ql) return LLONG_MAX / 4;
    if(ql <= l && r <= qr) return t[o];
    int m = (l + r) / 2;
    return min(getmin(2 * o, l, m, ql, qr), getmin(2 * o + 1, m + 1, r, ql, qr)) + lz[o];
}
int main(){
    ll C;
    scanf("%d %lld", &n, &C);
    vector<ll> a(n + 1);
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    t.assign(4 * n + 4, LLONG_MAX / 4); lz.assign(4 * n + 4, 0);
    vector<ll> f(n + 1, 0);
    vector<int> smax, smin;                 // chi so: a giam dan / a tang dan
    for(int i = 1; i <= n; i++){
        setv(1, 0, n - 1, i - 1, f[i - 1]);  // j = i - 1: nhom chi gom a[i]
        while(!smax.empty() && a[smax.back()] <= a[i]){
            int k = smax.back(); smax.pop_back();
            int lo = smax.empty() ? 0 : smax.back();
            add(1, 0, n - 1, lo, k - 1, a[i] - a[k]);   // max cua cac j nay doi tu a[k] thanh a[i]
        }
        smax.push_back(i);
        while(!smin.empty() && a[smin.back()] >= a[i]){
            int k = smin.back(); smin.pop_back();
            int lo = smin.empty() ? 0 : smin.back();
            add(1, 0, n - 1, lo, k - 1, a[k] - a[i]);   // min giam tu a[k] xuong a[i]
        }
        smin.push_back(i);
        f[i] = getmin(1, 0, n - 1, 0, i - 1) + C;
    }
    printf("%lld\n", f[n]);
    return 0;
}

import sys

# Cach 3: QHD + cay phan doan (cong doan, min doan) + 2 ngan xep don dieu - O(N log N)
def main():
    data = sys.stdin.buffer.read().split()
    n, C = int(data[0]), int(data[1])
    a = [0] + [int(v) for v in data[2:2 + n]]
    INF = float('inf')
    size = 1
    while size < n: size *= 2
    t = [INF] * (2 * size)       # t[o] = min cua nut o (da tinh lz cua chinh no)
    lz = [0] * (2 * size)

    def add(ql, qr, v, o=1, l=0, r=size - 1):
        if qr < l or r < ql: return
        if ql <= l and r <= qr:
            t[o] += v; lz[o] += v; return
        m = (l + r) // 2
        add(ql, qr, v, 2 * o, l, m); add(ql, qr, v, 2 * o + 1, m + 1, r)
        t[o] = min(t[2 * o], t[2 * o + 1]) + lz[o]

    def setv(p, v):
        path = []; o, l, r = 1, 0, size - 1
        while l < r:
            path.append(o); v -= lz[o]
            m = (l + r) // 2
            if p <= m: o, r = 2 * o, m
            else: o, l = 2 * o + 1, m + 1
        t[o] = v; lz[o] = 0
        for o in reversed(path):
            t[o] = min(t[2 * o], t[2 * o + 1]) + lz[o]

    def getmin(ql, qr, o=1, l=0, r=size - 1):
        if qr < l or r < ql: return INF
        if ql <= l and r <= qr: return t[o]
        m = (l + r) // 2
        return min(getmin(ql, qr, 2 * o, l, m), getmin(ql, qr, 2 * o + 1, m + 1, r)) + lz[o]

    f = [0] * (n + 1)
    smax, smin = [], []
    for i in range(1, n + 1):
        setv(i - 1, f[i - 1])
        while smax and a[smax[-1]] <= a[i]:
            k = smax.pop(); lo = smax[-1] if smax else 0
            add(lo, k - 1, a[i] - a[k])
        smax.append(i)
        while smin and a[smin[-1]] >= a[i]:
            k = smin.pop(); lo = smin[-1] if smin else 0
            add(lo, k - 1, a[k] - a[i])
        smin.append(i)
        f[i] = getmin(0, i - 1) + C
    print(f[n])

sys.setrecursionlimit(10000)
main()

Các bạn bấm chạy tay code C++ để xem từng dòng nhé (để dễ nhìn, khung bên phải vẽ thẳng mảng $val$ thay vì cây phân đoạn; ô vàng là đoạn vừa được cộng):

C++▶ Chạy tay từng dòng codeCách 3: duy trì val[j] = f[j] + max − min bằng cây phân đoạn và hai ngăn xếp đơn điệu.

Dữ liệu vào (stdin) – sửa thoải mái9 5 1 3 2 20 21 20 5 4 6

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3typedef long long ll;

4

5// Cach 3: QHD + cay phan doan (cong doan, min doan) + 2 ngan xep don dieu - O(N log N)

6// val[j] = f[j] + max(a[j+1..i]) - min(a[j+1..i]), f[i] = C + min(val[0..i-1])

7int n;

8vector<ll> t, lz;

9void add(int o, int l, int r, int ql, int qr, ll v){ // cong v vao val[ql..qr]

10 if(qr < l || r < ql) return;

11 if(ql <= l && r <= qr){ t[o] += v; lz[o] += v; return; }

12 int m = (l + r) / 2;

13 add(2 * o, l, m, ql, qr, v); add(2 * o + 1, m + 1, r, ql, qr, v);

14 t[o] = min(t[2 * o], t[2 * o + 1]) + lz[o];

15}

16void setv(int o, int l, int r, int p, ll v){ // gan val[p] = v

17 if(l == r){ t[o] = v; lz[o] = 0; return; }

18 int m = (l + r) / 2; v -= lz[o];

19 if(p <= m) setv(2 * o, l, m, p, v); else setv(2 * o + 1, m + 1, r, p, v);

20 t[o] = min(t[2 * o], t[2 * o + 1]) + lz[o];

21}

22ll getmin(int o, int l, int r, int ql, int qr){ // min val[ql..qr]

23 if(qr < l || r < ql) return LLONG_MAX / 4;

24 if(ql <= l && r <= qr) return t[o];

25 int m = (l + r) / 2;

26 return min(getmin(2 * o, l, m, ql, qr), getmin(2 * o + 1, m + 1, r, ql, qr)) + lz[o];

27}

28int main(){

29 ll C;

30 scanf("%d %lld", &n, &C);

31 vector<ll> a(n + 1);

32 for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);

33 t.assign(4 * n + 4, LLONG_MAX / 4); lz.assign(4 * n + 4, 0);

34 vector<ll> f(n + 1, 0);

35 vector<int> smax, smin; // chi so: a giam dan / a tang dan

36 for(int i = 1; i <= n; i++){

37 setv(1, 0, n - 1, i - 1, f[i - 1]); // j = i - 1: nhom chi gom a[i]

38 while(!smax.empty() && a[smax.back()] <= a[i]){

39 int k = smax.back(); smax.pop_back();

40 int lo = smax.empty() ? 0 : smax.back();

41 add(1, 0, n - 1, lo, k - 1, a[i] - a[k]); // max cua cac j nay doi tu a[k] thanh a[i]

42 }

43 smax.push_back(i);

44 while(!smin.empty() && a[smin.back()] >= a[i]){

45 int k = smin.back(); smin.pop_back();

46 int lo = smin.empty() ? 0 : smin.back();

47 add(1, 0, n - 1, lo, k - 1, a[k] - a[i]); // min giam tu a[k] xuong a[i]

48 }

49 smin.push_back(i);

50 f[i] = getmin(1, 0, n - 1, 0, i - 1) + C;

51 }

52 printf("%lld\n", f[n]);

53 return 0;

54}

ChậmVừaNhanhRất nhanh

Không gian$O(N)$

Thời gian$O(N \log N)$

Những cái bẫy trong bộ test

1. Tham lam ("nếu thêm bạn kế tiếp làm chênh lệch tăng không quá $C$ thì gom vào, không thì mở nhóm mới"): đúng với dãy không giảm nhưng sai khi điểm lên xuống – xem ví dụ "Tham lam bị lừa" ở khung minh hoạ.
2. Tưởng chi phí nhóm chỉ phụ thuộc hai đầu, tức thay $\max - \min$ bằng $|a_{j+1} - a_i|$ để dùng cây Fenwick: cũng chỉ đúng với dãy đơn điệu. Ví dụ 1 của đề đã bắt được lỗi này.
3. Quên cập nhật cả hai ngăn xếp hoặc cập nhật sai đoạn $[k', k-1]$ (lệch một chỉ số): các test răng cưa, khối bằng nhau và dãy giảm dần được cài vào để bắt lỗi này.
4. Code $O(N^2)$ với $N = 2 \cdot 10^5$ cần khoảng $2 \cdot 10^{10}$ phép tính – chắc chắn quá thời gian.

Bộ test chấm "bắt" những lỗi nào?

Cách làm	Sub 1	Sub 2	Sub 3	Điểm
Cách 1 – QHĐ O(N²)	Đúng	TLE	TLE	30
Cách 2 – thêm dãy không giảm	Đúng	Đúng	TLE	50
Tham lam gom nhóm	Sai	Đúng	Sai	20
Coi chi phí là |đầu − cuối|	Sai	Đúng	Sai	20
Cách 3 đầy đủ	Đúng	Đúng	Đúng	100

Ghi chú của mình: các code C++ ở trên đã được nộp thử trên ClueOJ với đúng bộ test của bài (giới hạn 1 giây, cách 3 chạy tối đa khoảng 0,2 giây). Bản Python cách 3 cho kết quả đúng nhưng chậm hơn nhiều với $N = 2 \cdot 10^5$, đi thi nên dùng C++.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇