Hướng dẫn cho LQDOJ CUP 2022 - Round 8 - BOUNCE2D

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: ldn694

Subtask \(1\) (\(15\%\) số điểm): \(W \leq 10, H = 0\), \(n, m \leq 10\).

Tutorial

Với \(W\) đủ nhỏ, ta có thể quay lui tất cả các cách di chuyển.
Độ phức tạp: \(\mathcal{O}(2^W)\)

Solution
C++
#include <bits/stdc++.h>

using namespace std;

const long long MAX_N = 1005;
const long long INF = (long long)1e18 + 10;
const long long LOG = 10;

long long width, height, numPump, numNail;
long long a[MAX_N][MAX_N];
long long result = INF;

void backtrack(long long x, long long step, long long sum) {
    if (x == width) {
        result = min(result, sum);
        return;
    }
    if (x + (1LL << step) > width) {
        return;
    }

    long long nextX = x + (1 << step);
    if (a[nextX][0] == 2) {  // is nail
        backtrack(nextX, 0, sum + 1);
        return;
    }
    backtrack(nextX, step, sum + 1);
    if (a[nextX][0] == 1) {  // is pump
        backtrack(nextX, step + 1, sum + 1);
    }
}

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

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

    cin >> width >> height >> numPump >> numNail;
    for (int i = 1; i <= numPump; i++) {
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;
    }
    for (int i = 1; i <= numNail; i++) {
        int x, y;
        cin >> x >> y;
        a[x][y] = 2;
    }

    backtrack(0, 0, 0);

    cout << (result == INF ? -1 : result);

    return 0;
}

Subtask \(2\) (\(20\%\) số điểm): \(W, H \leq 500\).

Tutorial

Ở subtask này, ta có thể sử dụng quy hoạch động như sau: Gọi \(\text{dp}[x][y][step][2]\) là số bước nhảy ít nhất để nhảy tới tọa độ \((x,y)\), đang có bước nhảy là \(\text{step}\) và có hướng \(0/1\) với hướng 0 là đi sang phải và hướng \(1\) là đi lên trên.
Ta nhận xét rằng bước nhảy của chúng ta luôn luôn có dạng là lũy thừa cơ số \(2\), giả sử \(\text{step}=2^k\), ta có thể chuyển trạng thái quy hoạch động của chúng ta trở thành \(\text{dp}[x][y][k][2]\). Lúc này ta chỉ cần cập nhật mảng quy hoạch động giống với mô tả của đề là được.
Độ phức tạp: \(\mathcal{O}(W \times H \times \log_2(W + H))\)

Solution
C++
#include <bits/stdc++.h>

using namespace std;

const long long MAX_N = 1005;
const long long INF = (long long)1e18 + 10;
const long long LOG = 10;

long long width, height, numPump, numNail;
long long a[MAX_N][MAX_N], dp[MAX_N][MAX_N][11][2];

bool minimize(long long &x, long long y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

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

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

    cin >> width >> height >> numPump >> numNail;

    for (int x = 0; x <= width; x++) {
        for (int y = 0; y <= height; y++) {
            a[x][y] = 0;
            for (int sz = 0; sz <= LOG; sz++) {
                for (int dir = 0; dir <= 1; dir++) {
                    dp[x][y][sz][dir] = INF;
                }
            }
        }
    }
    for (int dir = 0; dir <= 1; dir++) {
        dp[0][0][0][dir] = 0;
    }

    for (int i = 1; i <= numPump; i++) {
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;
    }
    for (int i = 1; i <= numNail; i++) {
        int x, y;
        cin >> x >> y;
        a[x][y] = 2;
    }

    for (int x = 0; x <= width; x++) {
        for (int y = 0; y <= height; y++) {
            for (int sz = 0; sz <= LOG; sz++) {
                for (int dir = 0; dir <= 1; dir++) {
                    long long nextX = (dir == 0 ? x + (1LL << sz) : x), nextY = (dir == 1 ? y + (1LL << sz) : y);
                    if (nextX <= width && nextY <= height) {
                        if (a[nextX][nextY] == 2) {  // is nail
                            for (int nxtDir = 0; nxtDir <= 1; nxtDir++) {
                                minimize(dp[nextX][nextY][0][nxtDir], dp[x][y][sz][dir] + 1);
                            }
                            continue;
                        }
                        if (a[nextX][nextY] == 1) {  // is pump
                            for (int nxtDir = 0; nxtDir <= 1; nxtDir++) {
                                minimize(dp[nextX][nextY][sz][nxtDir], dp[x][y][sz][dir] + 1);
                                if (sz < LOG) {
                                    minimize(dp[nextX][nextY][sz + 1][nxtDir], dp[x][y][sz][dir] + 1);
                                }
                            }
                            continue;
                        }
                        minimize(dp[nextX][nextY][sz][dir], dp[x][y][sz][dir] + 1);
                    }
                }
            }
        }
    }

    long long res = INF;
    for (int sz = 0; sz <= LOG; sz++) {
        for (int dir = 0; dir <= 1; dir++) {
            minimize(res, dp[width][height][sz][dir]);
        }
    }

    cout << (res == INF ? -1 : res);

    return 0;
}

