Editorial for ptit008: Chuyến đi từ thiện

Hiểu bài toán

Xác định độ cao tối đa có thể đạt được của một chuỗi n địa điểm (từ 1 đến n), trong đó chỉ có m địa điểm biết chính xác độ cao. Các địa điểm còn lại chưa biết nhưng phải thỏa mãn điều kiện: độ chênh lệch độ cao giữa hai địa điểm kề nhau không vượt quá 1. Nếu có mâu thuẫn giữa các địa điểm đã biết (ví dụ chênh lệch lớn hơn khoảng cách), đáp án là -1.

Các cách tiếp cận

Cách Tối ưu hóa hình học (Phương pháp thẳng)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    long long n, m;
    cin >> n >> m;
    vector<pair<long long, long long>> a(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i].first >> a[i].second;
    }
    sort(a.begin(), a.end());

    // Kiểm tra mâu thuẫn giữa các điểm đã biết
    for (int i = 0; i < m - 1; i++) {
        long long dist = a[i+1].first - a[i].first;
        long long h_diff = abs(a[i+1].second - a[i].second);
        if (h_diff > dist) {
            cout << -1;
            return 0;
        }
    }

    long long ans = 0;

    // Xử lý đoạn bên trái điểm đầu tiên
    // Dốc lên 1 đơn vị mỗi bước về phía trước -> max tại pos 1 là h0 + (pos0 - 1)
    ans = max(ans, a[0].second + (a[0].first - 1));

    // Xử lý đoạn bên phải điểm cuối cùng
    // Dốc lên 1 đơn vị mỗi bước lùi lại -> max tại pos n là hm + (n - posm)
    ans = max(ans, a[m-1].second + (n - a[m-1].first));

    // Xử lý đoạn giữa các điểm已知
    for (int i = 0; i < m - 1; i++) {
        long long p1 = a[i].first, h1 = a[i].second;
        long long p2 = a[i+1].first, h2 = a[i+1].second;
        long long dist = p2 - p1;
        long long diff = abs(h2 - h1);

        // Công thức tính đỉnh cao nhất trên đoạn thẳng nối 2 điểm
        // Đỉnh nằm ở vị trí nơi xu hướng tăng/giảm đảo chiều
        // Công thức: max(h1, h2) + (dist - diff) / 2
        long long peak = max(h1, h2) + (dist - diff) / 2;
        ans = max(ans, peak);
    }

    cout << ans;
    return 0;
}

• Time Complexity: O(m log m)
• Space Complexity: O(m)

Bài toán có thể biến đổi thành bài toán tìm hàm số f(x) (độ cao tại vị trí x) sao cho f(x) liên tục, |f(x)-f(y)| <= |x-y|. Với các điểm已知 (di, hi), hàm số bị ràng buộc bởi các đường thẳng giới hạn. Đáp án chính là giá trị lớn nhất của hàm số này.

1. Kiểm tra tính khả thi: Duyệt qua các cặp điểm已知 liên tiếp. Nếu |h2 - h1| > (p2 - p1) thì không thể vẽ đường thẳng thỏa mãn dốc <= 1, in -1.

2. Đoạn đầu và đoạn cuối:

   • Đoạn [1, p1]: Để đạt độ cao lớn nhất, ta đi lên 1 đơn vị mỗi bước từ điểm đầu tiên trở về vị trí 1. Độ cao tối đa tại vị trí 1 là h1 + (p1 - 1).
   • Đoạn [pm, n]: Tương tự, đi lên 1 đơn vị mỗi bước từ điểm cuối về vị trí n. Độ cao tối đa tại vị trí n là hm + (n - pm).

