Chuỗi hạt bồ đề (PTIT009)

Nguồn: LuyenCode (PTIT009) Độ khó: Trung bình Vét cạn Xâu Đếm phân phối

Đề bài

PTIT009 – Chuỗi hạt bồ đề

Trong chuyến đi khám phá thế giới của mình, Grenore muốn tìm hiểu thêm về văn hóa phương Đông. Cậu được biết rằng để tìm hiểu văn hóa phương Đông một cách nhanh nhất, người ta sẽ đi đến những ngôi chùa. Khi Grenore đến nơi, thứ duy nhất làm cậu thích thú là những chuỗi hạt bồ đề, các chuỗi hạt bồ đề khi mới nhìn thoáng qua, chúng có vẻ khác nhau, nhưng thực chất đó chỉ là sự thay đổi trong thứ tự của chuỗi hạt.

Ví dụ như chuỗi hạt có chữ "ryuu" và "yuur" là như nhau, chỉ có một điều duy nhất là hạt chữ "r" từ vị trí đầu bị di chuyển xuống cuối. Bằng cách di chuyển này, từ các chuỗi hạt giống nhau, ta có thể tạo ra các chuỗi hạt khác nhau.

Grenore cực kỳ thấy hứng thú với điều này, cậu chọn ra $n$ chuỗi hạt, và kiểm tra xem liệu chúng có thể đưa về một dãy giống hệt nhau hay không (các hạt chỉ có thể di chuyển từ đầu về cuối, vì các nhà sư cho rằng di chuyển hạt từ cuối về đầu là xúc phạm thần linh) với số bước ít nhất.

Dữ liệu vào:

• Dòng đầu tiên gồm một số $n$ $(1 \le n \le 50)$ là số chuỗi hạt bồ đề mà Grenore đã lấy.
• $n$ dòng tiếp theo, mỗi dòng là một xâu chỉ gồm các chữ cái tiếng Anh, viết thường, biểu thị một chuỗi hạt.

Giới hạn:

• Các xâu đều có cùng một kích thước, mỗi xâu không có quá 50 ký tự $(1 \le |s| \le 50)$.

Dữ liệu ra: Gồm một số nguyên duy nhất là số bước biến đổi để các chuỗi hạt trở nên giống nhau, nếu không thể biến đổi, in ra -1.

Input #1

2
ryuu
yuur

Output #1

1

Input #2

2
abcdef
abcdee

Output #2

-1

Lời mở đầu

Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy qua tin nhắn. Tin rằng sẽ có giá trị với nhiều bạn nên mình viết lại thành bài giải đầy đủ để các bạn tham khảo nhen. Hy vọng mang đến được giá trị cho các bạn 😇.

Giải thích lại đề cho bạn nào chưa hiểu: ta có $n$ chuỗi, mỗi bước được chọn một chuỗi bất kỳ và đem ký tự đầu tiên của nó xuống cuối. Hỏi cần ít nhất bao nhiêu bước (tính tổng trên tất cả các chuỗi) để $n$ chuỗi trở nên giống hệt nhau.

• Ví dụ 1: "ryuu" đem chữ "r" xuống cuối thành "yuur", giống chuỗi thứ hai ⇒ chỉ cần 1 bước.
• Ví dụ 2: "abcdef" có chữ "f", còn "abcdee" không có chữ "f" mà lại có 2 chữ "e". Xoay kiểu gì cũng không thêm/bớt được ký tự nào ⇒ không bao giờ giống nhau được ⇒ in -1.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào để nhảy tới:

Cách 1Vét cạn (duyệt trâu) chọn chuỗi gốc · O(n² · |s|²)

Cách 1Vét cạn chọn chuỗi gốc – O(n² · |s|²)

Bài này mình gợi ý cho em học viên đúng một câu: dùng duyệt trâu, xét tất cả mọi trường hợp có thể có. "Duyệt trâu" nghe hơi lạ tai nhưng nó chính là vét cạn đó các bạn, tiếng Anh là brute force. Dân trong ngành hay gọi bằng thuật ngữ duyệt trâu, các bạn cũng nên làm quen đi 😄.

