Lá Bài (LABAI)

Nguồn: Đề thi HSG (học viên hỏi) Độ khó: Trung bình Đồ thị Chu trình Hàng đợi

Đề bài

Bài 3: Lá bài

Có $N$ lá bài với các số hiệu là $1, 2, \ldots, N$ $(N \le 50)$. Trên lá bài $i$ ghi một số nguyên dương $F[i]$, $1 \le F[i] \le N$.

Yêu cầu: Hãy tìm nhiều lá bài nhất sao cho tập các số hiệu của chúng bằng với tập các số ghi trên các lá bài đó.

Dữ liệu vào: Đọc từ file text LABAI.INP có cấu trúc như sau:

• Dòng thứ nhất chứa số nguyên dương $N$.
• Các dòng tiếp theo, mỗi dòng chứa 10 số (cho đến khi hết $N$ số) lần lượt là các số ghi trên các lá bài, từ lá bài 1 đến lá bài $N$, mỗi số cách nhau ít nhất một dấu cách.

Dữ liệu ra: Kết quả ghi ra file text LABAI.OUT có cấu trúc như sau:

• Dòng thứ nhất ghi số lượng lá bài.
• Các dòng tiếp theo, mỗi dòng ghi 10 số hiệu của các lá bài được chọn, các số hiệu ghi theo thứ tự tăng dần cho đến hết, mỗi số cách nhau ít nhất một dấu cách.

(Code trong bài đọc/ghi chuẩn (bàn phím/màn hình) như trên các hệ thống chấm online. Nếu nộp theo file thì các bạn thêm freopen("LABAI.INP", "r", stdin); freopen("LABAI.OUT", "w", stdout); ở đầu hàm main nhé.)

LABAI.INP

14
6 5 1 3 4 2 8 10 7 9
3 2 1 9

LABAI.OUT

10
1 2 3 4 5 6 7 8 9 10

Lời mở đầu

Nay mình đi comment dạo thấy bài này cũng được (một bạn lớp 11 hỏi ý tưởng), đăng để anh em thử sức nhé. 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 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

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

Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Có 14 lá bài, số ghi trên lá $1..14$ lần lượt là 6 5 1 3 4 2 8 10 7 9 3 2 1 9.

• Nếu chọn cả 14 lá thì tập số hiệu là $\{1, \ldots, 14\}$, nhưng các số ghi trên lá chỉ gồm $\{1, \ldots, 10\}$ – không có ai ghi số 11, 12, 13, 14 ⇒ không bằng nhau.
• Chọn 10 lá $1..10$: các số ghi trên chúng là 6 5 1 3 4 2 8 10 7 9 – đúng bằng tập $\{1, 2, \ldots, 10\}$ ⇒ thỏa. Đáp án là 10 lá.

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

Nhận xétTập cần chọn = các chu trìnhCách 1Đi theo mũi tên từ mỗi lá · O(N²)Cách 2Loại dần lá thừa bằng hàng đợi · O(N)

Nhận xét quan trọng: đây là bài tìm chu trình

Mình vẽ mỗi lá bài là một đỉnh, rồi kẻ mũi tên từ lá $i$ tới lá $F[i]$ (số ghi trên lá $i$ chỉ sang lá có số hiệu đó). Mỗi đỉnh có đúng một mũi tên đi ra. Gọi $S$ là tập lá được chọn, điều kiện đề là $\{F[i] : i \in S\} = S$:

• Mũi tên từ mọi lá trong $S$ phải chỉ vào trong $S$ (vế trái $\subseteq S$).
• Mọi lá trong $S$ đều phải được ít nhất một lá trong $S$ chỉ tới (vế phải $\subseteq$ vế trái). Mà $S$ có $|S|$ mũi tên đi ra và phải "phủ" đủ $|S|$ đỉnh ⇒ mỗi đỉnh trong $S$ được chỉ tới đúng một lần, tức là $F$ là một hoán vị trên $S$.
• Hoán vị thì tách thành các chu trình ⇒ $S$ là hợp của một số chu trình. Ngược lại, lấy bất kỳ chu trình nào cũng thỏa.

Kết luận

Tập lớn nhất cần chọn chính là tất cả các lá nằm trên chu trình của đồ thị $i \to F[i]$. Những lá "lơ lửng" ngoài chu trình (như lá 11, 12, 13, 14 trong ví dụ) thì không bao giờ chọn được. Vì mỗi đỉnh có 1 mũi tên ra nên đi mãi thế nào cũng rơi vào một chu trình ⇒ đáp án luôn có ít nhất 1 lá.