Subtask \(3\) (\(25\%\) số điểm): \(n, m \leq 500\).

Tutorial

Từ subtask này trở đi, \(W,H\) có thể lên tới \(10^9\), do đó việc lưu mảng \(\text{dp}\) như subtask 2 là không thể. Ta cần phải tìm cách thay đổi trạng thái quy hoạch động sang một dạng nào đấy khác mà có thể lưu được.
Quan sát đoạn code của subtask 2, ta có thể nhận xét rằng: Chỉ những tọa độ đặc biệt thì việc cập nhật mảng quy hoạch động mới phức tạp, trong khi đó ở những tọa độ không chứa bơm hay đinh, nó chỉ cập nhật duy nhất vị trí cách nó một khoảng \(2^k\). Lợi dụng tính chất này, ta có thể thay đổi trạng thái quy hoạch động \(\text{dp}[x][y][k][2]\) ban đầu trở thành \(\text{dp}[i][k]\), là số bước nhảy ít nhất để nhảy tới tọa độ đặc biệt thứ \(i\) và có bước nhảy hiện tại là \(2^k\). Lưu ý tọa độ \((0,0)\) và \((W,H)\) cũng là hai tọa độ đặc biệt. Khi duyệt qua các tọa độ đặc biệt \(i\), ta sẽ duyệt theo thứ tự tăng dần theo \(x\) trước theo \(y\) sau để đảm bảo các trạng thái trước được tính trước.
Vì tại \(i\) ta chỉ có hai hướng đi là lên trên hoặc sang phải, ta có nhận xét rằng chỉ cần cập nhật \(j_0\) là tọa độ gần nhất ở bên phải và \(j_1\) là tọa độ gần nhất ở phía trên của \(i\) với các bước đi độ dài \(2^k\) là được. Bởi vì việc cập nhật \(j'\) nào đó khác \(j_0\) và \(j_1\) từ \(i\) sẽ là vô nghĩa khi muốn từ \(i\) tới \(j'\), ta cũng phải đi qua \(j_0\) hoặc \(j_1\). Khi ấy bài toán quay về việc tìm \(j_0\) và \(j_1\) với mỗi \(i\) và \(k\).
Ở subtask này, vì \(n,m\) đủ nhỏ, ta có thể đơn thuần xét tất cả giá trị \(j\) để tìm \(j_0\) và \(j_1\) thỏa mãn với mỗi \(i\) và \(k\).
Độ phức tạp: \(\mathcal{O}((n + m)^2 \times \log_2(W + H))\)

Solution
C++
#include <bits/stdc++.h>

using namespace std;

const long long MAX_N = 100005;
const long long INF = (long long)1e18 + 10;
const long long LOG = 29;

struct Point {
    long long x, y, id, state;
    Point(long long _x = 0, long long _y = 0, long long _id = 0, long long _state = 0) : x(_x), y(_y), id(_id), state(_state){};
    // state = 0 nail
    // state = 1 pump
};

bool cmpX(const Point &A, const Point &B) {
    return (A.x == B.x) ? A.y < B.y : A.x < B.x;
}

bool cmpY(const Point &A, const Point &B) {
    return (A.y == B.y) ? A.x < B.x : A.y < B.y;
}

bool cmpId(const Point &A, const Point &B) {
    return A.id < B.id;
}

