Hướng dẫn giải của Chuỗi hạt bồ đề


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, hieuochimchim

Editorial for ptit009: Chuỗi hạt bồ đề

Hiểu bài toán

Bài toán yêu cầu tìm số bước tối thiểu để biến đổi n chuỗi hạt thành một chuỗi giống hệt nhau bằng cách thực hiện thao tác 'dời hạt từ đầu về cuối' (cyclic shift). Mỗi bước dời, ký tự đầu tiên được chuyển xuống cuối chuỗi. Nếu không thể biến đổi tất cả chuỗi về cùng một chuỗi, output là -1.

Ví dụ: "ryuu" có thể trở thành "yuur" sau 1 bước (dời 'r' xuống cuối).

Giả sử chuỗi đích là S. Với mỗi chuỗi Ai ban đầu, có thể có nhiều cách dời để được S. Nếu ta chọn S là một trong các chuỗi ban đầu, số bước để biến đổi chuỗi Aj thành S là số lần dời cần thiết để đưa Aj về S. Số bước này tương ứng với độ lệch chu kỳ (cyclic shift offset) giữa Aj và S.

Đề bài yêu cầu chọn một chuỗi đích (không nhất thiết phải là chuỗi ban đầu, nhưng kết quả sẽ là tối ưu nếu chọn một trong các chuỗi ban đầu làm đích) sao cho tổng số bước biến đổi của các chuỗi còn lại về nó là nhỏ nhất.

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

Cách Brute Force (Duyệt chuỗi đích)
#include <stdio.h>
#include <string.h>
#include <limits.h>

int main() {
    int n;
    scanf("%d", &n);
    char s[55][55];
    for (int i = 0; i < n; i++) {
        scanf("%s", s[i]);
    }
    int len = strlen(s[0]);
    int min_total = INT_MAX;
    int possible = 0;

    // Duyệt từng chuỗi làm chuỗi đích
    for (int i = 0; i < n; i++) {
        int current_total = 0;
        int ok = 1;
        for (int j = 0; j < n; j++) {
            if (i == j) continue;

            // Tạo chuỗi kép để kiểm tra cyclic shift
            char double_s[110];
            strcpy(double_s, s[j]);
            strcat(double_s, s[j]);

            // Tìm vị trí của chuỗi đích trong chuỗi kép
            char *ptr = strstr(double_s, s[i]);
            if (ptr == NULL) {
                ok = 0;
                break;
            }
            int shift = (int)(ptr - double_s);
            // Chỉ chấp nhận nếu shift < len (để tránh lấy kết quả từ phần thứ hai của chuỗi kép không cần thiết)
            // và phải khớp đúng độ dài len
            if (shift >= len || strncmp(ptr, s[i], len) != 0) {
                 ok = 0;
                 break;
            }
            current_total += shift;
        }
        if (ok) {
            possible = 1;
            if (current_total < min_total) {
                min_total = current_total;
            }
        }
    }

    if (!possible) printf("-1");
    else printf("%d", min_total);
    return 0;
}
  • Time Complexity: O(n^2 * L^2)
  • Space Complexity: O(L)

Phương pháp này giả định rằng chuỗi đích cuối cùng phải là một trong các chuỗi ban đầu (điều này luôn đúng để tối thiểu hóa số bước).

  1. Duyệt qua từng chuỗi s[i] trong danh sách để thử làm chuỗi đích.
  2. Với mỗi chuỗi đích s[i], tính tổng số bước cần thiết để biến đổi tất cả các chuỗi khác s[j] về s[i].
  3. Để biến đổi s[j] thành s[i], ta cần tìm số lần dời (shift) cần thiết. Ta ghép s[j] với chính nó thành một chuỗi kép tmp.
  4. Nếu s[i] xuất hiện trong tmp, vị trí xuất hiện chính là số bước dời.
  5. Nếu có bất kỳ chuỗi s[j] nào không thể biến đổi thành s[i], thì s[i] không thể là chuỗi đích chung.
  6. Cập nhật tổng số bước nhỏ nhất.
Cách Optimized Brute Force
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>

int calculate_shift(const char *src, const char *dest, int len) {
    char buffer[102];
    strcpy(buffer, src);
    strcat(buffer, src);
    for (int k = 0; k < len; k++) {
        if (strncmp(buffer + k, dest, len) == 0) {
            return k;
        }
    }
    return -1;
}

int main() {
    int n;
    scanf("%d", &n);
    char s[55][55];
    for (int i = 0; i < n; i++) scanf("%s", s[i]);
    int len = strlen(s[0]);
    int min_total = INT_MAX;
    int possible = 0;

    // Kiểm tra tính tương đồng trước (tùy chọn nhưng cần thiết cho logic)
    // Đảm bảo tất cả chuỗi đều thuộc cùng một chu kỳ
    // Logic kiểm tra trong vòng lặp dưới đã đủ

    for (int i = 0; i < n; i++) {
        int total = 0;
        int ok = 1;
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            int shift = calculate_shift(s[j], s[i], len);
            if (shift == -1) {
                ok = 0;
                break;
            }
            total += shift;
        }
        if (ok) {
            possible = 1;
            if (total < min_total) min_total = total;
        }
    }

    if (!possible) printf("-1");
    else printf("%d", min_total);
    return 0;
}
  • Time Complexity: O(n^2 * L)
  • Space Complexity: O(L)