Tại sao dám vét cạn? Vì dữ liệu quá nhỏ: tối đa chỉ $50$ chuỗi, mỗi chuỗi dài tối đa $50$ ký tự. Còn vét cạn ra sao thì mình đi từng ý nhé.

Mỗi chuỗi có bao nhiêu trạng thái?

Mỗi chuỗi chỉ được quyền đem ký tự ở đầu về cuối. Ví dụ chuỗi ban đầu là "12345" thì nó có tất cả các trạng thái:

k = 0: 12345k = 1: 23451k = 2: 34512k = 3: 45123k = 4: 51234

Tức là có đúng Length trạng thái với Length là độ dài chuỗi. Xoay thêm lần nữa (k = 5) thì lại quay về "12345" như ban đầu, nên không cần xét tiếp. Trạng thái sau $k$ bước chính là s.substr(k) + s.substr(0, k): phần từ vị trí $k$ trở đi, nối với $k$ ký tự đầu.

Xét trước khi nào chắc chắn in -1

Rõ ràng một điều là $n$ chuỗi đều phải có số lượng của từng ký tự bằng nhau. Ví dụ chuỗi thứ nhất có 3 chữ a, 2 chữ b, 4 chữ c thì các chuỗi còn lại cũng phải có đúng 3 chữ a, 2 chữ b, 4 chữ c như vậy, có thể nằm ở vị trí khác nhưng phải đủ số lượng ấy. Nếu có một chuỗi nào chỉ có 1 chữ a hay không có chữ b thì kết luận -1 ngay, bởi phép biến đổi chỉ là đem từ đầu về cuối, nó không làm thêm hay bớt ký tự nào cả.

Trong code, mỗi chuỗi có một mảng đếm check[i] kích thước 123 (mã ASCII của 'z' là 122), check[i][c] là số lần ký tự c xuất hiện trong chuỗi thứ $i$ (kỹ thuật đếm phân phối). Sau đó so sánh check[i] với check[i - 1] cho mọi $i$ là biết ngay.

Cách khác: sắp xếp rồi so sánh

Em học viên có đề xuất ý: sắp xếp từng chuỗi rồi so sánh, khác nhau thì chắc chắn -1. Ý này đúng, nhưng nhớ là không được sắp xếp trên chuỗi gốc nha, vì mình còn phải xử lý xoay chuỗi sau đó nữa. Sắp xếp làm đổi thứ tự thì sai luật (chỉ được đem ký tự ở đầu về cuối). Bản Python bên dưới dùng đúng ý này: sorted(a[i]) tạo ra một danh sách mới đã sắp, chuỗi gốc vẫn giữ nguyên.

Tìm số bước ít nhất: chọn từng chuỗi làm gốc

Xét tất cả tình huống có thể xảy ra: lần lượt chọn từng chuỗi làm gốc và cố gắng biến đổi tất cả các chuỗi còn lại thành chuỗi gốc đó. Với mỗi chuỗi, vét cạn mọi khả năng biến đổi của nó ($k = 0, 1, \ldots, \text{Length} - 1$), đến khi nào trùng thì dừng và cộng $k$ vào tổng chi phí.

Ví dụ có $n = 3$ chuỗi: 123, 456, 789:

• Chọn 123 làm gốc, cố gắng biến đổi 456 và 789 xem có về được 123 không.
• Sau đó chọn 456 làm gốc, cố gắng biến đổi 123 và 789.
• Sau đó chọn 789 làm gốc, cố gắng biến đổi 123 và 456.

Nếu một chuỗi đã xoay hết Length trạng thái mà vẫn không giống chuỗi gốc thì chuỗi gốc đó không chọn được, chuyển sang chọn chuỗi gốc khác. Trong các chuỗi gốc chọn được, lấy tổng chi phí nhỏ nhất. Nếu chọn hết $n$ chuỗi gốc mà không được cái nào thì kết luận -1.

Ý chính

Đáp án $= \min\limits_{i} \sum\limits_{j} k_{j}$, trong đó $k_j$ là số bước xoay ít nhất để chuỗi $a_j$ thành đúng chuỗi gốc $a_i$ (chuỗi gốc thì $k_i = 0$). Gốc $i$ nào có một chuỗi không xoay về được thì bỏ qua.

