Bài 5.4. Đệ quy đuôi và biến đổi sang vòng lặp

Chào mừng các bạn quay trở lại với series về Cấu trúc dữ liệu và Giải thuật! Trong bài học trước, chúng ta đã làm quen với khái niệm đệ quy - một kỹ thuật lập trình mạnh mẽ và thanh lịch. Tuy nhiên, đệ quy truyền thống có một nhược điểm tiềm ẩn: lãng phí bộ nhớ stack do mỗi lần gọi hàm đệ quy đều tạo ra một frame mới trên stack. Khi độ sâu đệ quy quá lớn, điều này có thể dẫn đến lỗi Stack Overflow.

May mắn thay, tồn tại một dạng đặc biệt của đệ quy được gọi là đệ quy đuôi (Tail Recursion), và nó có thể được tối ưu hóa để giải quyết vấn đề này. Thậm chí, chúng ta có thể dễ dàng biến đổi một hàm đệ quy đuôi thành một hàm sử dụng vòng lặp (Iteration) mà không làm mất đi tính đúng đắn của giải thuật, đồng thời loại bỏ hoàn toàn chi phí stack!

Hãy cùng đi sâu tìm hiểu nhé!

Đệ quy đuôi (Tail Recursion) là gì?

Đệ quy đuôi là một trường hợp đặc biệt của đệ quy, trong đó lời gọi đệ quy là thao tác cuối cùng được thực hiện trong hàm. Không còn phép tính hay xử lý nào khác cần phải làm sau khi lời gọi đệ quy trả về.

Để hiểu rõ hơn, hãy xem xét sự khác biệt giữa đệ quy thông thường và đệ quy đuôi qua một ví dụ kinh điển: tính giai thừa.

Ví dụ: Tính Giai thừa (Factorial)

Đệ quy thông thường (Không phải đệ quy đuôi)

int factorial_recursive(int n) {
    if (n == 0) {
        return 1; // Trường hợp cơ sở
    } else {
        // Lời gọi đệ quy KHÔNG phải là thao tác cuối cùng.
        // Sau khi factorial_recursive(n-1) trả về, ta còn phải nhân kết quả với n.
        return n * factorial_recursive(n - 1);
    }
}

Giải thích: Trong hàm factorial_recursive(n), khi n > 0, hàm gọi lại chính nó với đối số n-1. Tuy nhiên, sau khi lời gọi factorial_recursive(n-1) hoàn thành và trả về một giá trị, hàm factorial_recursive(n) vẫn phải thực hiện thêm một phép tính nữa: phép nhân kết quả trả về với n. Điều này có nghĩa là hàm factorial_recursive(n) cần ghi nhớ giá trị của n trong frame stack của nó cho đến khi lời gọi con hoàn thành. Đây chính là lý do dẫn đến việc sử dụng nhiều bộ nhớ stack.

Đệ quy đuôi (Tail Recursive)

Để biến đổi sang đệ quy đuôi, chúng ta cần truyền kết quả trung gian (kết quả tích lũy) thông qua các tham số của hàm đệ quy. Điều này thường đòi hỏi một hoặc nhiều tham số bổ sung.

// Hàm hỗ trợ đệ quy đuôi
int tail_factorial_helper(int n, int accumulator) {
    if (n == 0) {
        // Trường hợp cơ sở: trả về kết quả tích lũy cuối cùng
        return accumulator;
    } else {
        // Lời gọi đệ quy là thao tác CUỐI CÙNG.
        // Kết quả n * accumulator được tính và truyền thẳng vào lời gọi tiếp theo.
        return tail_factorial_helper(n - 1, n * accumulator);
    }
}

// Hàm wrapper để gọi đệ quy đuôi với giá trị khởi tạo
int factorial_tail_recursive(int n) {
    // Giai thừa của 0 là 1, nên accumulator ban đầu là 1.
    return tail_factorial_helper(n, 1);
}

