Hoán Vị Thần Kỳ (MAGPERM)
Đề bài
MAGPERM – Hoán vị thần kì
Cho một mảng $A$ gồm $N$ phần tử và 1 số $K$, các phần tử của mảng $A$ được đánh số từ $1$ đến $N$. Gọi một hoán vị của mảng $A$ là mảng $B$. Hãy viết chương trình tìm xem liệu có hoán vị $B$ nào thoả mãn:
- Các phần tử ở cùng một vị trí trong cả $A$ và $B$ đều có chênh lệch bằng $K$.
Ví dụ: Cho một mảng gồm 4 phần tử $A = [1, 2, 3, 4]$, $K = 2$. Thì ta tìm được một hoán vị $B = [3, 4, 1, 2]$ thoả mãn điều kiện đề bài vì:
- Ta có $B[0] - A[0] = 3 - 1 = 2$.
- Ở các vị trí khác ta có $A[2] - B[2] = 3 - 1 = 2$, tương tự với các vị trí còn lại.
Dữ liệu vào:
- Dòng 1 chứa số $N$ là độ dài của mảng và 1 số $K$.
Biết rằng:
- $1 \le N \le 10^5$
- $0 \le K \lt N$
Dữ liệu ra:
- Nếu có hoán vị $B$ nào thoả mãn đề bài, in ra hoán vị $B$ đó, mỗi phần tử cách nhau 1 dấu cách.
- Nếu không có hoán vị $B$ nào thoả mãn đề bài, in ra $-1$.
2 12 13 1-13 01 2 3Lời mở đầu
Bài này là một bài "tìm quy luật" rất điển hình: code thì ngắn tũn, nhưng phải chịu khó làm nháp vài ví dụ thì mới nhìn ra được. Một khi đã nhìn ra rồi thì các bạn sẽ thấy nó "thần kỳ" đúng như tên bài 😆.
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é:
Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Mảng $A$ luôn là $1, 2, \ldots, N$; ta cần xếp lại thành $B$ sao cho ở mọi vị trí $|B[i] - A[i]| = K$:
- Input #1 ($N = 2$, $K = 1$): $A = [1, 2]$, chọn $B = [2, 1]$ thì $|2 - 1| = 1$ và $|1 - 2| = 1$ ✔.
- Input #2 ($N = 3$, $K = 1$): vị trí 1 buộc phải là số 2 (vì $1 - 1 = 0$ không có), vị trí 3 cũng buộc phải là số 2 (vì $3 + 1 = 4$ vượt $N$) ⇒ số 2 bị dùng 2 lần ⇒ không có hoán vị nào ⇒ in
-1. - Input #3 ($N = 3$, $K = 0$): chênh lệch 0 nghĩa là giữ nguyên ⇒
1 2 3.
Có thể nhiều bạn nhìn vào sẽ thấy ngay một tư tưởng vét cạn: xét qua tất cả các hoán vị có thể có của $1..N$, so từng hoán vị với dãy ban đầu xem ở từng vị trí có chênh lệch đúng bằng $K$ không; nếu tất cả đều đúng thì đó là đáp án, còn có cặp nào khác $K$ thì bỏ qua xét hoán vị tiếp theo; đến cuối không có hoán vị nào thoả thì in $-1$.
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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Tìm quy luật chia cụm 2K – hoán đổi trong mảng – O(N)
Xét dãy ban đầu $1..N$ và bắt đầu từ số 1. Để số ở vị trí 1 trong hoán vị chênh lệch đúng $K$ thì số đó phải là $1 + K$ đúng không? Và tương tự ở vị trí $1 + K$ thì ta đặt số 1. Vậy cứ theo nguyên tắc đổi chỗ các cặp $\{1, 1 + K\}, \{2, 2 + K\}, \{3, 3 + K\}, \ldots$
Ví dụ $N = 4$, $K = 2$ như đề: đổi cặp $\{1, 3\}$ rồi cặp $\{2, 4\}$ ⇒ dãy hoán vị là $3, 4, 1, 2$. Nghĩa là ta đổi các cặp $\{a, b\}$ với $a$ bắt đầu từ 1, $b$ bắt đầu từ $1 + K$, rồi tăng đều cả hai lên 1 đơn vị: $\{a + 1, b + 1\}, \{a + 2, b + 2\}, \ldots$ cho đến khi giá trị $a$ của cặp tiếp theo bằng giá trị $b$ của cặp đầu tiên (tức là $1 + K$) thì dừng.
Thử một ví dụ khác $N = 12$, $K = 2$: các cặp đổi chỗ là $\{1, 3\}, \{2, 4\}$. Nếu tiếp tục sẽ là $\{3, 5\}$ – nhưng số 3 đã bị dùng ở cặp đầu tiên rồi nên dừng. Coi như ta đã xử lý xong 4 số từ 1 đến 4. Lặp lại quy trình bắt đầu từ số 5: đổi $\{5, 7\}, \{6, 8\}$. Rồi bắt đầu từ số 9: đổi $\{9, 11\}, \{10, 12\}$. Kết quả: $3, 4, 1, 2, 7, 8, 5, 6, 11, 12, 9, 10$.
⇒ Có đáp án khi và chỉ khi $N$ chia hết cho $2K$ (với $K \gt 0$). Số cụm là $\dfrac{N}{2K}$.
Như $N = 12$, $K = 2$ thì 12 chia hết cho 4 ⇒ có đáp án; $N = 4$, $K = 2$ cũng vậy. Còn input #2: $N = 3$, $K = 1$ thì 3 không chia hết cho 2 ⇒ không có hoán vị nào ⇒ -1.
- Vị trí $1..K$: $i - K \lt 1$ nên bắt buộc lấy $i + K$, tức là dùng hết các số $K+1..2K$.
- Các số $1..K$: số $v$ chỉ có thể nằm ở vị trí $v + K$ (vì $v - K \lt 1$) ⇒ vị trí $K+1..2K$ bắt buộc là các số $1..K$.
- Vậy cụm đầu $1..2K$ bị "khoá" hoàn toàn, phần còn lại $2K+1..N$ là một bài toán y hệt (chỉ dịch đi $2K$). Cứ thế lặp lại.
n % (2 * k) sẽ là chia cho 0 ⇒ chương trình văng lỗi! Phải xét riêng trường hợp này: $K = 0$ nghĩa là dãy hoán vị vẫn là dãy ban đầu, in $1, 2, \ldots, N$. Trong code mình viết k != 0 && n % (2 * k) != 0 – nhờ toán tử && "đoản mạch" nên khi $k = 0$ vế sau không bao giờ được tính.Minh hoạ chia cụm và đổi chỗ
Các bạn nhập $N$, $K$ rồi bấm Tiếp để xem từng cặp được đổi chỗ trong từng cụm. Dòng nhỏ phía trên mỗi ô là vị trí $i$, dòng dưới là chênh lệch $|B[i] - i|$:
Vậy cách cài đặt: đầu tiên kiểm tra $N$ có chia hết cho $2K$ không, nếu không thì in $-1$. Nếu chia hết thì tạo mảng a có $N + 1$ phần tử (dùng chỉ số $1..N$, bỏ qua chỉ số 0) với a[i] = i. Số cụm là sz = n / (2 * k). Với mỗi cụm chỉ cần biết $K$ vị trí đầu tiên của cụm, rồi đổi chỗ với vị trí cộng thêm $K$. Cụm đầu tiên thì $K$ vị trí đầu là $1..K$; sang cụm tiếp theo thì cộng dồn thêm $2K$: như $N = 12$, $K = 2$ thì là $1, 2$ rồi $5, 6$ rồi $9, 10$.
- Biến
szchính là số lượng cụm có $2K$ phần tử. - Biến
start,finishlà vị trí bắt đầu và kết thúc của $K$ phần tử đầu tiên mỗi cụm. Thực ra chỉ cầnstartlà đủ vìfinish = start + K - 1, nhưng thói quen mình đã có start là phải có finish cho rõ ràng hihi.
Source code để các bạn tham khảo thấy rõ những gì mình đã phân tích ở trên:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
if(k != 0 && n % (2 * k) != 0){
cout << -1;
return 0;
}
if(k == 0){
for(int i = 1; i <= n; ++i){
cout << i << " ";
}
}
else{
int a[n + 1];
for(int i = 1; i <= n; ++i){
a[i] = i;
}
int sz = n / (2 * k);
int start = 1;
int finish = k;
while(sz--){
for(int i = start; i <= finish; ++i){
swap(a[i], a[i + k]);
}
start += 2 * k;
finish += 2 * k;
}
for(int i = 1; i <= n; ++i){
cout << a[i] << " ";
}
}
return 0;
}n, k = map(int, input().split())
if k != 0 and n % (2 * k) != 0:
print(-1)
elif k == 0:
print(*range(1, n + 1))
else:
a = list(range(n + 1))
sz = n // (2 * k)
start = 1
finish = k
for _ in range(sz):
for i in range(start, finish + 1):
a[i], a[i + k] = a[i + k], a[i]
start += 2 * k
finish += 2 * k
print(*a[1:])Đánh giá độ phức tạp của cách làm này:
- Không gian: nếu không có hoán vị hoặc $K = 0$ thì $O(1)$, còn lại là $O(N)$ do lưu mảng
a. Xét trường hợp xấu nhất thì kết luận $O(N)$. - Thời gian: không có hoán vị thì $O(1)$. Có hoán vị: nếu $K = 0$ thì $O(N)$ cho vòng in $1..N$; nếu $K \ne 0$ thì $O(N)$ tạo mảng + $O(N)$ duyệt các cụm và đổi chỗ + $O(N)$ in kết quả, tức $O(3N)$, bỏ hằng số theo quy tắc nhân Big-O còn $O(N)$.
Với $N$ tối đa $10^5$ thì cao lắm cũng chỉ $3 \cdot 10^5$ lần lặp, trong khi ngưỡng 1 giây là $(3 \div 5) \cdot 10^7$ hay cao lắm $10^8$ ⇒ nhỏ hơn cả trăm lần, quá thoải mái 😎.
Cách 2In thẳng từng cụm, không cần mảng – O(N), bộ nhớ O(1)
Thật ra code ở trên còn chưa tối ưu đâu: với $K \ne 0$ ta hoàn toàn có thể in ra hoán vị mà không cần mảng, tức bộ nhớ luôn $O(1)$; thời gian vẫn $O(N)$ nhưng thực tế tốt hơn vì không phải tạo mảng, cũng không phải đổi chỗ – chỉ chạy in kết quả trực tiếp.
Quay lại ví dụ $N = 12$, $K = 2$ với 3 cụm $\{1, 2, 3, 4\}, \{5, 6, 7, 8\}, \{9, 10, 11, 12\}$. Nguyên tắc: với từng cụm, in $K$ phần tử sau cùng của cụm rồi in $K$ phần tử đầu tiên của cụm. Cụm 1: in $3, 4$ rồi $1, 2$. Cụm 2: in $7, 8$ rồi $5, 6$. Cụm 3: in $11, 12$ rồi $9, 10$ ⇒ $3, 4, 1, 2, 7, 8, 5, 6, 11, 12, 9, 10$.
start, finish là số đầu và số cuối của cụm. Điểm chia là $y = \left\lfloor \dfrac{start + finish}{2} \right\rfloor$. Ví dụ cụm $\{1, 2, 3, 4\}$: $y = \lfloor 5 / 2 \rfloor = 2$.In các số từ $y + 1$ đến
finish ($K$ phần tử sau cùng), rồi in từ start đến $y$ ($K$ phần tử đầu tiên). Cụm đầu tiên có start = 1, finish = 2K; sang cụm sau thì cả hai cộng thêm $2K$.Source code để các bạn tham khảo thấy rõ những gì mình đã phân tích ở trên:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
if(k == 0){
for(int i = 1; i <= n; ++i){
cout << i << " ";
}
}
else{
if(n % (2 * k) != 0){
cout << -1;
}
else{
int sz = n / (2 * k);
int start = 1, finish = 2 * k;
while(sz--){
int y = (start + finish) / 2;
for(int i = y + 1; i <= finish; ++i){
cout << i << " ";
}
for(int i = start; i <= y; ++i){
cout << i << " ";
}
start += 2 * k;
finish += 2 * k;
}
}
}
return 0;
}n, k = map(int, input().split())
if k == 0:
print(*range(1, n + 1))
elif n % (2 * k) != 0:
print(-1)
else:
res = []
sz = n // (2 * k)
start, finish = 1, 2 * k
for _ in range(sz):
y = (start + finish) // 2
res.extend(range(y + 1, finish + 1))
res.extend(range(start, y + 1))
start += 2 * k
finish += 2 * k
print(*res)Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(1)$ trong mọi tình huống.
- Thời gian: không tồn tại hoán vị thì $O(1)$, trường hợp xấu nhất khi có hoán vị là $O(N)$. Lưu ý lần này đúng là $O(N)$ chứ không phải $O(3N)$ như cách trước – về lý thuyết vẫn là $O(N)$ như nhau nhưng thực tế thì tốt hơn.
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét