Editorial for ptit021: Linh kiện điện tử

Hiểu bài toán

Bài toán yêu cầu tìm số lượng linh kiện bị mất ít nhất. Grenore đánh số linh kiện liên tiếp từ x đến x+n (với n là số lượng ban đầu). Kẻ trộm lấy đi k linh kiện (0 ≤ k < n), để lại n - k linh kiện. Ta được danh sách các linh kiện còn lại (kích thước n). Ta cần tìm số lượng linh kiện bị mất (k).

Giả sử Grenore đánh số từ x đến x+n-1. Nếu ta biết x và n, số linh kiện bị mất là tổng số đánh số trừ đi số còn lại: n - n = 0? Không, n là số lượng ban đầu. Nếu ta có m linh kiện còn lại (trong input là n, tạm gọi là m để tránh nhầm), thì số bị mất là (khoảng giá trị bao phủ) - m.

Tuy nhiên, Grenore chỉ đánh số liên tiếp. Do đó, các linh kiện còn lại nằm trong một khoảng [min, max]. Nếu Grenore đánh số từ x đến x + (số lượng ban đầu) - 1, thì khoảng này phải nằm trong [min, max] hoặc [min, max] nằm trong khoảng đánh số.

Vì Grenore đánh số liên tiếp và không có số thừa, số lượng ban đầu là một ẩn số. Tuy nhiên, Grenore sẽ đánh số liên tiếp từ x đến x + (số lượng ban đầu) - 1. Nếu ta có các số còn lại, khoảng giá trị bao phủ là từ số nhỏ nhất (min) đến số lớn nhất (max).

Để số lượng linh kiện bị mất là ít nhất, Grenore phải chọn x sao cho khoảng đánh số bao phủ ít nhất các số còn lại.

Xét ví dụ: Input là 4 số [10, 13, 12, 8]. Sắp xếp lại: [8, 10, 12, 13]. Khoảng giá trị bao phủ: 8 đến 13. Tổng số lượng đánh số trong khoảng này: 13 - 8 + 1 = 6. Số còn lại: 4. Số bị mất: 6 - 4 = 2.

Logic:

1. Sắp xếp các mảng a.
2. Khoảng giá trị các linh kiện còn lại là từ a[0] đến a[n-1].
3. Grenore đánh số liên tiếp. Để che phủ các số còn lại, dải số đánh số ít nhất phải bao gồm từ a[0] đến a[n-1].
4. Do đó, dải số đánh số là [a[0], a[n-1]].
5. Số lượng đánh số trong dải này là (a[n-1] - a[0] + 1).
6. Số lượng còn lại là n.
7. Số lượng bị mất là (a[n-1] - a[0] + 1) - n.

Lưu ý: Trong mô tả bài toán, 'n' dòng đầu là số lượng linh kiện còn lại. Các solution dùng biến n để lưu kích thước mảng a.

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

Cách Hash Map / Mảng đánh dấu (Frequency Array)

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int a[1000001];

int main() {
    int n;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        a[arr[i]] = 1;
    }
    int x = arr[0], xn = arr[0];
    for (int i = 0; i < n; i++) {
        if (arr[i] < x) {
            x = arr[i];
        } else if (arr[i] > xn) {
            xn = arr[i];
        }
    }
    int count = 0;
    for (int i = x; i <= xn; i++) {
        if (a[i] == 0) {
            count++;
        }
    }
    printf("%d", count);
    return 0;
}

• Time Complexity: O(Range) hoặc O(max_value)
• Space Complexity: O(Range) hoặc O(max_value)

Approach này sử dụng một mảng đánh dấu (một dạng Hash Map đơn giản) để lưu các vị trí đã xuất hiện.

1. Đọc dữ liệu và đánh dấu các vị trí có trong mảng a.
2. Tìm giá trị nhỏ nhất (min) và lớn nhất (max) trong danh sách.
3. Duyệt từ min đến max, đếm số lượng vị trí chưa được đánh dấu. Đây là cách tiếp cận trực quan nhưng tốn bộ nhớ và thời gian nếu khoảng giá trị (max - min) lớn, kể cả khi n nhỏ. Tuy nhiên, với ràng buộc a_i <= 10^6, nó vẫn chạy được.

Cách Sắp xếp và Tính khoảng cách

#include<stdio.h>
#include<stdlib.h>

int cmp(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int n;    scanf("%d", &n);
    int a[n];
    for(int i=0; i<n; i++)    scanf("%d", &a[i]);
    qsort(a, n, sizeof(int), cmp);
    int cnt = 0;
    for(int i=1; i<n; i++){
        int x = a[i] - a[i-1];
        if(x>1)    cnt += x - 1;
    }
    printf("%d\n", cnt);
    return 0;
}

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

Cách này dựa trên giả định rằng Grenore đánh số liên tiếp trong khoảng từ số nhỏ nhất đến số lớn nhất của các linh kiện còn lại.

1. Sắp xếp mảng a.
2. Tính tổng các khoảng trống giữa các phần tử liên tiếp. Khoảng trống giữa a[i] và a[i-1] là a[i] - a[i-1] - 1.
3. Tổng số bị mất chính là tổng các khoảng trống này. Ví dụ: [8, 10, 12, 13]. Khoảng trống: (10-8-1)=1, (12-10-1)=1, (13-12-1)=0. Tổng = 2.

Cách Tối ưu (Tìm Min/Max)

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int a[n];

    // Đọc các linh kiện còn lại
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    // Tìm linh kiện có số hiệu nhỏ nhất và lớn nhất
    int min_val = a[0];
    int max_val = a[0];

    for (int i = 1; i < n; i++) {
        if (a[i] < min_val) min_val = a[i];
        if (a[i] > max_val) max_val = a[i];
    }

    // Tổng số linh kiện ban đầu từ min_val đến max_val
    int total_count = max_val - min_val + 1;

    // Số linh kiện bị mất là tổng số linh kiện ban đầu trừ đi số linh kiện còn lại
    int lost_count = total_count - n;

    printf("%d\n", lost_count);

    return 0;
}

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

Đây là giải pháp tối ưu nhất. Logic: Grenore đánh số liên tiếp. Để lấy ít nhất số bị mất, dải số đánh số phải bao gồm chính xác các số từ nhỏ nhất đến lớn nhất trong danh sách còn lại.

1. Tìm min và max của mảng a.
2. Số lượng đánh số trong dải này là max - min + 1.
3. Số lượng còn lại là n.
4. Số lượng bị mất là (max - min + 1) - n. Độ phức tạp là O(N) để tìm min/max, và O(1) bộ nhớ.

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

Bài học kinh nghiệm

• Vấn đề có thể được coi là tìm số lượng số nguyên thiếu trong một dải số liên tiếp [min, max] bao gồm tất cả các phần tử của mảng.
• Giả định rằng Grenore chọn dải số đánh số sao cho các linh kiện còn lại nằm trong dải đó và dải số này là nhỏ nhất có thể (từ min đến max) là chìa khóa.
• Số lượng bị mất = (Số lượng số trong khoảng từ min đến max) - (Số lượng phần tử trong mảng).

Lỗi thường gặp

• Lầm tưởng rằng cần phải tìm giá trị x (giá trị bắt đầu đánh số) một cách tường minh. Thực tế, ta chỉ cần khoảng giá trị bao phủ các phần tử còn lại.
• Bỏ qua việc sắp xếp hoặc tìm min/max chính xác nếu chỉ duyệt mảng một cách ngẫu nhiên.
• Lỗi tràn số nếu tính toán trên các biến int với giá trị lớn (dù trong bài này giá trị 10^6 khá an toàn cho int).