bool minimize(long long &x, long long y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

long long width, height, numPump, numNail, n;
long long nextPos[MAX_N * 2][LOG + 1][2], pre[MAX_N * 2], dp[MAX_N * 2][LOG + 1], updateId[MAX_N * 2];
Point a[MAX_N * 2];

long long dist(const Point &A, const Point &B, long long step) {
    return (abs(A.x - B.x) + abs(A.y - B.y)) / step;
}

void findNextPos(long long dir) {
    for (int i = 0; i <= n; i++) {
        for (int sz = 0; sz <= LOG; sz++) {
            nextPos[i][sz][dir] = -1;
        }
    }
    for (int i = 0; i <= n; i++) {
        for (int sz = 0; sz <= LOG; sz++) {
            long long nextJ = -1, mi = INF;
            long long samePara = (dir == 0 ? a[i].y : a[i].x);
            long long diffPara = (dir == 0 ? a[i].x : a[i].y);
            for (int j = 0; j <= n; j++) {
                if (i == j) {
                    continue;
                }
                long long nextSamePara = (dir == 0 ? a[j].y : a[j].x);
                long long nextDiffPara = (dir == 0 ? a[j].x : a[j].y);
                if (samePara == nextSamePara && diffPara <= nextDiffPara && (nextDiffPara - diffPara) % (1 << sz) == 0) {
                    if (minimize(mi, nextDiffPara - diffPara)) {
                        nextJ = j;
                    }
                }
            }
            nextPos[i][sz][dir] = nextJ;
        }
    }
}

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

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

    cin >> width >> height >> numPump >> numNail;

    a[0] = Point(0, 0, 0, 0);
    for (int i = 1; i <= numPump; i++) {
        int x, y;
        cin >> x >> y;
        a[++n] = Point(x, y, i, 1);
    }
    for (int i = 1; i <= numNail; i++) {
        int x, y;
        cin >> x >> y;
        a[++n] = Point(x, y, i + numPump, 0);
    }
    a[++n] = Point(width, height, numPump + numNail + 1, 0);

    for (int dir = 0; dir <= 1; dir++) {
        findNextPos(dir);
    }

    sort(a, a + n + 1, cmpX);
    for (int i = 0; i <= n; i++) {
        updateId[i] = a[i].id;
    }
    sort(a, a + n + 1, cmpId);
    for (int i = 0; i <= n; i++) {
        for (int sz = 0; sz <= LOG; sz++) {
            dp[i][sz] = INF;
        }
    }

    dp[0][0] = 0;
    for (int i = 0; i <= n; i++) {
        long long pos = updateId[i];
        for (int sz = 0; sz <= LOG; sz++) {
            if (dp[pos][sz] != INF) {
                for (int dir = 0; dir <= 1; dir++) {
                    long long nxt = nextPos[pos][sz][dir];
                    long long cost = dist(a[pos], a[nxt], (1LL << sz));
                    if (a[nxt].state == 0) {  // is nail
                        minimize(dp[nxt][0], dp[pos][sz] + cost);
                        continue;
                    }
                    if (a[nxt].state == 1) {  // is pump
                        minimize(dp[nxt][sz], dp[pos][sz] + cost);
                        if (sz < LOG) minimize(dp[nxt][sz + 1], dp[pos][sz] + cost);
                        continue;
                    }
                    minimize(dp[nxt][sz], dp[pos][sz] + cost);
                }
            }
        }
    }

    long long res = INF;
    for (int sz = 0; sz <= LOG; sz++) {
        minimize(res, dp[n][sz]);
    }

    cout << (res == INF ? -1 : res);

    return 0;
}

Subtask \(4\) (\(20\%\) số điểm): \(H = 0\).

Tutorial

Khi \(n,m\) lớn, ta không thể đơn thuần duyệt hết tất cả \(j\) để tìm \(j_0\) và \(j_1\) nữa. Vì \(H=0\), ta nhận xét rằng từ \(i\) có thể nhảy tới \(j\) với bước nhảy \(2^k\) \(\Leftrightarrow\) \(x_i \text{ mod } 2^k = x_j \text{ mod } 2^k\). Để tìm \(j_0\) cho \(i\) và \(k\), ta sẽ tiền xử lý như sau:
Với mỗi \(k\), ta tạo mảng \(a_i = x_i \text{ mod } 2^k\), khi đó điều kiện ở trên sẽ tương đương \(a_i = a_j\). Để tìm \(j>i\) nhỏ nhất mà \(a_i=a_j\), ta chỉ cần sắp xếp tăng dần mảng \(a\), sau đó duyệt từ cuối về đầu và sử dụng một cấu trúc dữ liệu hay kỹ thuật nào đó (map/unordered_map/nén số/\(\ldots\)) để đánh dấu lại vị trí mới nhất có giá trị \(v\) là gì.
Độ phức tạp: \(\mathcal{O}((n + m) \times \log_2(n + m) \times \log_2(W))\)

Solution
C++
#include <bits/stdc++.h>

using namespace std;

const long long MAX_N = 100005;
const long long INF = (long long)1e18 + 10;
const long long LOG = 29;

struct Point {
    long long x, y, id, state;
    Point(long long _x = 0, long long _y = 0, long long _id = 0, long long _state = 0) : x(_x), y(_y), id(_id), state(_state){};
    // state = 0 nail
    // state = 1 pump
};

