Editorial for ptit003: Khôi phục dãy số

Hiểu bài toán

Cho một hoán vị độ dài n bị đánh mất. Bob chỉ nhớ các hiệu $pi - p{i-1}$ (từ $i=2$ đến $n$). Nhiệm vụ là khôi phục lại hoán vị ban đầu.

Quy luật: Gọi các hiệu là $q1, q2, ..., q{n-1}$. Ta có: $p2 - p1 = q1 \implies p2 = p1 + q1$ $p3 - p2 = q2 \implies p3 = p2 + q2 = p1 + q1 + q2$ ... $pi = p1 + \sum{j=1}^{i-1} qj$

Như vậy, các phần tử của dãy số đều phụ thuộc vào giá trị $p1$. Để dãy là một hoán vị của $1..n$, các giá trị $pi$ phải là các số nguyên dương phân biệt nằm trong khoảng $[1, n]$.

Yêu cầu: Nếu có nhiều cách chọn $p_1$ thỏa mãn, in ra dãy có tổng các phần tử nhỏ nhất.

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

Cách Tính tổng và kiểm tra (Phương pháp 1)

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

int main(){
    int n;
    scanf("%d",&n);
    int c[n+1];
    for(int i=0;i<=n;i++){
        c[i]=0;
    }
    int d[n];
    d[0]=0;
    for(int i=1;i<n;i++){
        scanf("%d",&d[i]);
        d[i]+=d[i-1];
    }
    int min=d[0];
    for(int i=1;i<n;i++){
        if(d[i]<min) min=d[i];
    }
    int a[n];
    a[0]=1-min;
    if (a[0] < 1 || a[0] > n) {
        printf("-1");
        return 0;
    }
    c[a[0]]=1;
    for(int i=1;i<n;i++){
        a[i]=a[0]+d[i];
        if(a[i]<1||a[i]>n){
            printf("-1");
            return 0;
        }
        if(c[a[i]]==1){
            printf("-1");
            return 0;
        }
        c[a[i]]=1;
    }
    for(int i=0;i<n;i++){
        printf("%d ",a[i]);
    }
}

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

Cách tiếp cận này tính toán dãy tổng tiền tố của các hiệu số (mảng d).

• $d[i]$ lưu tổng các hiệu số từ đầu đến vị trí thứ $i$. Do đó $pi = p1 + d[i]$.
• Để tổng dãy số nhỏ nhất, ta cần $p_1$ nhỏ nhất có thể.
• Vì $pi \ge 1$, nên $p1 + d[i] \ge 1 \implies p_1 \ge 1 - d[i]$ với mọi $i$.
• Do đó, $p1$ nhỏ nhất thỏa mãn là $p1 = 1 - \min(d)$.
• Sau khi xác định $p_1$, ta xây dựng dãy $p$ và kiểm tra xem các phần tử có nằm trong $[1, n]$ và có bị trùng lặp không bằng mảng đánh dấu.
• Nếu kiểm tra thất bại, in -1.

Cách Tối ưu với Kiểm tra Duyệt (Phương pháp 2)

#include <stdio.h>
#include <limits.h>

int main() {
    int n;
    scanf("%d", &n);
    int a[100005];
    long long prefix[100005];
    int used[100005] = {0};
    for (int i = 0; i < n - 1; i++) {
        scanf("%d", &a[i]);
    }
    prefix[0] = 0;
    long long min_val = 0;
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] + a[i - 1];
        if (prefix[i] < min_val) {
            min_val = prefix[i];
        }
    }
    long long offset = 1 - min_val;
    int ok = 1;
    for (int i = 0; i < n; i++) {
        long long value = prefix[i] + offset;
        if (value < 1 || value > n || used[value]) {
            ok = 0;
            break;
        }
        used[value] = 1;
    }

    if (!ok) {
        printf("-1\n");
    } else {
        for (int i = 0; i < n; i++) {
            printf("%lld ", prefix[i] + offset);
        }
    }
    return 0;
}

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

Giống Phương pháp 1 về logic tính toán.

• Tính dãy tổng tiền tố prefix.
• Tìm giá trị min_val của dãy tổng tiền tố để xác định offset (giá trị khởi đầu $p_1$).
• Kiểm tra tính hợp lệ của dãy số mới tạo ra.
• Cách này tách biệt logic tính toán và kiểm tra rõ ràng hơn.

Cách Tối ưu với Kiểm tra Trực tiếp (Phương pháp 3)

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
int main(){
    int n,i,min;
    int a[100005],b[100005],dem[100005];
    scanf("%d",&n);
    for (i=1;i<=n-1;i++){
        scanf("%d",&a[i]);
        if (a[i]<1-n || a[i]>n-1){
            printf("-1");
            return 0;
        }
}
    b[1]=1;
    min=1;
    for (i=2;i<=n;i++){
        b[i]=b[i-1]+a[i-1];
        if (b[i]<min) min=b[i];
    }
    for (i=1;i<=n;i++){
        b[i]=b[i]-(min-1);
        if (b[i]>n){
            printf("-1");
            return 0;            
        }
        dem[b[i]]++;
    }
    for (i=1;i<=n;i++){
        if (dem[i]!=1){
            printf("-1");
            return 0;
        }
    }
    for (i=1;i<=n;i++)
        printf("%d ",b[i]);
    return 0;
}

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

Phương pháp này cũng dựa trên logic tổng tiền tố.

• Giả sử $p_1=1$, tính toán dãy số.
• Tìm giá trị nhỏ nhất min của dãy này.
• Dịch chuyển toàn bộ dãy lên trên sao cho giá trị nhỏ nhất trở thành 1. Phép toán là trừ đi (min - 1).
• Kiểm tra xem sau khi dịch chuyển, các giá trị có bị vượt quá $n$ không.
• Sử dụng mảng dem (đếm tần suất) để kiểm tra xem các số có bị trùng lặp không. Nếu dem[i] != 1 thì có trùng lặp hoặc thiếu số.
• Đây là cách kiểm tra khá trực quan và hiệu quả.

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

Bài học kinh nghiệm

• Tất cả các phần tử trong dãy đều có thể được biểu diễn dưới dạng $pi = p1 + Si$, trong đó $Si$ là tổng các hiệu số từ đầu đến $i-1$ (tính với $S_1 = 0$).
• Để tổng các phần tử trong dãy nhỏ nhất, ta cần chọn giá trị khởi đầu $p1$ là nhỏ nhất có thể. Xét điều kiện $pi \ge 1 \implies p1 + Si \ge 1 \implies p1 \ge 1 - Si$. Do đó $p1 = 1 - \min(Si)$.
• Sau khi xác định được $p_1$, việc còn lại chỉ là xây dựng dãy và kiểm tra xem nó có thực sự là một hoán vị (các số phân biệt và chạy từ 1 đến n) hay không.

Lỗi thường gặp

• Lỗi số nguyên (Integer Overflow): Khi tính tổng tiền tố, các giá trị có thể vượt quá giới hạn của int nếu $n$ lớn. Nên dùng long long cho các biến tính toán tổng.
• Quên kiểm tra trùng lặp: Sau khi điều chỉnh dãy số để có giá trị dương, ta cần kiểm tra chắc chắn các số trong dãy là duy nhất. Việc chỉ kiểm tra phạm vi $[1, n]$ là chưa đủ.
• Lỗi truy cập mảng: Khi n=1, không có input q_i, cần xử lý đúng để không lỗi.