Vì sao chỉ cần thử gốc là một trong các chuỗi ban đầu?

Có bạn sẽ thắc mắc: lỡ chuỗi chung tốt nhất là một trạng thái đã xoay, không trùng chuỗi ban đầu nào thì sao? Giả sử trong một phương án, chuỗi nào cũng bị xoay ít nhất 1 bước. Khi đó bỏ bớt 1 bước ở mọi chuỗi thì chúng vẫn giống nhau (cùng là chuỗi chung "lùi lại" 1 nấc), mà tổng chi phí lại giảm đi $n$. Vậy phương án tốt nhất luôn có ít nhất một chuỗi giữ nguyên (0 bước), tức chuỗi chung chính là một chuỗi ban đầu. Thử hết $n$ chuỗi làm gốc là đủ.

Đầu về cuối, không phải cuối về đầu

Quy luật đề đưa ra là đem ký tự ở đầu về cuối nhé, còn cuối về đầu là "xúc phạm thần linh" đấy 😆. Xoay ngược chiều thì số bước $k$ sẽ khác, ra sai đáp án.

Minh hoạ vét cạn

Em nhập các chuỗi (cách nhau bởi dấu cách) rồi bấm Tiếp: hàng xanh lá là chuỗi đang được chọn làm gốc, hàng cam là chuỗi đang được xoay thử, các hạt xanh dương là những hạt đã bị đem từ đầu xuống cuối.

Các chuỗi

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này. Code này mình code vội đúng theo tư tưởng đã trình bày ở trên (đã nộp thành công trên web), mình chỉ căn lại thụt lề cho dễ đọc, chưa clean nhiều để các bạn dễ đối chiếu với phần phân tích:

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<string> a(n);
    vector<vector<int>> check(n, vector<int>(123, 0));
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        for(int j = 0; j < a[i].length(); ++j){
            check[i][a[i][j]]++;
        }
    }
    bool flag = true;
    for(int i = 1; i < n; ++i){
        if(check[i] != check[i - 1]){
            flag = false;
            break;
        }
    }
    if(flag == false){
        cout << -1;
    }
    else{
        long long Min = LLONG_MAX;
        for(int i = 0; i < n; ++i){
            long long sum = 0;
            flag = true;
            for(int j = 0; j < n; ++j){
                bool flag2 = false;
                for(int k = 0; k < a[j].length(); ++k){
                    string s = a[j].substr(k) + a[j].substr(0, k);
                    if(s == a[i]){
                        sum += k;
                        flag2 = true;
                        break;
                    }
                }
                if(flag2 == false){
                    flag = false;
                    break;
                }
            }
            if(flag == true){
                Min = min(Min, sum);
            }
        }
        if(Min == LLONG_MAX){
            cout << -1;
        }
        else{
            cout << Min;
        }
    }
    return 0;
}

n = int(input())
a = [input().strip() for _ in range(n)]

# Điều kiện -1: số lượng từng ký tự của mọi chuỗi phải giống nhau
flag = True
for i in range(1, n):
    if sorted(a[i]) != sorted(a[i - 1]):
        flag = False
        break

if not flag:
    print(-1)
else:
    Min = -1
    for i in range(n):              # chọn a[i] làm chuỗi gốc
        total = 0
        flag = True
        for j in range(n):          # biến đổi a[j] về a[i]
            flag2 = False
            for k in range(len(a[j])):
                s = a[j][k:] + a[j][:k]
                if s == a[i]:
                    total += k
                    flag2 = True
                    break
            if not flag2:
                flag = False
                break
        if flag and (Min == -1 or total < Min):
            Min = total
    print(Min)

C++▶ Chạy tay từng dòng codeĐếm ký tự để loại -1, rồi chọn từng chuỗi làm gốc và xoay các chuỗi khác về gốc.

Dữ liệu vào (stdin) – sửa thoải mái2 ryuu yuur

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 cout.tie(0);

8 int n;

9 cin >> n;

10 vector<string> a(n);

