Hướng dẫn cho LQDOJ CUP 2022 - Round 3 - QBST

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: zipdang04

Subtask $1$ ($20\%$ số điểm): $n \leq 20$.

Tutorial

Gọi $\max_u = \max (s_1, s_2, \dots, s_n)$ là giá trị của cây con gốc $u$.

Ta nhận thấy, với một cây bất kỳ chứa các đỉnh $\{l, l+1, l+2, \dots, r-1, r\}$ (từ giờ ta sẽ gọi là cây đoạn $(l, r)$), nếu đỉnh $u\ (l \le u \le r)$ là gốc của cây, thì cây con trái của đỉnh $u$ (nếu có) sẽ là cây đoạn $(l, u-1)$ và cây con phải (nếu có) sẽ là $(u+1, r)$.

Theo công thức tính của cây đoạn $(l, r)$ như đề, nếu $u$ là đỉnh gốc của cây, thì ta có thể hiểu nôm na giá trị của cây là giá trị lớn nhất của một trong ba trường hợp sau:

$s_u = c_u + \Sigma w_v = c_u + (\Sigma w - w_u) = \Sigma w + (c_u - w_u)$ (với $\Sigma w$ là tổng các $w$ của các đỉnh từ $l$ tới $r$).
Giá trị của cây con trái
Giá trị của cây con phải.

Gọi $f(l, r)$ là giá trị nhỏ nhất có thể đạt được của cây đoạn $(l, r)$

Với mỗi cây đoạn $(l, r)$ như vậy, ta lần lượt thử từng đỉnh $u$ làm gốc của cây. Khi đó, ta có công thức:
$$f(l, r) = \max_{l \le u \le r} \begin{cases} s_u = (c_u - w_u) + \Sigma w\\ f(l, u-1)\\ f(u+1, r) \end{cases} (\Sigma w = w_l + w_{l+1} + \dots + w_r).$$

Khi đó, ta đáp án của chúng ta chính là $f(1, n)$.

Cách chọn gốc và dựng cây này đảm bảo tổng giá trị của mỗi cây con sẽ là tối thiểu.

Tuy nhiên, đề bài chỉ yêu cầu giá trị của mỗi cây con không quá $\lim = f(1, n)$, hơn nữa là dãy tiền thứ tự của cây phải lớn nhất. Vì vậy chúng ta cần phải dựng cây lại từ đầu.

Xét cây $(l, r)$ bất kỳ, bắt đầu từ cây $(1, n)$. Ta sẽ lần lượt thử từng đỉnh $u$ làm gốc theo thứ tự $r \rightarrow l$, và ngay khi giá trị của cây gốc $u$ đoạn $(l, r)$ không vượt quá $\lim$ thì ta kết luận luôn đó là gốc mà chúng ta cần tìm, rồi ngay lập tức duyệt sang cây $(l, u-1)$ rồi tới $(u+1, r)$.

Độ phức tạp: $\mathcal{O}\left(2^n\right)$

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3005;
const long long INF = 1e18;

int numNode;
int weight[MAX_N], value[MAX_N];
long long prefixSum[MAX_N];

long long cal(int left, int right) {
    if (left > right) {
        return 0;
    }
    if (left == right) {
        return weight[left];
    }

    long long sum = prefixSum[right] - prefixSum[left - 1];
    long long result = INF;
    for (int root = right; root >= left; root--) {
        result = min(result, max({weight[root] + sum - value[root], cal(left, root - 1), cal(root + 1, right)}));
    }
    return result;
}