Trong ví dụ: $1 \to 6 \to 2 \to 5 \to 4 \to 3 \to 1$ là một chu trình, $7 \to 8 \to 10 \to 9 \to 7$ là chu trình thứ hai; còn lá 11, 12, 13, 14 chỉ chỉ vào chu trình chứ không ai chỉ lại về chúng. Phần minh hoạ ở Cách 2 sẽ vẽ hình này cho các bạn xem.

Cách 1Đi theo mũi tên từ từng lá – O(N²)

Lá $i$ nằm trên chu trình khi và chỉ khi xuất phát từ $i$, đi theo mũi tên $i \to F[i] \to F[F[i]] \to \ldots$ thì sẽ quay lại $i$. Một chu trình dài nhất cũng chỉ có $N$ đỉnh, nên chỉ cần đi tối đa $N$ bước: nếu gặp lại $i$ thì chọn, còn đi đủ $N$ bước mà chưa gặp thì $i$ nằm ngoài chu trình.

Ví dụ lá 11: $11 \to 3 \to 1 \to 6 \to 2 \to 5 \to 4 \to 3 \to \ldots$ cứ quay vòng trong chu trình $\{1, 2, 3, 4, 5, 6\}$ mãi mà không bao giờ về 11 ⇒ không chọn. Lá 7: $7 \to 8 \to 10 \to 9 \to 7$ ⇒ quay về 7, chọn.

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 n, F[55];

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> F[i];
    vector<int> chon;
    for(int i = 1; i <= n; i++){
        int x = F[i];
        for(int b = 1; b < n && x != i; b++)
            x = F[x];
        if(x == i) chon.push_back(i);
    }
    cout << chon.size() << "\n";
    for(int k = 0; k < (int)chon.size(); k++){
        cout << chon[k];
        if(k % 10 == 9 || k + 1 == (int)chon.size()) cout << "\n";
        else cout << " ";
    }
    return 0;
}

import sys

data = sys.stdin.read().split()
n = int(data[0])
F = [0] + [int(v) for v in data[1:n + 1]]

chon = []
for i in range(1, n + 1):
    x = F[i]
    b = 1
    while b < n and x != i:
        x = F[x]
        b += 1
    if x == i:
        chon.append(i)

print(len(chon))
for k in range(0, len(chon), 10):
    print(' '.join(map(str, chon[k:k + 10])))

In 10 số mỗi dòng

Đề yêu cầu mỗi dòng 10 số hiệu, nên sau số thứ $k$ (đếm từ 0) mình xuống dòng khi $k \bmod 10 = 9$ hoặc khi là số cuối cùng, còn lại in dấu cách.

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

• Không gian: $O(N)$.
• Thời gian: mỗi lá đi tối đa $N$ bước ⇒ $O(N^2)$. Với $N \le 50$ thì quá nhẹ, chạy tức thì.

Không gian$O(N)$

Thời gian$O(N^2)$

Cách 2Loại dần những lá "thừa" bằng hàng đợi – O(N)

Có bạn hỏi dưới bài: "bài này dùng set được không ạ?". Được nhé 😄 – ý tưởng rất tự nhiên là: ban đầu lấy hết các lá, rồi cứ lá nào có số hiệu mà không còn lá nào ghi số đó thì chắc chắn không thể nằm trong tập cần chọn ⇒ bỏ nó đi. Bỏ lá $u$ đi thì số $F[u]$ mất đi một lần xuất hiện, có thể làm lá $F[u]$ trở thành "thừa" tiếp. Cứ lặp đến khi không bỏ được nữa thì phần còn lại chính là các chu trình.

Dùng set để mỗi vòng tính lại tập các số đang được ghi cũng được, nhưng gọn và nhanh nhất là dùng mảng đếm:

Thuật toán

cnt[i] = số lá còn lại đang ghi số $i$ (bậc vào của đỉnh $i$). Ban đầu đẩy mọi lá có cnt[i] = 0 vào hàng đợi. Mỗi lần lấy $u$ ra: đánh dấu bỏ $u$, giảm cnt[F[u]]; nếu nó về 0 thì đẩy $F[u]$ vào hàng đợi. Những lá không bị bỏ là đáp án.

Một lá nằm trên chu trình luôn được lá đứng trước nó trên chu trình chỉ vào, mà lá đó cũng không bao giờ bị bỏ ⇒ cnt của nó không bao giờ về 0. Ngược lại, các lá ngoài chu trình nằm trên các "cành cây" chĩa vào chu trình, sẽ bị bỏ dần từ ngọn vào.