Giải thích: Hàm tail_factorial_helper có thêm tham số accumulator. Tham số này giữ kết quả của các phép nhân đã thực hiện cho đến thời điểm hiện tại. Trong lời gọi tail_factorial_helper(n - 1, n * accumulator), giá trị mới của accumulator (n * accumulator) được tính trước khi gọi đệ quy. Khi lời gọi đệ quy được thực hiện, không còn bất kỳ phép tính nào khác cần phải làm với kết quả của lời gọi đó. Hàm cha chỉ đơn giản là trả về trực tiếp kết quả của lời gọi đệ quy con. Đây chính là đặc điểm của đệ quy đuôi.

Tại sao đệ quy đuôi lại quan trọng?

Điểm đặc biệt của đệ quy đuôi nằm ở chỗ nó cho phép tối ưu hóa bởi trình biên dịch. Kỹ thuật tối ưu này được gọi là Tail Call Optimization (TCO).

Khi một trình biên dịch hỗ trợ TCO và gặp một lời gọi đệ quy đuôi, thay vì tạo một stack frame mới cho lời gọi đó, nó có thể tái sử dụng stack frame hiện tại. Về cơ bản, nó biến đổi lời gọi đệ quy thành một lệnh "nhảy" (jump) về đầu hàm, cập nhật các tham số của hàm giống như cách vòng lặp cập nhật biến.

Kết quả là, một hàm đệ quy đuôi được tối ưu hóa sẽ sử dụng bộ nhớ stack hiệu quả như một vòng lặp. Nó tránh được nguy cơ tràn bộ nhớ stack ngay cả với độ sâu đệ quy rất lớn.

Mặc dù không phải mọi ngôn ngữ hoặc mọi trình biên dịch đều hỗ trợ TCO một cách mặc định và đầy đủ, việc viết code dưới dạng đệ quy đuôi vẫn rất hữu ích vì nó cho phép tối ưu hóa. Hơn nữa, như chúng ta sẽ thấy, cấu trúc của đệ quy đuôi giúp việc biến đổi nó sang dạng lặp thủ công trở nên cực kỳ đơn giản và trực quan.

Biến đổi đệ quy đuôi sang vòng lặp

Nếu trình biên dịch của bạn không hỗ trợ TCO hoặc bạn muốn đảm bảo hiệu quả bộ nhớ một cách tường minh, bạn có thể tự biến đổi hàm đệ quy đuôi sang dạng lặp. Quá trình này khá đơn giản vì đệ quy đuôi đã chuyển hết trạng thái cần thiết (kết quả trung gian, các biến kiểm soát) vào các tham số.

Các bước biến đổi cơ bản:

Xác định các tham số thay đổi: Các tham số của hàm đệ quy đuôi (bao gồm cả tham số tích lũy) sẽ trở thành các biến trong vòng lặp.
Thiết lập vòng lặp: Vòng lặp (thường là while) sẽ tiếp tục chạy miễn là điều kiện ngược lại với trường hợp cơ sở của đệ quy còn đúng.
Khởi tạo biến lặp: Khởi tạo các biến trong vòng lặp với giá trị khởi tạo ban đầu của các tham số đệ quy.
Cập nhật biến lặp: Bên trong vòng lặp, cập nhật các biến lặp theo cách mà các tham số đệ quy được cập nhật trong lời gọi đệ quy.
Xử lý trường hợp cơ sở: Khi vòng lặp kết thúc (tương đương với đạt đến trường hợp cơ sở), kết quả chính là giá trị trả về của trường hợp cơ sở trong hàm đệ quy đuôi.

Hãy áp dụng các bước này cho ví dụ giai thừa.

Ví dụ 1: Tính Giai thừa (Tiếp tục)

Biến đổi từ Đệ quy đuôi sang Vòng lặp

Hàm đệ quy đuôi của chúng ta là: tail_factorial_helper(int n, int accumulator) Trường hợp cơ sở: n == 0, trả về accumulator. Lời gọi đệ quy: tail_factorial_helper(n - 1, n * accumulator)