11 vector<vector<int>> check(n, vector<int>(123, 0));

12 for(int i = 0; i < n; ++i){

13 cin >> a[i];

14 for(int j = 0; j < a[i].length(); ++j){

15 check[i][a[i][j]]++;

16 }

17 }

18 bool flag = true;

19 for(int i = 1; i < n; ++i){

20 if(check[i] != check[i - 1]){

21 flag = false;

22 break;

23 }

24 }

25 if(flag == false){

26 cout << -1;

27 }

28 else{

29 long long Min = LLONG_MAX;

30 for(int i = 0; i < n; ++i){

31 long long sum = 0;

32 flag = true;

33 for(int j = 0; j < n; ++j){

34 bool flag2 = false;

35 for(int k = 0; k < a[j].length(); ++k){

36 string s = a[j].substr(k) + a[j].substr(0, k);

37 if(s == a[i]){

38 sum += k;

39 flag2 = true;

40 break;

41 }

42 }

43 if(flag2 == false){

44 flag = false;

45 break;

46 }

47 }

48 if(flag == true){

49 Min = min(Min, sum);

50 }

51 }

52 if(Min == LLONG_MAX){

53 cout << -1;

54 }

55 else{

56 cout << Min;

57 }

58 }

59 return 0;

60}

ChậmVừaNhanhRất nhanh

Một vài ghi chú về code:

• check[i][a[i][j]]++: ký tự a[i][j] được dùng trực tiếp làm chỉ số (C++ tự đổi char sang mã ASCII), ví dụ 'a' là ô 97, 'z' là ô 122, nên mảng đếm cần 123 ô.
• check[i] != check[i - 1]: hai vector so sánh được trực tiếp bằng == / !=, nó so từng phần tử giúp mình luôn.
• Min khởi tạo LLONG_MAX (số long long lớn nhất). Cuối cùng mà Min vẫn là LLONG_MAX nghĩa là không có chuỗi gốc nào chọn được ⇒ in -1. Trường hợp này xảy ra khi số lượng ký tự giống hệt nhau nhưng thứ tự vòng tròn khác, ví dụ "abc" và "acb" (em bấm nút Đủ ký tự vẫn -1 trong khung chạy tay để xem).
• Bản Python dùng sorted(a[i]) != sorted(a[i - 1]) thay cho mảng đếm, đúng ý "sắp xếp rồi so sánh" ở trên, và dùng Min = -1 làm giá trị "chưa có".

Đánh giá độ phức tạp của cách làm này:

• Không gian: $n$ chuỗi và $n$ mảng đếm 123 ô ⇒ $O(n \cdot |s|)$.
• Thời gian: bước đếm ký tự mất $O(n \cdot |s|)$. Phần vét cạn: $n$ chuỗi gốc × $n$ chuỗi cần xoay × tối đa $|s|$ lần xoay, mỗi lần tạo chuỗi và so sánh mất $O(|s|)$ ⇒ $O(n^2 \cdot |s|^2) = 50^4 \approx 6.25 \cdot 10^6$ phép tính, quá nhẹ nhàng.

Không gian$O(n \cdot |s|)$

Thời gian$O(n^2 \cdot |s|^2)$

Bước kiểm tra -1 ban đầu có bắt buộc không?

Thật ra không bắt buộc: nếu số lượng ký tự khác nhau thì phần vét cạn cũng sẽ không tìm được gốc nào và in -1. Nhưng xét trước giúp mình hiểu bản chất bài toán và loại sớm được nhiều trường hợp, đó cũng là thói quen tư duy tốt khi giải bài.

Ghi chú của mình: code C++ và Python ở trên cho đúng output 2 ví dụ của đề, và đã được kiểm tra với 500 bộ test ngẫu nhiên ($n \le 5$, $|s| \le 6$, có cả trường hợp đủ ký tự nhưng vẫn -1), so với một code vét cạn khác (thử mọi trạng thái xoay của chuỗi đầu làm chuỗi chung) – khớp hết. Với $n = 50$, $|s| = 50$: C++ chạy khoảng 0.01 giây, Python khoảng 0.1 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