void buildTree(int left, int right, long long limit) {
    long long sum = prefixSum[right] - prefixSum[left - 1];
    for (int root = right; root >= left; root--) {
        long long cur = max({weight[root] + sum - value[root], cal(left, root - 1), cal(root + 1, right)});
        if (cur <= limit) {
            cout << root << ' ';
            buildTree(left, root - 1, limit);
            buildTree(root + 1, right, limit);
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    freopen("QBST.inp", "r", stdin);
    freopen("QBST.out", "w", stdout);

    cin >> numNode;
    for (int i = 1; i <= numNode; i++) {
        cin >> weight[i];
    }
    for (int i = 1; i <= numNode; i++) {
        cin >> value[i];
    }

    for (int i = 1; i <= numNode; i++) {
        prefixSum[i] = prefixSum[i - 1] + value[i];
    }

    long long answer = cal(1, numNode);

    cout << answer << '\n';
    buildTree(1, numNode, answer);

    return 0;
}

Subtask $2$ ($20\%$ số điểm): $n \leq 4 \times 10^2$.

Tutorial

Ta cải tiến subtask 1 bằng cách sử dụng kỹ thuật đệ quy có nhớ để không phải tính lại giá trị $f(l, r)$ nhiều lần.
Độ phức tạp: $\mathcal{O}\left(n^2\right)$

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3005;
const long long INF = 1e18;

int numNode;
int weight[MAX_N], value[MAX_N];
long long prefixSum[MAX_N];

long long dp[MAX_N][MAX_N];

long long cal(int left, int right) {
    if (dp[left][right] > 0) {
        return dp[left][right];
    }
    if (left > right) {
        return 0;
    }
    if (left == right) {
        return weight[left];
    }

    long long sum = prefixSum[right] - prefixSum[left - 1];
    long long result = INF;
    for (int root = right; root >= left; root--) {
        result = min(result, max({weight[root] + sum - value[root], cal(left, root - 1), cal(root + 1, right)}));
    }
    dp[left][right] = result;
    return result;
}

void buildTree(int left, int right, long long limit) {
    long long sum = prefixSum[right] - prefixSum[left - 1];
    for (int root = right; root >= left; root--) {
        long long cur = max({weight[root] + sum - value[root], cal(left, root - 1), cal(root + 1, right)});
        if (cur <= limit) {
            cout << root << ' ';
            buildTree(left, root - 1, limit);
            buildTree(root + 1, right, limit);
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    freopen("QBST.inp", "r", stdin);
    freopen("QBST.out", "w", stdout);

    cin >> numNode;
    for (int i = 1; i <= numNode; i++) {
        cin >> weight[i];
    }
    for (int i = 1; i <= numNode; i++) {
        cin >> value[i];
    }

    for (int i = 1; i <= numNode; i++) {
        prefixSum[i] = prefixSum[i - 1] + value[i];
    }

    long long answer = cal(1, numNode);

    cout << answer << '\n';
    buildTree(1, numNode, answer);

    return 0;
}

Subtask $3$ ($20\%$ số điểm): $n \leq 3 \times 10^3$.

Tutorial

Nhận xét: Với một cây bất kỳ, nếu ta thay gốc từ đỉnh $u$ sang đỉnh $v$, thì chỉ có $s_u$ và $s_v$ bị thay đổi giá trị.

Nhận thấy công thức của $s_u = \Sigma w + (c_u - w_u)$ có cụm $(c_u - w_u)$ phụ thuộc vào $u$.
Sau khi thử nghiệm, nếu có hai đỉnh $u, v \ (l \le u,v \le r)$ sao cho $c_u - w_u < c_v - w_v$, thì việc đưa đỉnh $u$ lên làm gốc sẽ cho giá trị của cây nhỏ hơn là đưa đỉnh $v$ làm gốc.

Chứng minh: Giả sử dựng cây gốc $v$, gọi $s'_u, s'_v$ là giá trị $s$ mới sau khi thay đổi sang gốc $u$. Dễ dàng nhận thấy $s'_u < s_v$ (vì $c_u - v_u < c_v - w_v$) và $s'_v < s_v$ (vì đỉnh $v$ làm gốc của cây nhỏ hơn). Vì vậy, chắc chắn giá trị của cây sẽ giảm. ($a, b < c$ thì dù $c > d$ hay $c < d$, $\max(a, b) < \max(c, d$).

Vì thế, để tính $f(l, r)$, chúng ta luôn chọn đỉnh $u$ có $c_u - w_u$ nhỏ nhất.
Còn để dựng cây thỏa mãn đề, ta sẽ chọn đỉnh có chỉ số lớn nhất thỏa mãn $s_u \le f(1, n)$.

Với một đoạn $(l, r)$ bất kỳ, điểm gốc kỳ vọng của cây sẽ nằm quanh vị trí chính giữa đoạn, tách đoạn ra làm đôi.
Vì vậy, độ cao kỳ vọng của cây đáp án sẽ vào khoảng $\log n$, dẫn tới việc dù bạn tìm $c-w$ nhỏ nhất bằng một vòng for, độ phức tạp trung bình của bài này vẫn sẽ là $\mathcal{O}(n\log n)$.
Tuy nhiên, độ phức tạp trong trường hợp tệ nhất vẫn là $\mathcal{O}(n^2)$, nếu điểm gốc nằm gần $l$ hơn $r$.

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;
const long long INF = 1e18;

int n;
int weight[MAX_N], value[MAX_N];
long long prefixSum[MAX_N];

long long dfs(int left, int right) {
    if (left > right) {
        return 0;
    }
    long long answer = INF;
    int root = 0;
    for (int i = right; i >= left; i--) {
        long long cur = prefixSum[right] - prefixSum[left - 1] + weight[i] - value[i];
        if (cur < answer) {
            answer = cur;
            root = i;
        }
    }
    return max({answer, dfs(left, root - 1), dfs(root + 1, right)});
}

void buildTree(int left, int right, long long limit) {
    if (left > right) {
        return;
    }
    for (int root = right; root >= left; root--) {
        long long cur = prefixSum[right] - prefixSum[left - 1] + weight[root] - value[root];
        if (cur <= limit) {
            cout << root << ' ';
            buildTree(left, root - 1, limit);
            buildTree(root + 1, right, limit);
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    freopen("QBST.inp", "r", stdin);
    freopen("QBST.out", "w", stdout);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> weight[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> value[i];
    }

    for (int i = 1; i <= n; i++) {
        prefixSum[i] = prefixSum[i - 1] + value[i];
    }
    long long answer = dfs(1, n);

    cout << answer << '\n';
    buildTree(1, n, answer);

    return 0;
}

Subtask $4$ ($40\%$ số điểm): Không có ràng buộc gì thêm.

Tutorial

Ta có: $s_u = c_u - w_u + \Sigma w \le f(1, n) \Rightarrow c_u - w_u \le f(1, n) - \Sigma w$.

Nhận thấy bài toán gồm 2 truy vấn, một truy vấn tìm $c_u - w_u$ nhỏ nhất trong đoạn, và một truy vấn tìm vị trí $u$ lớn nhất trong đoạn $(l, r)$ sao cho $c_u - w_u \le f(1, n) - \Sigma w$.
Nên để cải tiến, ta có thể dùng Segment Tree hoặc Sparse Table để xử lý truy vấn. Ở đây chúng ta sẽ dùng Segment Tree.

Với mỗi node quản lý đoạn $(l, r)$ của cây, ta lưu $\min_u c_u - w_u$ của đoạn.
Khi đó, việc tìm $c_u - w_u$ nhỏ nhất (1), và tìm $u$ lớn nhất sao cho $c_u - w_u$ không quá giới hạn $X = f(1, n) - \Sigma w$ cho trước(2) đều đơn giản, vì đây là những bài toán kinh điển.

Cụ thể lời giải truy vấn (2): Ta xuất phát từ gốc của cây Segment Tree, nếu con phải có $\min \le X$ thì chuyển sang con phải (vì ta cần $u$ lớn nhất), ngược lại thì đi sang con trái, cho tới khi đến node lá cuối cùng.

Độ phức tạp lúc này sẽ là

Trung bình: $\mathcal{O}(n \log \log n)$
Tệ nhất: $\mathcal{O}(n \log n)$

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;
const int LOG = 17;

int numNode;
int weight[MAX_N], value[MAX_N];
long long prefixSum[MAX_N];
pair<int, int> sparseTable[LOG][MAX_N];
pair<int, int> a[MAX_N];
int log_2[MAX_N];

int getm(int left, int right) {
    int level = log_2[right - left + 1];
    return min(sparseTable[level][left], sparseTable[level][right - (1 << level) + 1]).second;
}

long long ans = 0;
void dfs(int left, int right) {
    int node = getm(left, right);
    ans = max(ans, weight[node] + prefixSum[right] - prefixSum[left - 1]);
    if (left != node) dfs(left, node - 1);
    if (node != right) dfs(node + 1, right);
}

void buildTree(int left, int right) {
    int node = right + 1;
    long long lim = ans - (prefixSum[right] - prefixSum[left - 1]);
    for (int i = 16; i >= 0; i--) {
        if (node > (1 << i) && sparseTable[i][node - (1 << i)].first > lim) {
            node -= (1 << i);
        }
    }
    node--;
    cout << node << ' ';
    if (left != node) {
        buildTree(left, node - 1);
    }
    if (node != right) {
        buildTree(node + 1, right);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    freopen("QBST.inp", "r", stdin);
    freopen("QBST.out", "w", stdout);

    cin >> numNode;
    for (int i = 2; i <= numNode; i++) {
        log_2[i] = log_2[i >> 1] + 1;
    }

    for (int i = 1; i <= numNode; i++) {
        cin >> weight[i];
    }
    for (int i = 1; i <= numNode; i++) {
        cin >> value[i];
    }

    for (int i = 1; i <= numNode; i++) {
        weight[i] -= value[i];
        prefixSum[i] = prefixSum[i - 1] + value[i];
        sparseTable[0][i] = pair<int, int>(weight[i], i);
    }
    for (int level = 1; level < LOG; level++) {
        for (int i = 1; i <= numNode - (1 << (level - 1)); i++) {
            sparseTable[level][i] = min(sparseTable[level - 1][i], sparseTable[level - 1][i + (1 << (level - 1))]);
        }
    }

    dfs(1, numNode);

    cout << ans << '\n';
    buildTree(1, numNode);

    return 0;
}

Bình luận

Tải bình luận...

Không có bình luận nào.

Hướng dẫn cho LQDOJ CUP 2022 - Round 3 - QBST

Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20\).

Subtask \(2\) (\(20\%\) số điểm): \(n \leq 4 \times 10^2\).

Subtask \(3\) (\(20\%\) số điểm): \(n \leq 3 \times 10^3\).

Subtask \(4\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Bình luận