Tham số thay đổi: n và accumulator. Chúng ta sẽ dùng biến current_n và current_accumulator trong vòng lặp.
Điều kiện vòng lặp: Trường hợp cơ sở là n == 0. Điều kiện ngược lại là n > 0. Vòng lặp sẽ là while (current_n > 0).
Khởi tạo biến lặp: Giá trị ban đầu của n là tham số truyền vào hàm wrapper (n), accumulator là 1. Nên current_n = n, current_accumulator = 1.
Cập nhật biến lặp: Trong lời gọi đệ quy, n mới là n - 1, accumulator mới là n * accumulator. Bên trong vòng lặp, chúng ta sẽ cập nhật:
- current_accumulator = current_accumulator * current_n;
- current_n = current_n - 1;
Kết quả trả về: Khi vòng lặp kết thúc (current_n bằng 0), kết quả là giá trị cuối cùng của current_accumulator (tương ứng với giá trị trả về ở trường hợp cơ sở return accumulator;).

Áp dụng các bước trên, ta có hàm lặp:

int factorial_iterative(int n) {
    // Kiểm tra trường hợp đặc biệt cho n âm nếu cần, nhưng giả định n >= 0
    if (n < 0) {
        // Xử lý lỗi hoặc trả về giá trị thích hợp
        return -1; // Hoặc ném ngoại lệ
    }

    // Khởi tạo biến lặp từ giá trị ban đầu của tham số đệ quy
    int current_accumulator = 1;
    int current_n = n;

    // Vòng lặp thay thế các lời gọi đệ quy
    // Điều kiện lặp là ngược lại của điều kiện cơ sở (current_n == 0)
    while (current_n > 0) {
        // Cập nhật biến lặp theo cách tham số đệ quy được cập nhật
        current_accumulator = current_accumulator * current_n;
        current_n = current_n - 1;
    }

    // Trả về kết quả cuối cùng tương ứng với giá trị trả về của trường hợp cơ sở
    return current_accumulator;
}

Giải thích: Phiên bản lặp này sử dụng biến current_accumulator để tích lũy kết quả và current_n để đếm ngược từ n về 0. Vòng lặp while tiếp tục cho đến khi current_n về 0, tương tự như cách hàm đệ quy đuôi dừng lại ở trường hợp cơ sở n == 0. Mỗi lần lặp, chúng ta cập nhật current_accumulator và current_n giống hệt cách các tham số được cập nhật trong lời gọi đệ quy đuôi tail_factorial_helper(n - 1, n * accumulator). Phiên bản này chỉ sử dụng một lượng bộ nhớ stack cố định, không phụ thuộc vào giá trị của n.

Ví dụ 2: Tính Tổng các phần tử trong mảng

Hãy xem xét cách tính tổng các phần tử trong một mảng bằng đệ quy đuôi và biến đổi nó sang lặp.

Đệ quy đuôi

Chúng ta cần truyền chỉ số hiện tại và tổng đã tính được cho đến chỉ số đó.

// Hàm hỗ trợ đệ quy đuôi
int tail_sum_helper(const int arr[], int index, int current_sum, int size) {
    if (index == size) {
        // Trường hợp cơ sở: đã duyệt hết mảng, trả về tổng tích lũy
        return current_sum;
    } else {
        // Lời gọi đệ quy là thao tác CUỐI CÙNG
        return tail_sum_helper(arr, index + 1, current_sum + arr[index], size);
    }
}

// Hàm wrapper
int sum_array_tail_recursive(const int arr[], int size) {
    // Bắt đầu từ chỉ số 0, tổng ban đầu là 0
    return tail_sum_helper(arr, 0, 0, size);
}

Giải thích: index theo dõi vị trí phần tử đang xét, current_sum tích lũy tổng các phần tử đã qua. Khi index bằng size (đã duyệt hết mảng), ta trả về current_sum. Ngược lại, ta gọi đệ quy với index + 1 và tổng mới là current_sum + arr[index]. Lời gọi đệ quy này là thao tác cuối cùng trong hàm.

Biến đổi từ Đệ quy đuôi sang Vòng lặp

