Khóa học CTDL và GT

Bài 16.2. Binary Search cơ bản và cài đặt

Chào mừng quay trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ khám phá một trong những thuật toán tìm kiếm kinh điển và mạnh mẽ nhất: Binary Search, hay còn gọi là Tìm kiếm nhị phân. Nếu bạn đã từng phải tìm kiếm một cuốn sách trong thư viện được sắp xếp theo thứ tự chữ cái, hoặc tra một từ trong cuốn từ điển dày cộp, thì bạn đã ngầm sử dụng ý tưởng cốt lõi của thuật toán này rồi đấy!

Tại sao lại cần Binary Search?

Trong bài trước, có thể bạn đã làm quen với Linear Search (Tìm kiếm tuyến tính). Đó là cách đơn giản nhất: duyệt qua từng phần tử một từ đầu đến cuối danh sách cho đến khi tìm thấy thứ cần tìm. Thuật toán này dễ hiểu, dễ cài đặt, nhưng có một nhược điểm chí mạng: nó có thể rất chậm khi danh sách của bạn cực kỳ dài. Hãy tưởng tượng bạn cần tìm một số trong một danh sách có một tỷ phần tử! Ở trường hợp xấu nhất, bạn có thể phải kiểm tra cả tỷ lần.

Binary Search ra đời để giải quyết vấn đề tốc độ này. Nó hoạt động nhanh hơn rất nhiều, đặc biệt là với các tập dữ liệu lớn. Tuy nhiên, để sử dụng được Binary Search, dữ liệu của bạn phải được sắp xếp. Đây là điều kiện tiên quyết cực kỳ quan trọng.

Binary Search Hoạt Động Như Thế Nào?

Ý tưởng của Binary Search dựa trên nguyên tắc chia để trị (divide and conquer). Thay vì kiểm tra tuần tự, chúng ta sẽ liên tục loại bỏ một nửa không gian tìm kiếm.

Hãy hình dung bạn đang tìm một số X trong một mảng arr đã được sắp xếp theo thứ tự tăng dần. Các bước thực hiện như sau:

1. Xác định phạm vi tìm kiếm ban đầu: từ phần tử đầu tiên đến phần tử cuối cùng của mảng. Ta sẽ sử dụng hai biến chỉ mục: low (điểm đầu) và high (điểm cuối). Ban đầu, low = 0 và high = kích thước mảng - 1.
2. Trong khi low còn nhỏ hơn hoặc bằng high (tức là phạm vi tìm kiếm vẫn còn hợp lệ): a. Tính chỉ mục của phần tử điểm giữa (mid) trong phạm vi tìm kiếm hiện tại. Công thức phổ biến là mid = low + (high - low) / 2. Cách tính này giúp tránh tràn số nếu low và high quá lớn, so với mid = (low + high) / 2. b. So sánh phần tử tại chỉ mục mid (arr[mid]) với giá trị X cần tìm:

   *   Nếu `arr[mid] == X`: *Chúc mừng!* Bạn đã tìm thấy phần tử tại chỉ mục `mid`. Kết thúc quá trình và trả về `mid`.
   *   Nếu `arr[mid] < X`: Phần tử ở giữa nhỏ hơn giá trị cần tìm. Điều này có nghĩa là nếu `X` tồn tại trong mảng, nó *chắc chắn phải nằm ở nửa bên phải* của `mid` (vì mảng đã sắp xếp). Ta loại bỏ nửa bên trái và cập nhật phạm vi tìm kiếm: `low = mid + 1`.
   *   Nếu `arr[mid] > X`: Phần tử ở giữa lớn hơn giá trị cần tìm. Tương tự, nếu `X` tồn tại, nó *chắc chắn phải nằm ở nửa bên trái* của `mid`. Ta loại bỏ nửa bên phải và cập nhật phạm vi tìm kiếm: `high = mid - 1`.

3. Nếu vòng lặp kết thúc mà không tìm thấy phần tử nào (tức là low trở nên lớn hơn high), điều đó có nghĩa là giá trị X không tồn tại trong mảng. Ta trả về một giá trị đặc biệt để báo hiệu không tìm thấy, ví dụ: -1.