Đây là phiên bản tối ưu hơn của Brute Force. Thay vì dùng strstr (tùy thuộc thư viện, có thể chậm), ta tự viết vòng lặp so sánh thủ công.

  1. Tạo chuỗi kép src + src.
  2. Duyệt k từ 0 đến len-1 để kiểm tra xem dest có nằm bắt đầu từ vị trí k của chuỗi kép không.
  3. Nếu khớp, trả về k.
  4. Nếu duyệt hết mà không tìm thấy, trả về -1.

Cách này đảm bảo độ phức tạp ổn định O(n^2 * L).

Cách Direct Calculation (Most Optimal)
#include <stdio.h>
#include <string.h>
#include <limits.h>

int n;
char s[55][55];
int len;

// Kiểm tra xem các chuỗi có thể biến đổi về nhau không
int check_compatibility() {
    char temp[110];
    // Lấy chuỗi đầu tiên làm tham chiếu
    strcpy(temp, s[0]);
    strcat(temp, s[0]);

    for (int i = 1; i < n; i++) {
        if (strstr(temp, s[i]) == NULL) return 0;
    }
    return 1;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%s", s[i]);
    len = strlen(s[0]);

    // Bước 1: Kiểm tra tính khả thi
    if (!check_compatibility()) {
        printf("-1");
        return 0;
    }

    int min_total = INT_MAX;

    // Bước 2: Duyệt qua tất cả các vị trí shift có thể của chuỗi đầu tiên làm chuỗi đích
    // Thay vì chỉ chọn 1 trong n chuỗi, ta xét tất cả các biến thể cyclic shift của chuỗi đầu tiên
    // (hoặc đơn giản là duyệt tất cả chuỗi ban đầu cũng đủ, nhưng duyệt all shifts đảm bảo tìm đúng min)
    // Thực tế, chỉ cần duyệt các chuỗi ban đầu là đủ vì độ ưu tiên.

    for (int i = 0; i < n; i++) {
        int current_sum = 0;
        for (int j = 0; j < n; j++) {
            if (i == j) continue;

            // Tính offset giữa s[j] và s[i]
            // Tạo s[j] + s[j]
            char temp_concat[110];
            strcpy(temp_concat, s[j]);
            strcat(temp_concat, s[j]);

            // Tìm s[i] trong s[j]+s[j]
            // Chỉ cần tìm vị trí đầu tiên (< len)
            int offset = -1;
            for (int k = 0; k < len; k++) {
                if (strncmp(temp_concat + k, s[i], len) == 0) {
                    offset = k;
                    break;
                }
            }
            current_sum += offset;
        }
        if (current_sum < min_total) min_total = current_sum;
    }

    printf("%d", min_total);
    return 0;
}
  • Time Complexity: O(n^2 * L)
  • Space Complexity: O(L)

Đây là phương pháp trực tiếp và tối ưu nhất.

  1. Kiểm tra tính khả thi: Kiểm tra xem tất cả các chuỗi có phải là các cyclic shift của nhau không. Có thể làm bằng cách ghép chuỗi đầu tiên với chính nó và kiểm tra xem các chuỗi khác có nằm trong đó không. Nếu có chuỗi không khớp, in -1.

  2. Tìm số bước tối thiểu:

    • Giả sử chuỗi đích là s[i] (một trong các chuỗi ban đầu).
    • Với mỗi chuỗi s[j], số bước để biến đổi s[j] về s[i] là độ lệch chu kỳ giữa chúng.
    • Để tính độ lệch, ta ghép s[j] với s[j] thành tmp. Nếu s[i] nằm trong tmp tại vị trí k, thì s[j] cần k bước dời để thành s[i].
    • Tong số bước để biến đổi tất cả về s[i] là tổng các k này.
    • Ta lặp qua tất cả s[i] để tìm tổng nhỏ nhất.

Lưu ý: Bài này có thể tối ưu hơn bằng cách chuẩn hóa chuỗi, nhưng với n, L <= 50, cách này hoàn toàn đủ nhanh.

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

Cách tiếp cận Time Space Tên
1 O(n^2 * L^2) O(L) Brute Force (Duyệt chuỗi đích)
2 O(n^2 * L) O(L) Optimized Brute Force
3 O(n^2 * L) O(L) Direct Calculation (Most Optimal)

Bài học kinh nghiệm

  • Thao tác 'dời đầu về cuối' tạo thành nhóm xoay chu kỳ (cyclic group). Hai chuỗi có thể biến đổi cho nhau iff chúng có cùng ký tự và là các xoay của nhau.
  • Chuỗi đích tối ưu để tối thiểu hóa tổng số bước luôn là một trong các chuỗi ban đầu.
  • Để tính số bước dời giữa chuỗi A và chuỗi B, ta ghép A với chính nó (A+A) và tìm B trong chuỗi ghép đó. Vị trí tìm thấy chính là số bước.

Lỗi thường gặp

  • Quên kiểm tra xem các chuỗi có thực sự biến đổi được cho nhau không. Nếu chỉ đơn giản tìm offset mà không kiểm tra, có thể bỏ qua trường hợp không tìm thấy (offset = -1).
  • Lỗi truy cập mảng khi sử dụng strcat vào mảng chưa đủ kích thước (cần ít nhất 2*L+1)
  • Sai lệch khi đếm số bước (ví dụ: dời 1 lần để từ 'ab' thành 'ba', offset tìm được là 1, đúng).

Bình luận

Please read the guidelines before commenting.


Không có bình luận tại thời điểm này.