Hàm đệ quy đuôi: tail_sum_helper(const int arr[], int index, int current_sum, int size) Trường hợp cơ sở: index == size, trả về current_sum. Lời gọi đệ quy: tail_sum_helper(arr, index + 1, current_sum + arr[index], size)

Tham số thay đổi: index và current_sum. Chúng ta sẽ dùng biến current_index và total_sum.
Điều kiện vòng lặp: Trường hợp cơ sở là index == size. Điều kiện ngược lại là index < size. Vòng lặp sẽ là while (current_index < size).
Khởi tạo biến lặp: Giá trị ban đầu của index là 0, current_sum là 0. Nên current_index = 0, total_sum = 0. Kích thước mảng size là cố định trong suốt quá trình.
Cập nhật biến lặp: Trong lời gọi đệ quy, index mới là index + 1, current_sum mới là current_sum + arr[index]. Bên trong vòng lặp, chúng ta sẽ cập nhật:
- total_sum = total_sum + arr[current_index];
- current_index = current_index + 1;
Kết quả trả về: Khi vòng lặp kết thúc (current_index bằng size), kết quả là giá trị cuối cùng của total_sum (tương ứng với giá trị trả về ở trường hợp cơ sở return current_sum;).

Áp dụng các bước trên, ta có hàm lặp:

int sum_array_iterative(const int arr[], int size) {
    // Khởi tạo biến lặp từ giá trị ban đầu của tham số đệ quy
    int total_sum = 0;
    int current_index = 0;

    // Vòng lặp thay thế các lời gọi đệ quy
    // Điều kiện lặp là ngược lại của điều kiện cơ sở (current_index == size)
    while (current_index < size) {
        // Cập nhật biến lặp theo cách tham số đệ quy được cập nhật
        total_sum = total_sum + arr[current_index];
        current_index = current_index + 1;
    }

    // Trả về kết quả cuối cùng
    return total_sum;
}

Giải thích: Phiên bản lặp này sử dụng biến total_sum để tích lũy tổng và current_index để duyệt qua mảng. Vòng lặp while tiếp tục cho đến khi current_index đạt đến size, tương tự như cách hàm đệ quy đuôi dừng lại. Mỗi lần lặp, chúng ta cộng phần tử hiện tại vào total_sum và tăng current_index, mô phỏng lại chính xác logic của lời gọi đệ quy đuôi.

Ví dụ 3: Tìm kiếm nhị phân (Binary Search)

Tìm kiếm nhị phân cũng là một giải thuật có thể được viết dưới dạng đệ quy đuôi một cách tự nhiên.

Đệ quy đuôi

Chúng ta cần truyền ranh giới dưới (low) và ranh giới trên (high) của phạm vi tìm kiếm hiện tại.

// Hàm hỗ trợ đệ quy đuôi
int tail_binary_search_helper(const int arr[], int low, int high, int target) {
    // Trường hợp cơ sở 1: Không tìm thấy (khoảng tìm kiếm không hợp lệ)
    if (low > high) {
        return -1; // Trả về -1 nếu không tìm thấy
    }

    int mid = low + (high - low) / 2;

    // Trường hợp cơ sở 2: Tìm thấy
    if (arr[mid] == target) {
        return mid; // Trả về chỉ số nếu tìm thấy
    }
    // Lời gọi đệ quy là thao tác CUỐI CÙNG trong mỗi nhánh
    else if (arr[mid] < target) {
        // Tìm kiếm trong nửa bên phải: low được cập nhật
        return tail_binary_search_helper(arr, mid + 1, high, target);
    } else { // arr[mid] > target
        // Tìm kiếm trong nửa bên trái: high được cập nhật
        return tail_binary_search_helper(arr, low, mid - 1, target);
    }
}

// Hàm wrapper
int binary_search_tail_recursive(const int arr[], int size, int target) {
    // Bắt đầu tìm kiếm trong toàn bộ mảng
    return tail_binary_search_helper(arr, 0, size - 1, target);
}