Minh hoạ loại dần lá thừa

Các bạn nhập $N$ và dãy $F$ rồi bấm Tiếp để xem từng lá bị loại (số nhỏ cạnh mỗi đỉnh là cnt):

N F[1..N]

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 n, F[55], cnt[55];
bool bo[55];

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> F[i];
        cnt[F[i]]++;
    }
    queue<int> q;
    for(int i = 1; i <= n; i++)
        if(cnt[i] == 0) q.push(i);
    while(!q.empty()){
        int u = q.front(); q.pop();
        bo[u] = true;
        cnt[F[u]]--;
        if(cnt[F[u]] == 0) q.push(F[u]);
    }
    vector<int> chon;
    for(int i = 1; i <= n; i++)
        if(!bo[i]) chon.push_back(i);
    cout << chon.size() << "\n";
    for(int k = 0; k < (int)chon.size(); k++){
        cout << chon[k];
        if(k % 10 == 9 || k + 1 == (int)chon.size()) cout << "\n";
        else cout << " ";
    }
    return 0;
}

import sys
from collections import deque

data = sys.stdin.read().split()
n = int(data[0])
F = [0] + [int(v) for v in data[1:n + 1]]

cnt = [0] * (n + 1)          # cnt[i] = số lá còn lại đang ghi số i
for i in range(1, n + 1):
    cnt[F[i]] += 1

bo = [False] * (n + 1)
q = deque(i for i in range(1, n + 1) if cnt[i] == 0)
while q:
    u = q.popleft()
    bo[u] = True
    cnt[F[u]] -= 1
    if cnt[F[u]] == 0:
        q.append(F[u])

chon = [i for i in range(1, n + 1) if not bo[i]]
print(len(chon))
for k in range(0, len(chon), 10):
    print(' '.join(map(str, chon[k:k + 10])))

C++▶ Chạy tay từng dòng codeCách 2: đếm cnt (bậc vào), loại dần lá có cnt = 0 bằng hàng đợi, phần còn lại là các chu trình.

Dữ liệu vào (stdin) – sửa thoải mái14 6 5 1 3 4 2 8 10 7 9 3 2 1 9

Dữ liệu mẫu:

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

2using namespace std;

3

4int n, F[55], cnt[55];

5bool bo[55];

6

7int main(){

8 cin >> n;

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

10 cin >> F[i];

11 cnt[F[i]]++;

12 }

13 queue<int> q;

14 for(int i = 1; i <= n; i++)

15 if(cnt[i] == 0) q.push(i);

16 while(!q.empty()){

17 int u = q.front(); q.pop();

18 bo[u] = true;

19 cnt[F[u]]--;

20 if(cnt[F[u]] == 0) q.push(F[u]);

21 }

22 vector<int> chon;

23 for(int i = 1; i <= n; i++)

24 if(!bo[i]) chon.push_back(i);

25 cout << chon.size() << "\n";

26 for(int k = 0; k < (int)chon.size(); k++){

27 cout << chon[k];

28 if(k % 10 == 9 || k + 1 == (int)chon.size()) cout << "\n";

29 else cout << " ";

30 }

31 return 0;

32}

ChậmVừaNhanhRất nhanh

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

• Không gian: các mảng F, cnt, bo và hàng đợi – $O(N)$.
• Thời gian: mỗi lá vào/ra hàng đợi tối đa một lần ⇒ $O(N)$. Cách này vẫn chạy tốt nếu đề nâng $N$ lên $10^5$, $10^6$, trong khi cách 1 khi đó sẽ chậm.

Không gian$O(N)$

Thời gian$O(N)$

Đây chính là "sắp xếp tô pô" thu gọn

Kỹ thuật bỏ dần đỉnh có bậc vào bằng 0 bằng hàng đợi chính là ý tưởng của thuật toán Kahn (sắp xếp tô pô). Đỉnh nào không bao giờ bị bỏ thì nằm trên chu trình – các bạn nhớ mẹo này để dùng cho nhiều bài đồ thị khác nhé.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 400 bộ test ngẫu nhiên $N \le 12$, so với code vét cạn thử mọi tập con lá bài – khớp hết (cả số lượng lẫn danh sách và cách xuống dòng); thêm 300 bộ test $30 \le N \le 50$ so 2 cách với nhau cũng khớp. Với $N \le 50$ cả 2 cách đều chạy tức thì.

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 😇