Hiểu bài toán

Bài toán yêu cầu kiểm tra sự t tồn tại của một số nguyên n thuộc đồng thời hai khoảng [A, B] và [C, D]. Nói cách khác, chúng ta cần xác định xem hai đoạn thẳng này có giao nhau hay không. Nếu có giao điểm (kể cả một điểm duy nhất), kết quả là 'YES', ngược lại là 'NO'. Dữ liệu đầu vào có thể lên tới 10^18 nên cần phải xử lý kiểu dữ liệu lớn (64-bit integer).

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

Cách So sánh biên

#include <stdio.h>

int main() {
    long long a, b, c, d;
    scanf("%lld %lld %lld %lld", &a, &b, &c, &d);

    // Hai đoạn [a, b] và [c, d] giao nhau nếu:
    // Đoạn thứ nhất kết thúc sau hoặc bằng lúc đoạn thứ hai bắt đầu (b >= c)
    // VÀ đoạn thứ hai kết thúc sau hoặc bằng lúc đoạn thứ hai bắt đầu (d >= a)
    if (b >= c && d >= a) {
        printf("YES");
    } else {
        printf("NO");
    }
    return 0;
}

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

Đây là cách tiếp cận trực quan và tối ưu nhất. Hai đoạn [A, B] và [C, D] có giao nhau khi và chỉ khi điểm cuối của đoạn thứ nhất (B) lớn hơn hoặc bằng điểm đầu của đoạn thứ hai (C) và điểm cuối của đoạn thứ hai (D) lớn hơn hoặc bằng điểm đầu của đoạn thứ nhất (A). Điều kiện logic này bao gồm cả trường hợp hai đoạn chỉ chạm nhau tại một điểm (ví dụ B = C).

Cách Phương pháp loại trừ

#include <stdio.h>

int main() {
    long long a, b, c, d;
    scanf("%lld %lld %lld %lld", &a, &b, &c, &d);

    // Hai đoạn KHÔNG giao nhau khi:
    // Đoạn 1 nằm hoàn toàn trước đoạn 2 (b < c)
    // HOẶC đoạn 1 nằm hoàn toàn sau đoạn 2 (d < a)
    if (b < c || d < a) {
        printf("NO");
    } else {
        printf("YES");
    }
    return 0;
}

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

Cách này kiểm tra các trường hợp không giao nhau. Nếu đoạn [A, B] nằm hoàn toàn trước [C, D] (tức B < C) hoặc [A, B] nằm hoàn toàn sau [C, D] (tức D < A), ta in 'NO'. Ngược lại, in 'YES'. Đây chỉ là cách viết khác của cách tiếp cận đầu tiên nhưng logic cũng tương đương.

Cách Xử lý chuỗi (Sai lệch)

#include <stdio.h>
#include <string.h>

// Hàm so sánh hai chuỗi số đại diện cho số lớn
int check(char a[], char b[]) {
    if(strlen(a) > strlen(b)) return 1; // a có nhiều chữ số hơn -> a lớn hơn
    else if(strlen(b) > strlen(a)) return 0; // b có nhiều chữ số hơn -> a nhỏ hơn
    else {
        // Cùng độ dài, so sánh từng chữ số từ trái sang phải
        for(int i = 0; i < strlen(a); i++) {
            if(a[i] > b[i]) return 1;
            if(a[i] < b[i]) return 0;
        }
    }
    return 2; // Bằng nhau
}

int main() {
    char a[50], b[50], c[50], d[50];
    scanf("%s %s %s %s", a, b, c, d);

    // Logic trong code mẫu có vẻ bị sai lệch so với bài toán chuẩn,
    // Nhưng về cơ bản nó đang cố gắng xử lý số nguyên lớn bằng chuỗi.
    // Code mẫu kiểm tra: if(check(b,c) == 0 || check(a,d) == 1)
    // Tức là: (B <= C) OR (A >= D) -> NO
    // Thực tế điều kiện giao nhau là B >= C VÀ D >= A.
    // Vậy code mẫu đang kiểm tra điều kiện BẶT NGƯỢC (không giao nhau).
    if(check(b, c) == 0 || check(a, d) == 1) {
        printf("NO");
    } else {
        printf("YES");
    }
    return 0;
}

• Time Complexity: O(L) ~ O(20)
• Space Complexity: O(1)

Cách tiếp cận này sử dụng chuỗi để xử lý số lớn (vượt quá 64-bit). Tuy nhiên, trong bài toán này với giới hạn 10^18, kiểu long long là đủ. Code mẫu sử dụng hàm check để so sánh chuỗi số, và logic điều kiện if(check(b,c) == 0 || check(a,d) == 1) thực chất là kiểm tra xem hai đoạn có KHÔNG giao nhau không (B <= C hoặc A >= D).

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

Bài học kinh nghiệm

• Bài toán chỉ cần kiểm tra sự giao nhau giữa hai đoạn thẳng, không cần duyệt qua các số.
• Điều kiện giao nhau giữa [A, B] và [C, D] là: max(A, C) <= min(B, D), hoặc tương đương với B >= C và D >= A.
• Với giới hạn dữ liệu 10^18, cần sử dụng kiểu dữ liệu 64-bit (long long trong C/C++, long trong Java).

Lỗi thường gặp

• Sử dụng kiểu int (32-bit) gây tràn số (overflow) vì dữ liệu đầu vào có thể lên tới 10^18.
• Viết sai điều kiện giao nhau, ví dụ quên trường hợp hai đoạn chỉ chạm nhau ở biên (phải dùng >= thay vì >).
• Confusion giữa toán tử && (và) và || (hoặc) trong điều kiện.