Mỗi lần lặp, thuật toán lại thu hẹp phạm vi tìm kiếm xuống còn một nửa. Chính vì thế, số lượng bước tìm kiếm giảm đi rất nhanh. Độ phức tạp thời gian của Binary Search là O(log n), nơi n là số phần tử trong mảng. Đây là một cải tiến vượt bậc so với O(n) của Linear Search khi n lớn.

Cài Đặt Binary Search bằng C++

Chúng ta có thể cài đặt Binary Search theo hai cách chính: lặp (iterative) và đệ quy (recursive).

Cách 1: Cài Đặt Sử Dụng Vòng Lặp (Iterative)

Đây là cách cài đặt phổ biến và thường được ưa chuộng hơn vì nó không tốn thêm bộ nhớ cho các lời gọi hàm đệ quy.

#include <iostream>
#include <vector> // Sử dụng vector cho dễ dàng

// Hàm Binary Search sử dụng vòng lặp
// Trả về chỉ mục của target nếu tìm thấy, ngược lại trả về -1
int binarySearchIterative(const std::vector<int>& arr, int target) {
    // Kiểm tra nếu mảng rỗng
    if (arr.empty()) {
        return -1;
    }

    int low = 0; // Chỉ mục đầu tiên
    int high = arr.size() - 1; // Chỉ mục cuối cùng

    // Lặp lại cho đến khi phạm vi tìm kiếm còn hợp lệ
    while (low <= high) {
        // Tính chỉ mục điểm giữa một cách an toàn
        int mid = low + (high - low) / 2;

        // So sánh phần tử ở giữa với target
        if (arr[mid] == target) {
            // Tìm thấy! Trả về chỉ mục
            return mid;
        } else if (arr[mid] < target) {
            // Phần tử giữa nhỏ hơn target, tìm kiếm ở nửa bên phải
            low = mid + 1;
        } else { // arr[mid] > target
            // Phần tử giữa lớn hơn target, tìm kiếm ở nửa bên trái
            high = mid - 1;
        }
    }

    // Nếu vòng lặp kết thúc mà không tìm thấy, target không có trong mảng
    return -1;
}

int main() {
    // Mảng đã được sắp xếp (điều kiện bắt buộc!)
    std::vector<int> sortedArray = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int target1 = 23;
    int target2 = 50;

    int index1 = binarySearchIterative(sortedArray, target1);
    if (index1 != -1) {
        std::cout << "Iterative: Phan tu " << target1 << " duoc tim thay tai chi muc: " << index1 << std::endl; // Output: Phan tu 23 duoc tim thay tai chi muc: 5
    } else {
        std::cout << "Iterative: Phan tu " << target1 << " khong co trong mang." << std::endl;
    }

    int index2 = binarySearchIterative(sortedArray, target2);
    if (index2 != -1) {
        std::cout << "Iterative: Phan tu " << target2 << " duoc tim thay tai chi muc: " << index2 << std::endl;
    } else {
        std::cout << "Iterative: Phan tu " << target2 << " khong co trong mang." << std::endl; // Output: Phan tu 50 khong co trong mang.
    }

    return 0;
}

Giải thích code (Iterative):

• Hàm binarySearchIterative nhận một std::vector<int> (là mảng đã sắp xếp) và giá trị target cần tìm.
• Chúng ta khởi tạo low = 0 và high = arr.size() - 1 để định nghĩa toàn bộ mảng là phạm vi tìm kiếm ban đầu.
• Vòng lặp while (low <= high) tiếp tục chừng nào phạm vi tìm kiếm còn chứa ít nhất một phần tử (low và high chưa vượt qua nhau).
• mid = low + (high - low) / 2; tính chỉ mục trung bình. Phép trừ (high - low) rồi chia 2, sau đó cộng với low giúp tránh lỗi tràn số có thể xảy ra nếu low + high vượt quá giá trị lớn nhất của kiểu int.
• Bên trong vòng lặp, chúng ta so sánh arr[mid] với target:
  • Nếu bằng, ta tìm thấy và trả về mid.
  • Nếu arr[mid] < target, ta biết target (nếu có) phải nằm ở phía sau mid, nên ta cập nhật low = mid + 1.
  • Nếu arr[mid] > target, target (nếu có) phải nằm ở phía trước mid, nên ta cập nhật high = mid - 1.