Giải thích: Hàm nhận vào mảng, ranh giới dưới low, ranh giới trên high, và giá trị target cần tìm. Các trường hợp cơ sở là khi khoảng tìm kiếm không còn hợp lệ (low > high) hoặc khi tìm thấy phần tử tại mid. Quan trọng là trong hai trường hợp gọi đệ quy tiếp theo (arr[mid] < target hoặc arr[mid] > target), lời gọi đệ quy tail_binary_search_helper là thao tác cuối cùng được thực hiện trong nhánh if-else đó. Không có phép tính nào khác sau khi lời gọi đệ quy trả về kết quả.

Biến đổi từ Đệ quy đuôi sang Vòng lặp

Hàm đệ quy đuôi: tail_binary_search_helper(const int arr[], int low, int high, int target) Trường hợp cơ sở: low > high (trả về -1) hoặc arr[mid] == target (trả về mid). Lời gọi đệ quy: tail_binary_search_helper(arr, mid + 1, high, target) hoặc tail_binary_search_helper(arr, low, mid - 1, target).

Tham số thay đổi: low và high. Chúng ta sẽ dùng biến current_low và current_high. target và mảng là cố định.
Điều kiện vòng lặp: Trường hợp cơ sở không tìm thấy là low > high. Điều kiện ngược lại là low <= high. Vòng lặp sẽ là while (current_low <= current_high). Trường hợp cơ sở tìm thấy (arr[mid] == target) sẽ được xử lý bên trong vòng lặp.
Khởi tạo biến lặp: Giá trị ban đầu của low là 0, high là size - 1. Nên current_low = 0, current_high = size - 1.
Cập nhật biến lặp: Bên trong vòng lặp, chúng ta tính mid.
- Nếu arr[mid] < target, thì low mới là mid + 1. Chúng ta cập nhật current_low = mid + 1;.
- Nếu arr[mid] > target, thì high mới là mid - 1. Chúng ta cập nhật current_high = mid - 1;.
Kết quả trả về: Nếu tìm thấy (arr[mid] == target), trả về mid ngay lập tức. Nếu vòng lặp kết thúc mà không tìm thấy (tức là current_low > current_high), trả về -1 (tương ứng với trường hợp cơ sở low > high).

Áp dụng các bước trên, ta có hàm lặp:

int binary_search_iterative(const int arr[], int size, int target) {
    // Khởi tạo biến lặp từ giá trị ban đầu của tham số đệ quy
    int low = 0;
    int high = size - 1;

    // Vòng lặp thay thế các lời gọi đệ quy
    // Điều kiện lặp là ngược lại của trường hợp cơ sở không tìm thấy (low > high)
    while (low <= high) {
        int mid = low + (high - low) / 2; // Tính điểm giữa an toàn

        // Xử lý trường hợp cơ sở tìm thấy
        if (arr[mid] == target) {
            return mid; // Trả về chỉ số nếu tìm thấy
        }
        // Cập nhật biến lặp theo cách tham số đệ quy được cập nhật
        else if (arr[mid] < target) {
            low = mid + 1; // Tìm kiếm trong nửa bên phải
        } else { // arr[mid] > target
            high = mid - 1; // Tìm kiếm trong nửa bên trái
        }
    }

    // Trả về kết quả tương ứng với trường hợp cơ sở không tìm thấy
    return -1; // Không tìm thấy
}

Giải thích: Phiên bản lặp này sử dụng biến low và high để theo dõi khoảng tìm kiếm hiện tại, tương tự như các tham số trong hàm đệ quy. Vòng lặp while (low <= high) tiếp tục miễn là khoảng tìm kiếm còn hợp lệ. Bên trong vòng lặp, chúng ta thực hiện việc kiểm tra phần tử ở giữa và cập nhật low hoặc high để thu hẹp phạm vi tìm kiếm, mô phỏng chính xác hành vi của các lời gọi đệ quy đuôi.

Lợi ích của phiên bản lặp so với đệ quy (khi không có TCO)

Như các ví dụ trên đã cho thấy, việc biến đổi đệ quy đuôi sang vòng lặp là khá trực tiếp. Phiên bản lặp mang lại những lợi ích quan trọng, đặc biệt khi trình biên dịch không hỗ trợ TCO hoặc bạn cần đảm bảo hiệu quả tối đa:

Hiệu quả bộ nhớ vượt trội: Vòng lặp chỉ sử dụng một lượng bộ nhớ stack cố định (cho các biến lặp), không phụ thuộc vào kích thước của đầu vào hoặc độ sâu của "đệ quy" ban đầu. Điều này hoàn toàn loại bỏ nguy cơ Stack Overflow - một vấn đề nghiêm trọng của đệ quy thông thường với các bài toán có kích thước lớn.
Hiệu suất ổn định: Chi phí của một lần lặp thường nhỏ hơn chi phí của một lời gọi hàm (dù là đệ quy hay không). Dạng lặp loại bỏ chi phí quản lý stack frame cho mỗi "bước" tính toán.
Dễ dàng gỡ lỗi: Đôi khi, việc theo dõi luồng thực thi trong một vòng lặp có thể dễ dàng hơn so với theo dõi nhiều cấp độ gọi hàm đệ quy lồng nhau.

Khi nào nên sử dụng đệ quy, đệ quy đuôi và vòng lặp?

Đệ quy thông thường: Phù hợp khi cấu trúc bài toán tự nhiên mang tính đệ quy (ví dụ: duyệt cây, xử lý các cấu trúc dữ liệu định nghĩa đệ quy như danh sách liên kết), và độ sâu đệ quy được kỳ vọng là không quá lớn. Code có thể rất thanh lịch và dễ đọc. Tuy nhiên, cần cẩn trọng với nguy cơ Stack Overflow.
Đệ quy đuôi: Là lựa chọn tốt khi bài toán có thể biểu diễn dưới dạng đệ quy đuôi (nghĩa là lời gọi đệ quy là thao tác cuối cùng). Nếu trình biên dịch hỗ trợ TCO, bạn sẽ nhận được hiệu quả của vòng lặp mà vẫn giữ được "dáng dấp" đệ quy trong code (có thể dễ đọc hơn đối với một số người). Nó cũng là bước trung gian lý tưởng nếu bạn định biến đổi sang lặp thủ công.
Vòng lặp (sau khi biến đổi từ đệ quy đuôi): Đây là lựa chọn an toàn và hiệu quả nhất về bộ nhớ, đặc biệt quan trọng với các bài toán có thể có đầu vào rất lớn hoặc khi bạn làm việc trong môi trường mà TCO không được đảm bảo. Mặc dù code có thể trông kém "đệ quy" hơn, nó loại bỏ rủi ro Stack Overflow và thường có hiệu suất tốt.

Bài tập ví dụ:

Nhóm Quốc Gia

Trong một ngày nọ, FullHouse Dev đang dạo chơi trong làng thì gặp một nhóm người đang ngồi thành hàng. Họ quyết định đặt ra một câu đố thú vị về việc đếm số lượng quốc gia trong nhóm người này.

Bài toán

Có \(N\) người đang ngồi thành một hàng, được đánh số từ 1 đến \(N\). Mỗi người được hỏi cùng một câu hỏi: "Có bao nhiêu người cùng quốc gia với bạn trong nhóm?". Những câu trả lời có thể đúng hoặc sai. Biết rằng những người cùng quốc gia luôn ngồi cạnh nhau.

Nếu tất cả các câu trả lời đều đúng, hãy xác định số lượng quốc gia khác nhau có trong nhóm. Ngược lại, in ra "Invalid Data".

INPUT FORMAT:

Dòng đầu tiên chứa một số nguyên - số lượng test case
Mỗi test case gồm 2 dòng:
- Dòng thứ nhất chứa số nguyên \(N\) - tổng số người trong nhóm
- Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách, số thứ \(i\) là câu trả lời của người thứ \(i\)

OUTPUT FORMAT:

Với mỗi test case, in ra một dòng chứa một số nguyên duy nhất thể hiện số lượng quốc gia khác nhau, hoặc "Invalid Data" nếu dữ liệu không hợp lệ.

Ràng buộc:

\(1 \leq N \leq 10^5\)