bool cmpX(const Point &A, const Point &B) {
    return (A.x == B.x) ? A.y < B.y : A.x < B.x;
}

bool cmpY(const Point &A, const Point &B) {
    return (A.y == B.y) ? A.x < B.x : A.y < B.y;
}

bool cmpId(const Point &A, const Point &B) {
    return A.id < B.id;
}

bool minimize(long long &x, long long y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

long long width, height, numPump, numNail, n;
long long nextPos[MAX_N * 2][LOG + 1], pre[MAX_N * 2], dp[MAX_N * 2][LOG + 1], updateId[MAX_N * 2];
Point a[MAX_N * 2];

long long dist(const Point &A, const Point &B, long long step) {
    return (abs(A.x - B.x) + abs(A.y - B.y)) / step;
}

void findNextPos() {
    sort(a, a + n + 1, cmpX);
    for (int sz = 0; sz <= LOG; sz++) {
        long long mod = (1LL << sz);
        vector<long long> val;
        for (int i = 0; i <= n; i++) {
            val.push_back(a[i].x % mod);
        }
        sort(val.begin(), val.end());
        val.resize(unique(val.begin(), val.end()) - val.begin());
        for (int i = 1; i <= (int)val.size(); i++) {
            pre[i] = -1;
        }
        for (int i = n; i >= 0; i--) {
            long long compressed_val = lower_bound(val.begin(), val.end(), a[i].x % mod) - val.begin() + 1;
            nextPos[a[i].id][sz] = pre[compressed_val];
            pre[compressed_val] = a[i].id;
        }
    }
}

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

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

    cin >> width >> height >> numPump >> numNail;

    a[0] = Point(0, 0, 0, 0);
    for (int i = 1; i <= numPump; i++) {
        int x, y;
        cin >> x >> y;
        a[++n] = Point(x, y, i, 1);
    }
    for (int i = 1; i <= numNail; i++) {
        int x, y;
        cin >> x >> y;
        a[++n] = Point(x, y, i + numPump, 0);
    }
    a[++n] = Point(width, height, numPump + numNail + 1, 0);

    findNextPos();
    sort(a, a + n + 1, cmpX);
    for (int i = 0; i <= n; i++) {
        updateId[i] = a[i].id;
    }
    sort(a, a + n + 1, cmpId);
    for (int i = 0; i <= n; i++) {
        for (int sz = 0; sz <= LOG; sz++) {
            dp[i][sz] = INF;
        }
    }

    dp[0][0] = 0;
    for (int i = 0; i <= n; i++) {
        long long pos = updateId[i];
        for (int sz = 0; sz <= LOG; sz++) {
            if (dp[pos][sz] != INF) {
                long long nxt = nextPos[pos][sz];
                long long cost = dist(a[pos], a[nxt], (1LL << sz));
                if (a[nxt].state == 0) {  // is nail
                    minimize(dp[nxt][0], dp[pos][sz] + cost);
                    continue;
                }
                if (a[nxt].state == 1) {  // is pump
                    minimize(dp[nxt][sz], dp[pos][sz] + cost);
                    if (sz < LOG) minimize(dp[nxt][sz + 1], dp[pos][sz] + cost);
                    continue;
                }
                minimize(dp[nxt][sz], dp[pos][sz] + cost);
            }
        }
    }

    long long res = INF;
    for (int sz = 0; sz <= LOG; sz++) {
        minimize(res, dp[n][sz]);
    }

    cout << (res == INF ? -1 : res);

    return 0;
}

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

Tutorial

Ý tưởng subtask 5 cũng sẽ tương tự subtask 4, chỉ khác rằng ta sẽ phải làm 2 lần. Lần thứ nhất, ta sắp xếp tăng dần theo \(x\) trước, theo \(y\) sau. Lúc này, ta có thể nhóm các tọa độ đặc biệt có cùng \(x\) về một nhóm. Khi ấy với mỗi \(i\) và \(k\) thì \(j_1\) của nó chắc chắn sẽ nằm cùng nhóm. Ta chỉ cần sử dụng thuật toán trong subtask 4 cho một nhóm đó là xong. Lần thứ hai cũng sẽ tương tự, chỉ khác là sắp xếp tăng dần theo \(y\) trước, theo \(x\) sau. Sau lần thứ hai ta sẽ tìm được \(j_0\) cho mỗi \(i\) và \(k\).
Độ phức tạp: \(\mathcal{O}((n + m) \times \log_2(n + m) \times \log_2(W + H))\)

Solution
C++
#include <bits/stdc++.h>