• Nếu vòng lặp kết thúc (low > high), điều đó có nghĩa là không tìm thấy target trong bất kỳ phạm vi tìm kiếm nào còn lại. Ta trả về -1 để báo hiệu điều này.
• Hàm main minh họa cách gọi hàm binarySearchIterative với một mảng mẫu và hai giá trị cần tìm (một có trong mảng, một không có).

Cách 2: Cài Đặt Sử Dụng Đệ Quy (Recursive)

Cách tiếp cận này sử dụng các lời gọi hàm đệ quy để thu hẹp phạm vi tìm kiếm.

#include <iostream>
#include <vector> // Sử dụng vector

// Hàm Binary Search sử dụng đệ quy
// Hàm helper này nhận thêm low và high làm tham số
int binarySearchRecursiveHelper(const std::vector<int>& arr, int low, int high, int target) {
    // Điều kiện dừng đệ quy (base case): phạm vi tìm kiếm không hợp lệ
    if (low > high) {
        // Không tìm thấy target
        return -1;
    }

    // Tính chỉ mục điểm giữa
    int mid = low + (high - low) / 2;

    // So sánh phần tử ở giữa với target
    if (arr[mid] == target) {
        // Tìm thấy! Trả về chỉ mục
        return mid;
    } else if (arr[mid] < target) {
        // Phần tử giữa nhỏ hơn target, tìm kiếm ở nửa bên phải
        // Gọi đệ quy với phạm vi mới: từ mid + 1 đến high
        return binarySearchRecursiveHelper(arr, mid + 1, high, target);
    } else { // arr[mid] > target
        // Phần tử giữa lớn hơn target, tìm kiếm ở nửa bên trái
        // Gọi đệ quy với phạm vi mới: từ low đến mid - 1
        return binarySearchRecursiveHelper(arr, low, mid - 1, target);
    }
}

// Hàm bọc (wrapper) cho dễ sử dụng từ bên ngoài
int binarySearchRecursive(const std::vector<int>& arr, int target) {
    // Kiểm tra nếu mảng rỗng
    if (arr.empty()) {
        return -1;
    }
    // Bắt đầu tìm kiếm với phạm vi toàn bộ mảng
    return binarySearchRecursiveHelper(arr, 0, arr.size() - 1, target);
}

int main() {
    // Mảng đã được sắp xếp (điều kiện bắt buộc!)
    std::vector<int> sortedArray = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int target1 = 23;
    int target2 = 50;

    int index1 = binarySearchRecursive(sortedArray, target1);
    if (index1 != -1) {
        std::cout << "Recursive: Phan tu " << target1 << " duoc tim thay tai chi muc: " << index1 << std::endl; // Output: Phan tu 23 duoc tim thay tai chi muc: 5
    } else {
        std::cout << "Recursive: Phan tu " << target1 << " khong co trong mang." << std::endl;
    }

    int index2 = binarySearchRecursive(sortedArray, target2);
    if (index2 != -1) {
        std::cout << "Recursive: Phan tu " << target2 << " duoc tim thay tai chi muc: " << index2 << std::endl;
    } else {
        std::cout << "Recursive: Phan tu " << target2 << " khong co trong mang." << std::endl; // Output: Phan tu 50 khong co trong mang.
    }

    return 0;
}

Giải thích code (Recursive):

• Chúng ta có hai hàm: binarySearchRecursiveHelper là hàm chính thực hiện đệ quy, nhận thêm low và high để xác định phạm vi tìm kiếm hiện tại. Hàm binarySearchRecursive chỉ là hàm bọc để gọi binarySearchRecursiveHelper lần đầu với toàn bộ mảng.
• Điều kiện dừng đệ quy (Base Case): if (low > high) là điều kiện quan trọng nhất. Nếu điểm đầu low vượt qua điểm cuối high, điều đó có nghĩa là phạm vi tìm kiếm đã bị thu hẹp đến mức không còn chứa phần tử nào, và chúng ta chưa tìm thấy target. Hàm trả về -1.
• Nếu không đạt điều kiện dừng, ta tính mid tương tự như cách lặp.
• So sánh arr[mid] với target:
  • Nếu bằng, ta tìm thấy và trả về mid. Lời gọi đệ quy kết thúc tại đây.
  • Nếu arr[mid] < target, ta biết target (nếu có) phải nằm ở phía sau mid. Thay vì cập nhật biến low, ta thực hiện một lời gọi đệ quy mới trên phạm vi mid + 1 đến high. Giá trị trả về của lời gọi đệ quy này chính là kết quả của hàm hiện tại.
  • Nếu arr[mid] > target, target (nếu có) phải nằm ở phía trước mid. Ta thực hiện lời gọi đệ quy mới trên phạm vi low đến mid - 1.
