Họ Hàng (HOHANG) (HSG 19.20)

Nguồn: VinhDinhCoder – HSG 19.20 Độ khó: Dễ Xâu Sắp xếp Đếm phân phối

Đề bài

HOHANG – Họ hàng – HSG 19.20

Ở vương quốc NONAME người ta đưa ra một quy tắc đặt tên kỳ lạ: Mỗi dòng họ chọn một dãy kí tự độ dài $n$ chỉ gồm các kí tự in hoa trong bảng chữ cái tiếng Anh. Khi đó để đặt tên cho một người trong dòng họ thì chỉ cần thay đổi thứ tự của các kí tự với nhau.

Yêu cầu: Cho biết hai xâu tên của hai người trong vương quốc, hãy kiểm tra xem hai người này có cùng dòng họ hay không.

Dữ liệu nhập:

• Dòng thứ nhất là số nguyên $T$ $(1 \le T \le 10)$ là số trường hợp cần kiểm tra.
• Các dòng tiếp theo mô tả $T$ trường hợp gồm:
  • Dòng thứ nhất là số nguyên dương $n$;
  • Dòng thứ hai là xâu tên thứ nhất;
  • Dòng thứ ba là xâu tên thứ hai.

Kết quả: In ra $T$ dòng là kết quả kiểm tra cho $T$ trường hợp. Nếu cùng dòng họ thì in 1, còn không ghi 0.

Ràng buộc:

• 50% test: $1 \le N \le 255$;
• 30% test: $1 \le N \le 10\,000$;
• 20% test: $1 \le N \le 100\,000$.

Giới hạn: thời gian 1 giây, bộ nhớ 128 MB.

Ví dụ 1 – input

3
3
LLQ
KHQ
3
FDF
GDD
3
KWE
EKW

Ví dụ 1 – output

0
0
1

Ví dụ 2 – input

2
3
FJS
FHF
3
HWJ
HJW

Ví dụ 2 – output

0
1

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Nhắc lại ngưỡng TLE

Với các hệ thống chấm giới hạn 1 giây, tối đa toàn bài chỉ nên lặp khoảng $(3 \div 5) \cdot 10^7$ lần là an toàn, tệ nhất là $10^8$ (lúc này thì hên xui nhé), vượt ngưỡng này là khả năng TLE rất cao. Ngưỡng này là cho C/C++; Python, C#, Java chạy chậm hơn nên ngưỡng phải thấp hơn. Đề cho 2 giây thì nhân ngưỡng lên 2, 3 giây thì nhân 3, 100 ms thì chia 10… cứ thế thôi. Bài này giới hạn 1 giây.

Chốt ngắn gọn lại là bài này cần kiểm tra giữa 2 tên xem có cùng dòng họ không? Có thì in ra 1, không thì in ra 0, và có $T$ bộ test cần kiểm tra.

Các bạn cần chú ý thông tin quan trọng: "Mỗi dòng họ chọn một dãy kí tự độ dài n … để đặt tên cho một người trong dòng họ thì chỉ cần thay đổi thứ tự của các kí tự với nhau." Vậy 2 người cùng dòng họ khi mà tất cả các ký tự có trong tên người này cũng đều có đầy đủ trong tên người kia, với số lượng y hệt; vị trí khác nhau là bình thường. Nói cách khác: tên này là một hoán vị các ký tự của tên kia.

Ví dụ người thứ nhất tên AABC (2 chữ A, 1 chữ B, 1 chữ C) thì người thứ hai tên CABA, CBAA hay ABAC đều là cùng dòng họ. Còn nếu người thứ hai tên CBCA thì không cùng dòng họ, bởi chỉ có 1 chữ A (lại dư 1 chữ C).

Giải thích ví dụ 1 của đề:

Tên 1	Tên 2	Nhận xét	Kết quả
LLQ	KHQ	Tên 1 có 2 chữ L, tên 2 không có chữ L nào	0
FDF	GDD	Tên 1 có 2 chữ F, tên 2 không có F mà lại có G	0
KWE	EKW	Cả hai đều có đúng 1 K, 1 W, 1 E	1

Ví dụ 2 cũng vậy: FJS và FHF khác nhau (một bên có J, S; một bên có 2 chữ F và H) nên in 0; HWJ và HJW chỉ đổi chỗ W, J nên in 1.

Khi đã xác định được vấn đề rồi thì cách giải quyết khá đơn giản, và có nhiều cách khác nhau. Mình trình bày 2 cách:

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 từng phần để nhảy tới:

Cách 1Sắp xếp 2 chuỗi rồi so sánh · O(T·N·logN)Cách 2Đếm phân phối · O(T·N)

Cách 1Sắp xếp 2 chuỗi rồi so sánh – O(T·N·logN)

Một cách giải quyết mà nhiều bạn chọn đó là đi sắp xếp chuỗi tăng dần (các ký tự tăng dần theo mã ASCII, tức là A đứng trước B, B đứng trước C… như trong bảng chữ cái). Sắp xếp cả 2 chuỗi tăng dần mục đích là để cùng thống nhất 1 quy chuẩn cho cả 2 chuỗi, khi đó chỉ việc so sánh 2 chuỗi với nhau: chỉ cần tại 1 vị trí có sự khác biệt ký tự giữa 2 bên là ngay lập tức kết luận không phải họ hàng, còn nếu đến cuối cùng vẫn đều giống nhau thì là họ hàng.

Tên 1	Sắp xếp	Tên 2	Sắp xếp	Kết quả
AABC	AABC	CABA	AABC	giống ⇒ 1
AABC	AABC	CBAA	AABC	giống ⇒ 1
AABC	AABC	ABAC	AABC	giống ⇒ 1
AABC	AABC	CBCA	ABCC	khác ở index 1 ⇒ 0

Chọn thuật toán sắp xếp cho đúng

Phải tính trước trường hợp xấu nhất: chuỗi có độ dài $N$ lên đến $10^5$. Nếu chọn những thuật toán sắp xếp không tối ưu như Interchange Sort, Bubble Sort, Selection Sort… có độ phức tạp $O(N^2)$ thì $(10^5)^2 = 10^{10}$, vượt xa ngưỡng 1 giây ⇒ chắc chắn TLE. Nên phải dùng Quick Sort, Merge Sort, Heap Sort hay đơn giản nhanh gọn là dùng hàm sort trong thư viện để đảm bảo $O(N \log N)$: $10^5 \cdot \log_2(10^5) \approx 10^5 \cdot 17$, ít hơn ngưỡng nên không sợ TLE.

Em nhập 2 tên rồi bấm Tiếp để xem 2 chuỗi được sắp xếp rồi so sánh từng vị trí như thế nào:

Tên 1 Tên 2

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        string a, b;
        cin >> a >> a >> b;
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        cout << (a == b) << endl;
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.read().split()
    t = int(data[0])
    pos = 1
    out = []
    for _ in range(t):
        a = data[pos + 1]          # bỏ qua n ở data[pos]
        b = data[pos + 2]
        pos += 3
        out.append('1' if sorted(a) == sorted(b) else '0')
    print('\n'.join(out))

main()

Giải thích 1 số chỗ trong code ở trên:

1. 3 dòng đầu hàm main (ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);): hiểu cơ bản là nó giúp cin/cout của C++ chạy nhanh gần bằng nhập xuất của C. Bài này có tối đa $T = 10$ bộ test, mỗi bộ có 2 chuỗi dài tới $10^5$ ⇒ cả thảy có thể lên đến $2 \cdot 10^6$ (2 triệu) ký tự cần nhập, là một con số lớn, nên hãy thêm 3 dòng này vào cho chạy nhanh hơn.
2. Biến n hơi dư thừa: đã dùng kiểu string thì đọc bao nhiêu ký tự nó cũng đọc vào hết. Nên mình chẳng cần tạo biến $n$ mà đọc 2 lần vào biến a (cin >> a >> a): lần đầu là để "đọc bỏ" số $n$ (vẫn phải đọc vì input có nó), lần sau đọc chuỗi thật vào, đè lên dữ liệu cũ.
3. sort(a.begin(), a.end()); sắp xếp chuỗi a từ đầu đến cuối tăng dần. Muốn giảm dần thì thêm tham số thứ 3: sort(a.begin(), a.end(), greater<char>());. Hàm sort dùng thuật toán IntroSort (kết hợp các thuật toán sắp xếp tối ưu), bạn nào muốn tìm hiểu thì bám theo từ khóa này nhé. Không dùng bits/stdc++.h thì phải tự #include <algorithm>.
4. cout << (a == b) in ra kết quả của phép so sánh: 2 chuỗi bằng nhau thì là true, in ra số 1; khác nhau thì false, in ra số 0. Phép == của string so từng ký tự, gặp vị trí khác là trả false ngay.

C++▶ Chạy tay từng dòng codeCách 1: sắp xếp 2 chuỗi tăng dần rồi so sánh a == b.

Dữ liệu vào (stdin) – sửa thoải mái2 3 FJS FHF 3 HWJ HJW

Dữ liệu mẫu:

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

2using namespace std;

3

4int main(){

5 ios::sync_with_stdio(false);

6 cin.tie(0);

7 cout.tie(0);

8 int t;

9 cin >> t;

10 while(t--){

11 string a, b;

12 cin >> a >> a >> b;

13 sort(a.begin(), a.end());

14 sort(b.begin(), b.end());

15 cout << (a == b) << endl;

16 }

17 return 0;

18}

ChậmVừaNhanhRất nhanh

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

• Không gian: $O(2 \cdot N)$ do ta có 2 chuỗi A, B ⇒ $O(N)$.
• Thời gian: vòng lặp chạy $T$ bộ test, mỗi bộ đọc 2 chuỗi mất $O(2N)$ và sắp xếp 2 chuỗi mất $O(2 \cdot N \log N)$. Tổng là $O(T \cdot 2 \cdot (N + N \log N))$. Theo quy tắc nhân BigO, bỏ hằng số 2; theo quy tắc cộng BigO, giữa $N$ và $N \log N$ lấy thành phần lớn hơn là $N \log N$. Vậy tổng quát là $O(T \cdot N \log N)$.

Không gian$O(N)$

Thời gian$O(T \cdot N \log N)$

Nếu tính chính xác trường hợp xấu nhất $T = 10$, mọi test đều có $N = 10^5$ thì số lần lặp cả thảy là $10 \cdot 2 \cdot (10^5 + 10^5 \cdot 17) = 3{,}6 \cdot 10^7$. Vẫn không bị TLE vì ngưỡng là $(3 \div 5) \cdot 10^7$, cao lắm là $10^8$, nhưng tính ra cũng gần chạm ngưỡng, khá mong manh đấy nhỉ :))

Cách 2Đếm phân phối – O(T·N)

Vẫn còn một cách làm tối ưu hơn: không phải tốn $O(N \log N)$ mà chỉ cần $O(N)$ thôi. Đó là dùng đếm phân phối.

Các ký tự trong mỗi chuỗi đều chỉ là chữ cái in hoa, tức là chỉ có 26 trường hợp từ A đến Z. Ký tự 'A' có mã ASCII là 65, 'Z' có mã ASCII là 90. Nên ta tạo mảng cnt có 100 phần tử chẳng hạn (index 0..99), và chỉ dùng các index từ 65 đến 90 thôi, coi như bỏ trống không dùng các index còn lại, bộ nhớ thoải mái thì có sao đâu hen các bạn. Ban đầu cả mảng cnt đều bằng 0.

• Duyệt chuỗi A: với mỗi ký tự a[i] ta tăng cnt[a[i]]++, tức là ô có index bằng mã ASCII của a[i] tăng thêm 1. Ví dụ a[i] = 'A' thì cnt[65]++, a[i] = 'B' thì cnt[66]++… Cứ thế ta thống kê được số lần xuất hiện của từng ký tự trong A.
• Duyệt chuỗi B: với mỗi ký tự b[i] ta đối chiếu bằng cách giảm cnt[b[i]]--. Nếu sau khi giảm mà cnt[b[i]] < 0 (cụ thể là $-1$) thì kết luận ngay A và B không phải họ hàng, vì ký tự đó trong B nhiều hơn trong A.
• Duyệt hết B mà không gặp số âm nào thì A, B là họ hàng.

Vì sao chỉ cần kiểm tra "bị âm"?

Hai chuỗi có cùng độ dài $n$. Nếu duyệt hết B mà không ô nào bị âm thì mỗi ký tự của B đều "trừ" được vào một ký tự tương ứng của A; B có đúng $n$ ký tự nên đã trừ hết đúng $n$ đơn vị mà A đã cộng vào ⇒ mọi ô cnt đều về 0 ⇒ số lần xuất hiện của từng ký tự ở 2 bên bằng nhau. Ở đây chỉ cần 1 mảng đếm thôi; mình thấy một số bạn dùng thêm 1 mảng đếm khác cho chuỗi B rồi đi so sánh 2 mảng đếm, như thế là rườm rà không cần thiết.

Em nhập 2 tên rồi bấm Tiếp để xem mảng đếm cnt thay đổi thế nào (chỉ hiện các ô của chữ cái có xuất hiện; số nhỏ phía trên là index = mã ASCII):

Tên 1 Tên 2

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        string s;
        cin >> s >> s;
        int cnt[100] = {0};
        for(int i = 0; i < (int)s.length(); ++i){
            cnt[s[i]]++;
        }
        cin >> s;
        int flag = 1;
        for(int i = 0; i < (int)s.length(); ++i){
            cnt[s[i]]--;
            if(cnt[s[i]] < 0){
                flag = 0;
                break;
            }
        }
        cout << flag << endl;
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.read().split()
    t = int(data[0])
    pos = 1
    out = []
    for _ in range(t):
        a = data[pos + 1]          # bỏ qua n ở data[pos]
        b = data[pos + 2]
        pos += 3
        cnt = [0] * 100
        for c in a:
            cnt[ord(c)] += 1
        flag = 1
        for c in b:
            cnt[ord(c)] -= 1
            if cnt[ord(c)] < 0:
                flag = 0
                break
        out.append(str(flag))
    print('\n'.join(out))

main()

Giải thích 1 số chỗ trong code ở trên:

1. Ta chỉ cần 1 chuỗi s duy nhất: cin >> s >> s đọc bỏ $n$ rồi đọc chuỗi A vào $s$, duyệt từng s[i] để tạo mảng thống kê cnt. Sau đó cin >> s đọc chuỗi B vào chính $s$, vì chuỗi A đã thống kê vào cnt xong, không còn nhu cầu dùng nữa. Cờ hiệu flag = 1; nếu sau khi cnt[s[i]]-- mà phát hiện cnt[s[i]] < 0 thì flag = 0 và break thoát vòng lặp, không cần duyệt tiếp. Cuối cùng in ra flag.
2. Thực ra cũng có thể không cần chuỗi s: đọc $n$ rồi cho vòng lặp chạy $n$ lần, mỗi lần đọc 1 ký tự rồi thống kê luôn, khỏi tốn bộ nhớ lưu chuỗi và khỏi duyệt 2 lần. Thế nhưng vì trước đó có đọc số nguyên nên khi đọc từng ký tự dễ bị dính bộ nhớ đệm (ký tự xuống dòng) và có thể ra kết quả sai. Nên để chắc ăn mình cứ đọc chuỗi như bình thường rồi duyệt chuỗi thống kê, chấp nhận duyệt 2 lần nhưng thế cho chắc hihi.
3. cnt[s[i]]: s[i] là kiểu char nhưng dùng làm index thì được tự đổi sang mã ASCII của nó (65..90), nên mảng 100 ô là đủ. Bản Python thì phải viết rõ ord(c).