Ví dụ

INPUT

4
2
1 1
2
1 3
7
1 1 2 2 3 3 3
7
7 7 7 7 7 7 7

OUTPUT

2
Invalid Data
4
1

Giải thích

Test case 1: Có hai người đến từ hai quốc gia khác nhau.
Test case 2: Chỉ có hai người nhưng người thứ hai lại nói có ba người cùng quốc gia với mình, vì vậy đây là dữ liệu không hợp lệ.
Test case 3: Có bốn nhóm người từ các quốc gia khác nhau.
Test case 4: Tất cả bảy người đều đến từ cùng một quốc gia. Đây là hướng dẫn giải bài "Nhóm Quốc Gia" bằng C++ một cách ngắn gọn:

Ý tưởng chính: Dựa vào ràng buộc "những người cùng quốc gia luôn ngồi cạnh nhau", ta biết rằng nhóm người được chia thành các khối liên tiếp, mỗi khối là một quốc gia. Câu trả lời của bất kỳ ai trong một khối kích thước S phải là S. Ta có thể duyệt qua hàng người, xác định từng khối quốc gia một cách tuần tự dựa vào câu trả lời của người đầu tiên trong khối, và kiểm tra tính hợp lệ của khối đó.
Thuật toán:
- Khởi tạo một biến num_countries = 0 để đếm số quốc gia.
- Khởi tạo một biến current_pos = 0 để theo dõi vị trí người hiện tại (sử dụng chỉ mục 0-based).
- Sử dụng một vòng lặp while chạy khi current_pos < N.
- Bên trong vòng lặp:
  - Tăng num_countries lên 1 (vì current_pos đánh dấu sự bắt đầu của một quốc gia mới).
  - Lấy câu trả lời của người tại current_pos. Gọi giá trị này là block_size. block_size = answers[current_pos].
  - Kiểm tra tính hợp lệ cho khối hiện tại:
    - block_size phải lớn hơn 0.
    - Khối này bắt đầu từ current_pos và có kích thước block_size. Vị trí kết thúc của khối là current_pos + block_size - 1. Kiểm tra xem current_pos + block_size có vượt quá N hay không. Nếu current_pos + block_size > N, dữ liệu không hợp lệ.
    - Kiểm tra xem tất cả những người trong khối này (từ current_pos đến current_pos + block_size - 1) có cùng câu trả lời là block_size hay không. Duyệt từ i = current_pos đến current_pos + block_size - 1 và kiểm tra answers[i] == block_size. Nếu có bất kỳ người nào trả lời khác, dữ liệu không hợp lệ.
  - Nếu bất kỳ kiểm tra tính hợp lệ nào ở trên thất bại, dừng xử lý test case này, đánh dấu là "Invalid Data".
  - Nếu tất cả các kiểm tra tính hợp lệ đều thành công, di chuyển current_pos về phía trước bằng cách cộng thêm block_size: current_pos += block_size.
- Sau khi vòng lặp while kết thúc:
  - Nếu trong quá trình duyệt không có lỗi tính hợp lệ nào xảy ra VÀ current_pos kết thúc bằng N (tức là ta đã duyệt hết N người một cách chính xác bằng các khối quốc gia), in ra num_countries.
  - Ngược lại (có lỗi xảy ra hoặc current_pos != N), in ra "Invalid Data".
Xử lý nhiều test case: Bọc toàn bộ logic trên trong một vòng lặp chạy số lần bằng số lượng test case đọc từ dòng đầu tiên.

Lưu ý quan trọng:

Sử dụng kiểu dữ liệu phù hợp cho N và các câu trả lời (int là đủ).
Chú ý sử dụng chỉ mục mảng (0-based trong C++).
Đảm bảo xử lý trường hợp dữ liệu không hợp lệ một cách nhất quán (ví dụ: sử dụng một biến boolean is_invalid).
Độ phức tạp thời gian của giải pháp này là O(N) cho mỗi test case vì mỗi người và câu trả lời của họ chỉ được kiểm tra một vài lần cố định.

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

Comments

There are no comments at the moment.