• Hàm main tương tự như ở cách lặp, minh họa cách sử dụng.

Mặc dù cách đệ quy thể hiện ý tưởng chia đôi mảng khá trực quan, nó có thể tốn kém bộ nhớ hơn cho stack các lời gọi hàm, đặc biệt với mảng rất lớn. Cách lặp thường hiệu quả hơn về mặt bộ nhớ.

Ví Dụ Minh Họa Chi Tiết

Hãy theo dõi quá trình Binary Search hoạt động với mảng [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (có 10 phần tử, chỉ mục từ 0 đến 9) và chúng ta muốn tìm target = 23.

• Bước 1:

  • low = 0, high = 9
  • mid = 0 + (9 - 0) / 2 = 4
  • arr[mid] (tức arr[4]) là 16.
  • 16 < 23 (arr[mid] < target). Target nằm ở bên phải.
  • Cập nhật low = mid + 1 = 4 + 1 = 5.
  • Phạm vi tìm kiếm mới: [5, 9].

• Bước 2:

  • low = 5, high = 9 (low <= high vẫn đúng)
  • mid = 5 + (9 - 5) / 2 = 5 + 4 / 2 = 5 + 2 = 7
  • arr[mid] (tức arr[7]) là 56.
  • 56 > 23 (arr[mid] > target). Target nằm ở bên trái.
  • Cập nhật high = mid - 1 = 7 - 1 = 6.
  • Phạm vi tìm kiếm mới: [5, 6].

• Bước 3:

  • low = 5, high = 6 (low <= high vẫn đúng)
  • mid = 5 + (6 - 5) / 2 = 5 + 1 / 2 = 5 + 0 = 5
  • arr[mid] (tức arr[5]) là 23.
  • 23 == 23 (arr[mid] == target). Tìm thấy!
  • Trả về chỉ mục mid, tức là 5.

Quá trình kết thúc chỉ sau 3 bước so sánh, thay vì phải kiểm tra tuần tự ít nhất 6 bước nếu dùng Linear Search.

Bây giờ, hãy thử tìm một giá trị không có trong mảng, ví dụ target = 50.

• Bước 1:

  • low = 0, high = 9
  • mid = 4, arr[4] = 16.
  • 16 < 50. Cập nhật low = 5.
  • Phạm vi: [5, 9].

• Bước 2:

  • low = 5, high = 9
  • mid = 7, arr[7] = 56.
  • 56 > 50. Cập nhật high = 6.
  • Phạm vi: [5, 6].

• Bước 3:

  • low = 5, high = 6
  • mid = 5, arr[5] = 23.
  • 23 < 50. Cập nhật low = 6.
  • Phạm vi: [6, 6].

• Bước 4:

  • low = 6, high = 6 (low <= high vẫn đúng)
  • mid = 6 + (6 - 6) / 2 = 6 + 0 = 6
  • arr[mid] (tức arr[6]) là 38.
  • 38 < 50. Cập nhật low = 7.
  • Phạm vi: [7, 6].

• Bước 5:

  • low = 7, high = 6. Lúc này low > high.
  • Vòng lặp while (low <= high) (ở bản lặp) sẽ dừng lại.
  • Hoặc điều kiện đệ quy if (low > high) (ở bản đệ quy) sẽ đúng và trả về -1.
  • Kết quả: Không tìm thấy. Trả về -1.

Xử Lý Các Trường Hợp Biên (Edge Cases)

• Mảng rỗng: Nếu mảng đầu vào rỗng, arr.size() sẽ là 0. high sẽ là -1. Ngay từ đầu, low (0) đã lớn hơn high (-1). Vòng lặp while (low <= high) sẽ không chạy lần nào, và hàm sẽ trả về -1, đúng như mong đợi. Tương tự với bản đệ quy, điều kiện low > high (0 > -1) sẽ đúng ngay lập tức ở lần gọi đầu tiên, trả về -1.
• Mảng chỉ có một phần tử: low = 0, high = 0. mid = 0. So sánh arr[0] với target. Nếu bằng thì tìm thấy. Nếu khác, low hoặc high sẽ được cập nhật, dẫn đến low > high ở bước tiếp theo, kết thúc tìm kiếm và trả về -1.
• Phần tử cần tìm là phần tử đầu tiên hoặc cuối cùng: Thuật toán vẫn hoạt động chính xác. Phạm vi tìm kiếm sẽ dần thu hẹp cho đến khi mid trùng với chỉ mục của phần tử đầu tiên hoặc cuối cùng.

Ưu Điểm và Nhược Điểm của Binary Search

• Ưu điểm:

  • Tốc độ cực nhanh: Độ phức tạp O(log n) làm cho nó hiệu quả hơn Linear Search rất nhiều trên các tập dữ liệu lớn.
  • Hiệu quả bộ nhớ: Cài đặt lặp chỉ cần một vài biến để lưu trữ low, high, mid, rất tiết kiệm bộ nhớ (độ phức tạp O(1) không gian bổ sung). Bản đệ quy tốn thêm không gian cho stack gọi hàm, nhưng vẫn thường chấp nhận được.

• Nhược điểm:

  • Yêu cầu dữ liệu phải được sắp xếp: Đây là hạn chế lớn nhất. Nếu dữ liệu chưa sắp xếp, bạn cần phải sắp xếp nó trước khi áp dụng Binary Search, điều này tốn thêm thời gian (thường là O(n log n)).
  • Yêu cầu truy cập ngẫu nhiên: Binary Search hoạt động hiệu quả nhất trên các cấu trúc dữ liệu cho phép truy cập nhanh đến bất kỳ phần tử nào bằng chỉ mục của nó (như mảng tĩnh hoặc std::vector). Nó không phù hợp trực tiếp với các cấu trúc như danh sách liên kết đơn (singly linked list) vì việc tìm phần tử giữa đòi hỏi phải duyệt từ đầu danh sách.

Ứng Dụng Trong Thực Tế

Binary Search không chỉ là một bài tập lý thuyết. Nó được sử dụng rộng rãi:

• Trong các thư viện chuẩn: Hàm tìm kiếm trong các thư viện chuẩn của nhiều ngôn ngữ (ví dụ: std::binary_search, std::lower_bound, std::upper_bound trong C++) thường dựa trên Binary Search hoặc các biến thể của nó.
• Cơ sở dữ liệu và hệ thống file: Nhiều cấu trúc dữ liệu được sử dụng trong cơ sở dữ liệu và hệ thống file (như B-trees) sử dụng nguyên lý chia đôi tương tự để tìm kiếm dữ liệu nhanh chóng.
• Tìm kiếm trong từ điển hoặc tập hợp (Set): Các cấu trúc dữ liệu như std::set hoặc std::map trong C++ thường được triển khai dựa trên cây tìm kiếm nhị phân tự cân bằng (Balanced Binary Search Trees), nơi việc tìm kiếm cũng sử dụng nguyên lý Binary Search để đạt O(log n).
• Tìm kiếm giá trị gần đúng hoặc giới hạn: Binary Search có thể được biến thể để tìm phần tử nhỏ nhất lớn hơn hoặc bằng một giá trị nào đó, hoặc phần tử lớn nhất nhỏ hơn hoặc bằng một giá trị nào đó (như lower_bound và upper_bound).
• Giải các bài toán: Nhiều bài toán lập trình thi đấu có thể được giải quyết hiệu quả bằng cách nhận ra rằng đáp án có thể được tìm kiếm bằng Binary Search trên một khoảng giá trị nào đó.

Bài tập ví dụ:

Đội ngũ đa dạng bình đẳng

Trong một buổi thảo luận về thuật toán, FullHouse Dev được giới thiệu một bài toán thú vị liên quan đến việc phân chia nhóm. Họ quyết định lập trình một giải pháp để giúp Alice, một giáo viên, trong việc tổ chức lớp học của mình. Với sự hỗ trợ của máy tính, FullHouse Dev bắt đầu phân tích vấn đề này.

Bài toán

Alice có \(n\) học sinh trong lớp, được đánh số từ \(1\) đến \(n\). Học sinh thứ \(i\) có chuyên môn trong môn học được đánh số \(a_i\). Alice cần chia học sinh thành hai đội. Tính đa dạng của một đội được định nghĩa là số lượng môn học khác nhau mà có ít nhất một học sinh trong đội có chuyên môn. Alice muốn phân chia học sinh sao cho mỗi học sinh thuộc đúng một đội và tính đa dạng của mỗi đội đều bằng \(k\). Liệu Alice có thể thực hiện được điều này không?

INPUT FORMAT:

• Dòng đầu tiên chứa một số nguyên \(T\) - số lượng bộ test.
• Với mỗi bộ test:
  • Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\).
  • Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\).