C++▶ Chạy tay từng dòng codeCách 2: một mảng đếm cnt – cộng theo chuỗi A, trừ theo chuỗi B, bị âm là không cùng họ.

Dữ liệu vào (stdin) – sửa thoải mái3 3 LLQ KHQ 3 FDF GDD 3 KWE EKW

Dữ liệu mẫu:

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

2using namespace std;

3

4int main(){

5 ios::sync_with_stdio(false);

6 cin.tie(0);

7 cout.tie(0);

8 int t;

9 cin >> t;

10 while(t--){

11 string s;

12 cin >> s >> s;

13 int cnt[100] = {0};

14 for(int i = 0; i < (int)s.length(); ++i){

15 cnt[s[i]]++;

16 }

17 cin >> s;

18 int flag = 1;

19 for(int i = 0; i < (int)s.length(); ++i){

20 cnt[s[i]]--;

21 if(cnt[s[i]] < 0){

22 flag = 0;

23 break;

24 }

25 }

26 cout << flag << endl;

27 }

28 return 0;

29}

ChậmVừaNhanhRất nhanh

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

• Không gian: $O(N + 100)$, tổng quát là $O(\max(N, 100))$.
• Thời gian: $T$ bộ test, mỗi bộ khởi tạo mảng 100 phần tử bằng 0, đọc 2 chuỗi mất $O(2N)$, duyệt 2 chuỗi để thay đổi mảng thống kê mất $O(2N)$, còn mỗi lần cnt[s[i]]++ hay -- chỉ tốn $O(1)$ vì truy cập trực tiếp theo index. Tổng là $O(T \cdot (100 + 4N))$, bỏ hằng số 4 ⇒ $O(T \cdot \max(100, N))$.

Không gian$O(\max(N, 100))$

Thời gian$O(T \cdot \max(100, N))$

Trường hợp xấu nhất $T = 10$, $N = 10^5$: số lần lặp là $10 \cdot (100 + 4 \cdot 10^5) = 4\,001\,000$ (4 triệu lẻ 1000), trong khi cách sắp xếp ở trên phải lặp tới khoảng 36 triệu lần, tức cách này nhanh hơn chừng 9 lần. Thực tế khi mình nộp trên web: cách sắp xếp tuy vẫn AC nhưng chạy mất 731 ms, còn cách đếm phân phối chỉ mất 31 ms.

Nếu N lên tới 10^6 thì sao?

Giả sử đề sửa cho $N$ tối đa $10^6$ (1 triệu) và vẫn $T = 10$ thì cách sắp xếp phải lặp khoảng 420 triệu lần, gấp 4 lần ngưỡng cho phép ⇒ TLE; còn cách đếm phân phối chỉ lặp khoảng 40 triệu lần, vẫn dưới ngưỡng thoải mái. Đến đây các bạn đã thấy cái hay của giải thuật rồi hen: cùng ra kết quả đúng nhưng đếm phân phối tối ưu hơn hẳn mà code cũng không dài thêm bao nhiêu.

Ghi chú của mình: code C++ và Python của cả 2 cách đều cho đúng output 2 ví dụ của đề, và đã được so với một chương trình vét cạn (thử mọi hoán vị của tên thứ nhất) trên 400 bộ test ngẫu nhiên – khớp hết. Với test lớn nhất ($T = 10$, $N = 10^5$) trên máy mình: cách 1 bản C++ khoảng 0.11 giây, Python khoảng 0.6 giây; cách 2 bản C++ khoảng 0.02 giây, Python khoảng 0.45 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 😇