using namespace std;

const long long MAX_N = 1e5 + 10;
const long long INF = (long long)1e18 + 10;
const long long LOG = 29;

struct Point {
    long long x, y, id, state;
    Point(long long _x = 0, long long _y = 0, long long _id = 0, long long _state = 0) : x(_x), y(_y), id(_id), state(_state){};
    // state = 0 nail
    // state = 1 pump
};

bool cmpX(const Point &A, const Point &B) {
    return (A.x == B.x) ? A.y < B.y : A.x < B.x;
}

bool cmpY(const Point &A, const Point &B) {
    return (A.y == B.y) ? A.x < B.x : A.y < B.y;
}

bool cmpId(const Point &A, const Point &B) {
    return A.id < B.id;
}

bool minimize(long long &x, long long y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

long long width, height, numPump, numNail, n;
long long nextPos[MAX_N * 2][LOG + 1][2], pre[MAX_N * 2], dp[MAX_N * 2][LOG + 1], updateId[MAX_N * 2];
Point a[MAX_N * 2];

long long dist(const Point &A, const Point &B, long long step) {
    return (abs(A.x - B.x) + abs(A.y - B.y)) / step;
}

void findNextPos(long long dir) {
    if (dir == 0) {  // horizontal
        sort(a, a + n + 1, cmpY);
    } else {  // vertical
        sort(a, a + n + 1, cmpX);
    }
    long long L = 0;
    while (L <= n) {
        long long R = L;
        while (R <= n && (dir == 0 ? a[R].y == a[L].y : a[R].x == a[L].x)) {
            R++;
        }
        R--;
        for (int sz = 0; sz <= LOG; sz++) {
            long long mod = (1LL << sz);
            vector<long long> val;
            for (int i = L; i <= R; i++) {
                val.push_back(dir == 0 ? a[i].x % mod : a[i].y % mod);
            }
            sort(val.begin(), val.end());
            val.resize(unique(val.begin(), val.end()) - val.begin());
            for (int i = 1; i <= (int)val.size(); i++) {
                pre[i] = -1;
            }
            for (int i = R; i >= L; i--) {
                long long compressed_val = lower_bound(val.begin(), val.end(), dir == 0 ? a[i].x % mod : a[i].y % mod) - val.begin() + 1;
                nextPos[a[i].id][sz][dir] = pre[compressed_val];
                pre[compressed_val] = a[i].id;
            }
        }
        L = R + 1;
    }
}

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

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

    cin >> width >> height >> numPump >> numNail;

    a[0] = Point(0, 0, 0, 0);
    for (int i = 1; i <= numPump; i++) {
        int x, y;
        cin >> x >> y;
        a[++n] = Point(x, y, i, 1);
    }
    for (int i = 1; i <= numNail; i++) {
        int x, y;
        cin >> x >> y;
        a[++n] = Point(x, y, i + numPump, 0);
    }
    a[++n] = Point(width, height, numPump + numNail + 1, 0);

    for (int dir = 0; dir <= 1; dir++) {
        findNextPos(dir);
    }
    sort(a, a + n + 1, cmpX);
    for (int i = 0; i <= n; i++) {
        updateId[i] = a[i].id;
    }
    sort(a, a + n + 1, cmpId);
    for (int i = 0; i <= n; i++) {
        for (int sz = 0; sz <= LOG; sz++) {
            dp[i][sz] = INF;
        }
    }

    dp[0][0] = 0;
    for (int i = 0; i <= n; i++) {
        long long pos = updateId[i];
        for (int sz = 0; sz <= LOG; sz++) {
            if (dp[pos][sz] != INF) {
                for (int dir = 0; dir <= 1; dir++) {
                    long long nxt = nextPos[pos][sz][dir];
                    long long cost = dist(a[pos], a[nxt], (1LL << sz));
                    if (a[nxt].state == 0) {  // is nail
                        minimize(dp[nxt][0], dp[pos][sz] + cost);
                        continue;
                    }
                    if (a[nxt].state == 1) {  // is pump
                        minimize(dp[nxt][sz], dp[pos][sz] + cost);
                        if (sz < LOG) minimize(dp[nxt][sz + 1], dp[pos][sz] + cost);
                        continue;
                    }
                    minimize(dp[nxt][sz], dp[pos][sz] + cost);
                }
            }
        }
    }

    long long res = INF;
    for (int sz = 0; sz <= LOG; sz++) {
        minimize(res, dp[n][sz]);
    }

    cout << (res == INF ? -1 : res);

    return 0;
}

Bình luận

Mới nhất
Tải bình luận...

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