Tóm tắt đề bài

Cho \(n\) điểm trên một vòng tròn được đánh số từ \(1\) đến \(n\) theo chiều kim đồng hồ. Có \(k\) đoạn dây, đoạn dây thứ \(i\) nối từ điểm \(l_i\) đến \(r_i\) theo chiều kim đồng hồ. Nhiệm vụ của bạn là chọn ra ít đoạn dây nhất sao cho tất cả \(n\) điểm trên vòng tròn đều được phủ bởi ít nhất một đoạn dây. Nếu không thể phủ hết, in ra impossible.

Phân tích

• Tính chất vòng tròn: Một đoạn dây nối từ \(l\) đến \(r\) theo chiều kim đồng hồ có thể đi qua điểm \(n\) rồi quay lại điểm \(1\) (nếu \(l > r\)). Để xử lý cấu trúc vòng tròn, ta có thể "trải phẳng" vòng tròn thành một đoạn thẳng có độ dài \(2n\).
  • Đoạn dây \([l, r]\) với \(l \le r\) sẽ phủ các điểm từ \(l\) đến \(r\). Trong mô hình tuyến tính, nó tương ứng với đoạn \([l, r]\) và \([l+n, r+n]\).
  • Đoạn dây \([l, r]\) với \(l > r\) sẽ phủ các điểm từ \(l\) đến \(n\) và từ \(1\) đến \(r\). Trong mô hình tuyến tính, nó tương ứng với đoạn \([l, r+n]\).
• Chiến thuật tham lam: Để phủ một khoảng \([S, S+n-1]\), từ vị trí hiện tại \(curr\), ta nên chọn đoạn dây bắt đầu tại hoặc trước \(curr\) và có điểm kết thúc \(r\) là lớn nhất có thể.
• Tối ưu hóa: Với \(n, k \le 10^6\), việc duyệt tham lam từng bước cho mỗi điểm bắt đầu sẽ tốn \(O(n \cdot k)\), không khả thi. Ta cần sử dụng kỹ thuật Binary Lifting (Nhảy nhị phân) để tăng tốc quá trình tìm kiếm.

Hướng giải quyết

1. Tiền xử lý

• Chuyển các đoạn dây về dạng tuyến tính trên phạm vi \([1, 2n]\).
• Gọi last[i] là điểm kết thúc xa nhất của một đoạn dây bất kỳ bắt đầu tại điểm \(i\) hoặc trước đó.
  • Khởi tạo last[l] = max(last[l], r) cho mỗi đoạn dây \([l, r]\).
  • Cập nhật last[i] = max(last[i], last[i-1]) để đảm bảo tính tham lam (chọn đoạn bắt đầu \(\le i\) có kết thúc xa nhất).

2. Xây dựng bảng nhảy nhị phân

• Gọi \(dp[i][j]\) là điểm xa nhất có thể đạt tới nếu sử dụng \(2^j\) đoạn dây, bắt đầu từ điểm \(i\).
• Cơ sở: \(dp[i][0] = last[i]\).
• Công thức truy hồi: \(dp[i][j] = dp[dp[i][j-1] + 1][j-1]\).
  • Ý nghĩa: Để nhảy \(2^j\) bước, ta nhảy \(2^{j-1}\) bước từ \(i\) đến một vị trí, sau đó từ vị trí kế tiếp nhảy thêm \(2^{j-1}\) bước nữa.

3. Tính toán kết quả

• Với mỗi điểm bắt đầu \(i\) từ \(1\) đến \(n\), ta cần tính số đoạn dây ít nhất để phủ được khoảng \([i, i+n-1]\).
• Sử dụng bảng \(dp\) để nhảy nhị phân:
  • Thử các bước nhảy từ \(2^{20}\) xuống \(2^0\).
  • Nếu nhảy \(2^j\) bước mà vẫn chưa phủ tới \(i+n-1\), ta thực hiện nhảy và cộng \(2^j\) vào kết quả.
• Kết quả cuối cùng là giá trị nhỏ nhất trong tất cả các điểm bắt đầu \(i\).

Độ phức tạp

• Thời gian: \(O((n+k) \log n)\) cho việc xây dựng bảng \(dp\) và \(O(n \log n)\) cho việc tìm kết quả. Tổng cộng là \(O((n+k) \log n)\).
• Bộ nhớ: \(O(n \log n)\) để lưu trữ bảng \(dp\).

Code tham khảo

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

#define endl "\n"
#define FAST ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);

const int LOG = 20;
const int INF = 1e9+7;
const int MAX = 2000005; // 2 * 10^6

int n, k;
int last[MAX];
int dp[MAX][LOG + 1];

struct Segment {
    int l, r;
    void input() {
        cin >> l >> r;
        if (r < l) {
            r = n + r; // Xử lý đoạn dây đi qua điểm n
        }
    }
} segments[1000005];

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= k; i++) {
        segments[i].input();
        // Cập nhật điểm kết thúc xa nhất cho điểm bắt đầu l
        last[segments[i].l] = max(last[segments[i].l], segments[i].r);
        // Để xử lý vòng tròn, ta cũng xét các đoạn tịnh tiến thêm n
        if (segments[i].l + n < MAX) {
            last[segments[i].l + n] = max(last[segments[i].l + n], min(MAX - 1, segments[i].r + n));
        }
    }

    // Tiền xử lý mảng last: last[i] là điểm kết thúc xa nhất của đoạn dây bắt đầu <= i
    for (int i = 1; i < MAX; i++) {
        last[i] = max(last[i], last[i - 1]);
    }

    // Xây dựng bảng Sparse Table (Binary Lifting)
    for (int i = 1; i < MAX; i++) {
        dp[i][0] = last[i];
    }

    for (int j = 1; j <= LOG; j++) {
        for (int i = 1; i < MAX; i++) {
            if (dp[i][j - 1] + 1 < MAX)
                dp[i][j] = dp[dp[i][j - 1] + 1][j - 1];
            else
                dp[i][j] = MAX - 1;
        }
    }

    // Hàm tính số đoạn dây tối thiểu để phủ từ sta đến fin
    auto calc = [&](int sta, int fin) {
        if (last[sta] < sta) return INF; // Không có đoạn dây nào bắt đầu tại hoặc trước sta
        int result = 0;
        int current = sta;
        for (int i = LOG; i >= 0; i--) {
            if (dp[current][i] < fin) {
                result += (1 << i);
                current = dp[current][i] + 1;
                if (current >= MAX) return INF;
            }
        }
        // Sau khi nhảy, nếu bước cuối cùng phủ được fin thì cộng thêm 1
        if (dp[current][0] >= fin) return result + 1;
        return INF;
    };

    int ans = INF;
    // Thử mọi điểm bắt đầu từ 1 đến n để tìm phương án tốt nhất
    for (int i = 1; i <= n; i++) {
        ans = min(ans, calc(i, i + n - 1));
    }

    if (ans >= INF) cout << "impossible";
    else cout << ans;
}

int main() {
    FAST;
    solve();
    return 0;
}