OUTPUT FORMAT:

• Với mỗi bộ test, in ra "YES" nếu Alice có thể chia đội thỏa mãn điều kiện, ngược lại in ra "NO".

Ràng buộc:

• \(1 \leq T \leq 10^5\)
• \(1 \leq n \leq 2 \times 10^5\)
• \(1 \leq k \leq n\)
• \(1 \leq a_i \leq n\)

Ví dụ

INPUT

2
6 2
1 4 4 6 2 1
4 2
1 1 1 1

OUTPUT

YES
NO

Giải thích

• Ở bộ test đầu tiên, Alice có thể đặt học sinh thứ tư và thứ năm vào đội một, và những học sinh còn lại vào đội hai. Khi đó, chuyên môn của các đội sẽ là \({6, 2}\) và \({1, 4, 1}\). Cả hai đội đều có tính đa dạng là 2.
• Ở bộ test thứ hai, không thể chia học sinh thành hai đội có tính đa dạng bằng 2. Tuyệt vời! Đây là hướng dẫn giải bài toán "Đội ngũ đa dạng bình đẳng" một cách ngắn gọn bằng C++, tập trung vào ý tưởng chính và cấu trúc dữ liệu cần dùng, không cung cấp code hoàn chỉnh.

1. Phân tích bài toán và yêu cầu:

• Chúng ta cần chia n học sinh thành hai đội.
• Mỗi học sinh thuộc đúng một đội.
• Mỗi đội phải có số lượng môn học (chuyên môn) độc đáo (tính đa dạng) đúng bằng k.
• Xác định xem việc chia đội có khả thi hay không.

2. Khái niệm quan trọng: Tính đa dạng

Tính đa dạng của một đội là số lượng các môn học khác nhau có ít nhất một học sinh trong đội đó chuyên môn.

3. Suy luận về điều kiện khả thi:

• Gọi tập hợp các môn học độc đáo trong Đội 1 là S1 và trong Đội 2 là S2.
• Yêu cầu bài toán là |S1| = k và |S2| = k.
• Tất cả học sinh phải được chia vào hai đội. Nếu một học sinh có chuyên môn a_i, thì a_i phải nằm trong tập hợp môn học của đội mà học sinh đó được xếp vào.
• Điều này có nghĩa là tập hợp tất cả các môn học độc đáo có trong toàn bộ n học sinh (U) phải là hợp của S1 và S2. Hay nói cách khác, U = S1 \cup S2.
• Theo nguyên lý bù trừ (inclusion-exclusion principle): |S1 \cup S2| = |S1| + |S2| - |S1 \cap S2|.
• Thay thế các giá trị đã biết: |U| = k + k - |S1 \cap S2| = 2k - |S1 \cap S2|.
• Vì |S1 \cap S2| \ge 0 (số lượng môn học chung giữa hai đội không âm), ta có |U| \le 2k. Nếu tổng số môn học độc đáo trong lớp mà lớn hơn 2k, thì không thể chia thành hai đội mà mỗi đội chỉ có k môn độc đáo và hợp lại bao gồm tất cả các môn học trong lớp.
• Nếu |U| < 2k, từ phương trình |U| = 2k - |S1 \cap S2|, ta suy ra |S1 \cap S2| = 2k - |U| > 0. Điều này có nghĩa là phải có ít nhất một môn học chung giữa hai đội. Tuy nhiên, việc có môn học chung chỉ khả thi khi môn học đó xuất hiện ít nhất hai lần trong toàn bộ lớp (để có thể xếp ít nhất 1 học sinh vào Đội 1 và ít nhất 1 học sinh vào Đội 2). Việc chứng minh điều này luôn khả thi khi |U| < 2k phức tạp hơn và không cần thiết nếu ta tìm được một điều kiện chặt chẽ hơn.
• Xét trường hợp |U| = 2k. Từ phương trình |U| = 2k - |S1 \cap S2|, ta suy ra 2k = 2k - |S1 \cap S2|, điều này chỉ đúng khi |S1 \cap S2| = 0. Tức là S1 và S2 phải là hai tập hợp rời nhau, mỗi tập có k môn học, và hợp của chúng chính là tập hợp tất cả các môn học độc đáo trong lớp.
• Nếu có đúng 2k môn học độc đáo trong lớp, ta có thể xây dựng một cách chia đội như sau: Xác định 2k môn học độc đáo đó. Chia 2k môn này thành hai tập rời nhau S1 và S2, mỗi tập k môn. Xếp tất cả học sinh có chuyên môn trong S1 vào Đội 1. Xếp tất cả học sinh có chuyên môn trong S2 vào Đội 2.
  • Mỗi học sinh đều có chuyên môn thuộc U = S1 \cup S2$, và vìS1,S2` rời nhau, mỗi học sinh được xếp vào đúng một đội.
  • Đội 1 chỉ có học sinh có chuyên môn trong S1. Vì mỗi môn trong S1 đều có ít nhất một học sinh chuyên môn (do S1 \subseteq U), nên Đội 1 có tính đa dạng đúng bằng |S1| = k.
  • Tương tự, Đội 2 có tính đa dạng đúng bằng |S2| = k.
• Như vậy, nếu số lượng môn học độc đáo trong toàn bộ lớp là đúng 2k, ta luôn có thể chia đội theo yêu cầu.
• Nếu số lượng môn học độc đáo trong toàn bộ lớp không bằng 2k (bao gồm cả trường hợp |U| < 2k và |U| > 2k), ta đã chứng minh là không thể tìm được hai tập S1, S2 có kích thước k mà hợp của chúng là U. Do đó, không thể chia đội thỏa mãn.

4. Kết luận điều kiện:

Điều kiện cần và đủ để Alice có thể chia đội là tổng số lượng môn học độc đáo trong toàn bộ lớp phải bằng đúng 2k.

5. Hướng giải thuật toán:

1. Với mỗi bộ test:
2. Đọc n và k.
3. Đọc danh sách n chuyên môn a_1, a_2, ..., a_n.
4. Đếm số lượng môn học độc đáo trong danh sách này. Cách hiệu quả là sử dụng một mảng boolean hoặc hash set để đánh dấu các môn học đã gặp.
   • Khởi tạo một mảng boolean seen có kích thước n+1 (hoặc lớn hơn giá trị a_i lớn nhất có thể) với tất cả giá trị là false.
   • Duyệt qua danh sách a_i. Đối với mỗi a_i:
     • Nếu seen[a_i] là false, tăng bộ đếm số môn học độc đáo và đặt seen[a_i] = true.
5. So sánh số lượng môn học độc đáo vừa đếm được với 2 * k.
6. Nếu bằng nhau, in ra "YES".
7. Nếu khác nhau, in ra "NO".

6. Cấu trúc dữ liệu gợi ý:

• Để lưu trữ danh sách chuyên môn: std::vector<int> hoặc mảng tĩnh int a[N].
• Để đếm số lượng môn học độc đáo một cách hiệu quả: std::vector<bool> hoặc bool seen[N+1] (kích thước phù hợp với ràng buộc của a_i và n) là tốt nhất vì a_i \le n. std::unordered_set<int> cũng là một lựa chọn hiệu quả (trung bình O(N)) nhưng có thể chậm hơn và dùng nhiều bộ nhớ hơn mảng boolean khi giá trị a_i nằm trong phạm vi nhỏ.

7. Ràng buộc và hiệu quả:

Với ràng buộc \sum n \leq 2 \times 10^5 trên tất cả các bộ test, giải pháp O(N) cho mỗi bộ test (sử dụng mảng boolean để đếm) sẽ đạt yêu cầu về thời gian và bộ nhớ.

Làm thêm nhiều bài tập miễn phí tại đây