Editorial for LQDOJ CUP 2022 - Final Round - XMAS

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

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

Tutorial

Đặt \(dp(l,r) =\) true / false tương ứng với việc có thể xóa hết toàn bộ số trong đoạn \([l, r]\) không?
Hai trường hợp:

\(a[l] + a[r] = k\), nếu \(dp(l + 1, r - 1)\) đúng thì \(dp(l, r)\) cũng đúng
Nếu tồn tại \(i : l \leq i < r\) mà \(dp(l, i)\) và \(dp(i + 1, r)\) đều đúng thì \(dp(l, r)\) là đúng.

Độ phức tạp: \(\mathcal{O}(n^{3})\)

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 105;

int n, k, numQuery;
int a[MAX_N];
bool dp[MAX_N][MAX_N];

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

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

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> numQuery;

    for (int i = 1; i < n; i++) {
        dp[i][i + 1] = a[i] + a[i + 1] == k;
    }

    for (int len = 4; len <= n; len += 2) {
        for (int left = 1, right = len; right <= n; left++, right++) {
            dp[left][right] = (a[left] + a[right] == k) && dp[left + 1][right - 1];
            for (int mid = left + 1; mid < right; mid += 2) {
                dp[left][right] |= dp[left][mid] && dp[mid + 1][right];
            }
        }
    }

    while (numQuery--) {
        int left, right;
        cin >> left >> right;
        cout << (dp[left][right] ? "YES\n" : "NO\n");
    }

    return 0;
}

Subtask \(2\) (\(30\%\) số điểm): \(n \leq 5 \times 10^{5}, q \leq 10\)

Tutorial

Để giải subtask này, ta cần các nhận xét sau:

nếu có 2 lựa chọn xóa bên trái trước, hoặc xóa bên phải trước, \([k - a, a, k-a]\), có thể xóa cặp nào cũng được vì mảng tạo thành sau đó là như nhau.
nếu gặp bất kì cặp nào xóa được thì cứ xóa trước.

Do đó, với mỗi truy vấn, ta có thể mô phỏng lại quá trình xóa trong \(O(n)\)
Độ phức tạp: \(\mathcal{O}(n \times q)\)

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 500005;

int n, k, numQuery;
int a[MAX_N];

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

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

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> numQuery;

    while (numQuery--) {
        int left, right;
        cin >> left >> right;
        stack<int> st;

        for (int i = left; i <= right; i++) {
            if (st.empty()) {
                st.push(a[i]);
            } else if (st.top() + a[i] != k) {
                st.push(a[i]);
            } else {
                st.pop();
            }
        }

        cout << (st.empty() ? "YES\n" : "NO\n");
    }

    return 0;
}

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

Tutorial

Đặt \(p[i]\) là vị trí gần \(i\) nhất, \(p[i]<i\) và \(a[p[i]] + a[i] = k\), sao cho đoạn con \(p[i] \ldots i\) có thể xóa được.
Nếu không tồn tại vị trí như vậy, quy ước \(p[i]\) là một giá trị đặc biệt nào đó (\(0,-1,\dots\))
Dùng các \(p\) trước đó để tính \(p\) hiện tại:

đặt \(p[i] = i - 1\)
chừng nào mà tổng \(a[p[i]] + a[i] \neq k\), gán \(p[i] = p[p[i]] - 1\)

Khi truy vấn: ta dùng mảng \(p\) để "nhảy" về theo quy tắc như trên.
Các thao tác này có thể tăng tốc bằng bảng thưa.
Độ phức tạp: \(\mathcal{O}((q+n)\log_{2} n)\)

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 500005;

int n, k, a[MAX_N], p[MAX_N], ip[MAX_N];
int numQuery, l[MAX_N], r[MAX_N];
bool ans[MAX_N];
vector<int> ids[MAX_N];
map<int, int> mark[MAX_N];
map<int, bool> reach[MAX_N];

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

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

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> numQuery;
    for (int i = 1; i <= numQuery; i++) {
        cin >> l[i] >> r[i];
        ids[r[i]].push_back(i);
    }

    a[0] = -1;
    reach[0][0] = true;
    for (int i = 1; i <= n; i++) {
        p[i] = mark[i - 1][k - a[i]];
        ip[p[i]] = i;
        if (p[i]) {
            swap(mark[i], mark[p[i] - 1]);
            swap(reach[i], reach[p[i] - 1]);
        }
        mark[i][a[i]] = i;
        reach[i][i] = true;
        for (int id : ids[i]) {
            ans[id] = reach[r[id]][l[id] - 1];
        }
    }

    for (int i = 1; i <= numQuery; i++) {
        cout << (ans[i] ? "YES\n" : "NO\n");
    }

    return 0;
}

Comments

There are no comments at the moment.