3. Đoạn giữa p1 và p2: Hai điểm已知 tạo thành các đường biên dưới dạng hình thang. Đỉnh cao nhất nằm ở giữa, nơi độ dốc thay đổi dấu. Nếu ta nối hai điểm bằng một đường zigzag (lên-xuống tối đa), đỉnh sẽ nằm ở khoảng giữa. Khoảng cách từ điểm cao hơn đến đỉnh là (dist - diff) / 2. Do đó đỉnh cao nhất là max(h1, h2) + (dist - diff) / 2.

Cách tiếp cận này loại bỏ hoàn toàn việc duyệt qua n (có thể lên tới 10^8), chỉ tập trung vào m (<= 10^5) điểm已知.

Cách Khôi phục và Lướt (Tham khảo)

// Pseudocode for approach 2 (Less optimal)
// Chỉ dùng khi n nhỏ, không áp dụng cho n <= 10^8
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> h(n + 1, -1); // -1表示未知
    for (int i = 0; i < m; i++) {
        int d, val;
        cin >> d >> val;
        h[d] = val;
    }

    // Kiểm tra mâu thuẫn
    for(int i=1; i<n; i++) {
        if (h[i] != -1 && h[i+1] != -1) {
            if (abs(h[i] - h[i+1]) > 1) {
                cout << -1; return 0;
            }
        }
    }

    // Khôi phục từ trái sang phải
    for(int i=2; i<=n; i++) {
        if (h[i] == -1) h[i] = max(0LL, h[i-1] - 1);
        else h[i] = min((long long)h[i], max(0LL, h[i-1] - 1));
    }

    // Khôi phục từ phải sang trái
    for(int i=n-1; i>=1; i--) {
        if (h[i] == -1) h[i] = max(0LL, h[i+1] - 1);
        else h[i] = min((long long)h[i], max(0LL, h[i+1] - 1));
    }

    long long ans = 0;
    for(int i=1; i<=n; i++) ans = max(ans, (long long)h[i]);
    cout << ans;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Đây là cách tiếp cận mô phỏng trực tiếp quá trình điền vào các chỗ trống.

1. Khởi tạo mảng độ cao, gán các điểm已知.
2. Duyệt từ trái sang phải: Nếu điểm i chưa biết, ta có thể đặt nó cao nhất là h[i-1] + 1 (nếu muốn leo dốc) hoặc h[i-1] - 1 (nếu đi xuống). Tuy nhiên, để đảm bảo tính hợp lệ với các điểm已知 sau đó, ta thường dùng quy hoạch động: h[i] = min(giá trị已知, max(0, h[i-1]-1)).
3. Duyệt từ phải sang trái và cập nhật lại.
4. Tìm max.

Lưu ý: Code mẫu ở trên là Pseudocode minh họa logic. Với n lên tới 10^8, cách này vượt quá giới hạn bộ nhớ (mảng 10^8 phần tử ~ 400MB) và thời gian chạy. Giải pháp tối ưu (Approach 1) đã chứng minh ta không cần mảng này.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể giải quyết hoàn toàn dựa trên các điểm已知 mà không cần quan tâm đến n (vô cùng lớn).
• Hàm số độ cao có tính chất 'Lipschitz' với hệ số 1, cho phép suy ra các đoạn tối đa giữa các điểm已知.
• Độ cao tối đa trên đoạn thẳng giữa hai điểm (p1, h1) và (p2, h2) là max(h1, h2) + (distance - |h1-h2|) / 2.

Lỗi thường gặp

• Không kiểm tra mâu thuẫn giữa các điểm已知 trước khi tính toán (ví dụ: distance=2 nhưng chênh lệch độ cao=3).
• Quên xử lý đoạn đường bên trái điểm đầu tiên và bên phải điểm cuối cùng.
• Sai lệch đơn vị (Off-by-one error) trong tính toán khoảng cách (ví dụ: pos 2 và pos 5 cách nhau 3 đơn vị).
• Sử dụng biến kiểu int cho các phép tính có thể vượt quá 2^31-1 (n, h_i, và kết quả trung gian đều có thể lên tới 10^8, nên dùng long long).