Đảo Ngược
Đề bài
Bạn được cho một hoán vị $p$ với độ dài $n$ (một dãy số chứa tất cả các số nguyên từ 1 đến $n$ theo một thứ tự bất kỳ). Bạn phải thực hiện đúng một thao tác sau:
- Chọn hai chỉ số $l$ và $r$ (với $1 \le l \le r \le n$).
- Đảo ngược đoạn con từ vị trí $l$ đến vị trí $r$ của hoán vị. Sau khi đảo ngược, hoán vị sẽ trở thành: $p_1, p_2,$ $\ldots,$ $p_{l-1},$ $p_r,$ $p_{r-1},$ $\ldots,$ $p_l,$ $p_{r+1},$ $\ldots,$ $p_n$.
Mục tiêu: tìm hoán vị có thứ tự từ điển nhỏ nhất có thể thu được sau khi thực hiện đúng một thao tác đảo ngược như trên.
Lưu ý về thứ tự từ điển: với hai hoán vị $a$ và $b$ cùng độ dài, $a$ được coi là nhỏ hơn $b$ về mặt từ điển nếu tại vị trí đầu tiên chúng khác nhau, phần tử của $a$ nhỏ hơn phần tử của $b$.
Hoán vị là một mảng gồm $n$ số nguyên phân biệt từ 1 đến $n$. Ví dụ: $[2,3,1,5,4]$ là một hoán vị, nhưng $[1,2,2]$ không phải (số 2 xuất hiện hai lần) và $[1,3,4]$ cũng không phải (với $n = 3$ nhưng lại có số 4 trong mảng).
Input: dòng đầu tiên chứa một số nguyên $t$ $(1 \le t \le 10^4)$ – số lượng bộ test. Mỗi bộ test gồm:
- Dòng thứ nhất chứa một số nguyên $n$ $(1 \le n \le 10^4)$ – độ dài của hoán vị.
- Dòng thứ hai chứa $n$ số nguyên $p_1, p_2, \ldots, p_n$ $(1 \le p_i \le n)$ – các phần tử của hoán vị. Dữ liệu đảm bảo đây là một hoán vị hợp lệ.
Dữ liệu đảm bảo tổng giá trị $n$ trên $t$ bộ test không vượt quá $10^6$.
Output: với mỗi bộ test, in ra hoán vị có thứ tự từ điển nhỏ nhất có thể thu được.
Subtask: 50% số test đầu tiên có $1 \le t, n \le 10^2$; 50% số test còn lại không có giới hạn gì thêm.
4
1
1
3
2 1 3
4
1 4 2 3
5
1 2 3 4 51
1 2 3
1 2 4 3
1 2 3 4 5Giải thích ví dụ:
- Test 1 ($n = 1$): hoán vị chỉ có một phần tử $[1]$. Đoạn duy nhất có thể chọn là $[1, 1]$. Kết quả vẫn là $[1]$.
- Test 2 ($n = 3$): hoán vị ban đầu là $[2, 1, 3]$. Cách tối ưu là đảo ngược đoạn $[1, 2]$. Kết quả thu được là $[1, 2, 3]$.
- Test 3 ($n = 4$): hoán vị ban đầu là $[1, 4, 2, 3]$. Cách tối ưu là đảo ngược đoạn $[2, 3]$ (các vị trí thứ 2 và thứ 3). Kết quả là $[1, 2, 4, 3]$.
- Test 4 ($n = 5$): hoán vị $[1, 2, 3, 4, 5]$ đã có thứ tự từ điển nhỏ nhất. Ta có thể chọn đoạn $[1, 1]$ (tức không thay đổi gì) để giữ nguyên nó.
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. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức làm, kèm phần hướng dẫn để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn 😇. Chúc các bạn học tốt và gặt hái nhiều thành công.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Hiểu đềTóm tắt đề bài
Cho sẵn một danh sách gồm $N$ số phân biệt (không trùng nhau) chỉ gồm các số từ 1 đến $N$ nằm rời rạc nhau, danh sách như thế gọi là một hoán vị. Ta cần chọn ra 2 số $L$ và $R$, đảo ngược thứ tự các số trong đoạn $[L, R]$ sao cho danh sách sau khi đảo ngược là hoán vị nhỏ nhất có thể, và in ra hoán vị đó.
Ví dụ hoán vị ban đầu là 1 4 2 3, liệt kê hết các cách chọn $L, R$:
| Đoạn đảo | Hoán vị thu được (in đậm là đoạn bị đảo) |
|---|---|
| — | 1 4 2 3 (giữ nguyên) |
| L = 1, R = 2 | 4 1 2 3 |
| L = 1, R = 3 | 2 4 1 3 |
| L = 1, R = 4 | 3 2 4 1 |
| L = 2, R = 3 | 1 2 4 3 ← nhỏ nhất |
| L = 2, R = 4 | 1 3 2 4 |
| L = 3, R = 4 | 1 4 3 2 |
Trường hợp $L = 2, R = 3$ cho hoán vị 1 2 4 3 nhỏ nhất trong tất cả các trường hợp, đó là đáp án. Nguyên tắc so sánh 2 hoán vị: đi từ đầu dãy, tại vị trí nào có chênh lệch thì ngay lập tức kết luận; nếu vẫn bằng nhau thì xét tiếp vị trí tiếp theo, giống như so sánh 2 chuỗi ký tự vậy.
50%Cách vét cạn: thử mọi cặp L, R
Cách dễ nhất là tạo mảng Min lưu hoán vị ban đầu, rồi vét cạn tất cả các cặp $L, R$: với mỗi cặp tạo ra dãy hoán vị tương ứng (mảng $b$), so sánh với Min, nhỏ hơn thì cập nhật lại. Xét đủ tất cả các cặp thì Min chính là đáp án.
Xem code vét cạn (50% điểm)
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e6;
int a[MAX + 5], b[MAX + 5], Min[MAX + 5];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t, n;
cin >> t;
while(t--){
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> a[i];
Min[i] = a[i];
}
for(int i = 1; i < n; ++i){
for(int j = i + 1; j <= n; ++j){
int L = i, R = j, idx = 1;
for(int k = 1; k < L; ++k){
b[idx++] = a[k];
}
for(int k = R; k >= L; --k){
b[idx++] = a[k];
}
for(int k = R + 1; k <= n; ++k){
b[idx++] = a[k];
}
bool check = false;
for(int m = 1; m <= n; ++m){
if(b[m] < Min[m]){
check = true;
break;
}
else if(b[m] > Min[m]){
break;
}
}
if(check == true){
for(int m = 1; m <= n; ++m){
Min[m] = b[m];
}
}
}
}
for(int m = 1; m <= n; ++m){
cout << Min[m] << " ";
}
cout << endl;
}
return 0;
}t = int(input())
for _ in range(t):
n = int(input())
a = list(map(int, input().split()))
best = a[:]
for L in range(n):
for R in range(L + 1, n):
b = a[:L] + a[L:R + 1][::-1] + a[R + 1:]
if b < best: # Python so sánh 2 list theo đúng thứ tự từ điển
best = b
print(*best)- Vì chỉ số $L, R$ trong đề tính từ 1 nên ta khởi tạo mảng dư 1 phần tử và chỉ dùng từ index 1 trở đi cho đồng bộ với đề, tránh lộn xộn.
- Mảng $b$ được tạo bằng 3 vòng lặp
for k: đầu tiên chứa các giá trị từ 1 đến $L-1$, tiếp theo là các giá trị từ $R$ về $L$ (đảo ngược), sau cùng là các giá trị từ $R+1$ đến $N$. Rồi so sánh $b$ vớiMinbằng cờ hiệucheck: gặpb[m] < Min[m]thìcheck = truevà dừng, gặpb[m] > Min[m]thì dừng luôn, bằng nhau thì xét tiếp.checklàtruethì chép $b$ vàoMin.
Độ phức tạp: có $\frac{N(N-1)}{2}$ cặp $L, R$, mỗi cặp mất $O(N)$ để tạo $b$ và so sánh, tổng cộng $O(N^3)$ cho mỗi bộ test. Với subtask đầu ($t, n \le 100$) thì tầm $100 \times 100^3 = 10^8$ phép tính, vừa chạm ngưỡng. Còn $n$ tới $10^4$ thì $10^{12}$, chắc chắn TLE. Tuy nhiên ta vẫn nên cài đặt cách cơ bản nhất này để làm công cụ kiểm tra cho cách tối ưu, bạn nào chưa biết thì xem bài Hạn chế lỗi Wrong Answer của mình nhé.
100%Cách tối ưu: tham lam – O(N)
Đọc yêu cầu đề là thấy mùi tham lam ngay: muốn kết quả nhỏ nhất. Để dãy hoán vị là nhỏ nhất thì các phần tử nhỏ nhất phải nằm ở đầu tiên. Ví dụ $N = 5$ thì hoán vị nhỏ nhất là 1 2 3 4 5, các số tăng dần từ trái qua phải.
a[i] == i thì số đó đã đứng đúng chỗ, giữ nguyên.② Vị trí đầu tiên mà
a[i] != i gọi là L.③ Tìm tiếp từ $L+1$ trở đi vị trí đang chứa giá trị L (giá trị lẽ ra phải đứng ở vị trí L), gọi là R.
④ In ra $a[1..L-1]$, rồi $a[R]$ về $a[L]$, rồi $a[R+1..N]$. Nếu không có vị trí sai nào thì in nguyên dãy.
1 4 2 3: $a[1] = 1$ đúng chỗ; $a[2] = 4 \ne 2$ nên $L = 2$; giá trị 2 đang ở vị trí 3 nên $R = 3$. Kết quả1 2 4 3.2 1 3: $a[1] = 2 \ne 1$ nên $L = 1$; giá trị 1 ở vị trí 2 nên $R = 2$. Kết quả1 2 3.1 2 3 4 5: tất cả đều đứng đúng chỗ, không có $L$ nào, kết quả giữ nguyên.
Em tự chạy thử từng bước nhé (nhập hoán vị tối đa 15 phần tử):
Khá đơn giản đúng không? Chỉ cần tham lam một chút thôi mà hehe 😄.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e6;
int a[MAX + 5];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t, n;
cin >> t;
while(t--){
cin >> n;
int start = -1, finish = -1;
for(int i = 1; i <= n; ++i){
cin >> a[i];
if(start == -1){
if(a[i] == i){
cout << i << " ";
}
else{
start = i;
}
}
else if(a[i] == start){
finish = i;
for(int j = finish; j >= start; --j){
cout << a[j] << " ";
}
}
else if(finish != -1){
cout << a[i] << " ";
}
}
cout << endl;
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
t = int(data[0]); pos = 1
out = []
for _ in range(t):
n = int(data[pos]); pos += 1
a = [0] + [int(x) for x in data[pos:pos + n]]; pos += n
L = 1
while L <= n and a[L] == L: # tìm vị trí đầu tiên đứng sai chỗ
L += 1
if L <= n:
R = a.index(L, L) # vị trí đang chứa giá trị L
a[L:R + 1] = a[L:R + 1][::-1] # đảo ngược đoạn [L, R]
out.append(' '.join(map(str, a[1:])))
print('\n'.join(out))
main()Giải thích một số chỗ trong code
ios::sync_with_stdio(0); cin.tie(0);2 dòng đầu tiên của hàm main sẽ giúp đẩy nhanh tốc độ nhập xuất dữ liệu nếu các bạn đang code theo ngôn ngữ C++ (để hiểu vì sao thì các bạn cứ gõ mấy từ này lên Google là sẽ ra rất nhiều bài viết giải thích nhé), nên kinh nghiệm trong các bài cần nhập xuất nhiều, như bài này tổng số phần tử cần nhập và xuất có thể lên tới $10^6$, ta nên để 2 dòng này vào cho chạy nhanh hơn. Tất nhiên nếu các bạn code theo cú pháp của C thì chẳng cần mấy dòng đó làm gì, tuy nhiên thường khi code các bài lập trình thi đấu thế này ta dùng C++ vì cú pháp ngắn gọn cũng như nhiều hỗ trợ của nó, vậy nên bạn nào code C++ thì nhớ thêm 2 dòng này vào đầu hàm main nhé. Các bạn có thể thử bỏ 2 dòng đó đi thì thời gian chạy tăng gấp nhiều lần.- Biến
startchính là $L$,finishchính là $R$, mình cố tình đặt tên vậy để các bạn thấy rõ. - Nhiều bạn sẽ trình bày dài dòng: một vòng lặp tìm
start, một vòng tìmfinish, rồi 3 vòng in 3 đoạn, cộng vòng đọc dữ liệu và vòng lặp bộ test, cả thảy 7 vòng lặp. Code của mình chỉ dùng đúng 3 vòng lặp, vì gộp luôn bước xử lý vào bước đọc dữ liệu: khởi tạostart = finish = -1(chưa tìm ra). Đọc mỗia[i]: nếustartvẫn là $-1$ thìa[i] == ilà in luôn, khác thì gánstart = i. Khi đã cóstart, gặpa[i] == startthì đó làfinish, in ngược từfinishvềstart. Sau đó cáca[i]tiếp theo (khifinish != -1) cứ thế in ra.
Từ $O(N^3)$ mỗi bộ test ta rút xuống còn $O(N)$, với tổng $n$ tối đa $10^6$ thì chỉ khoảng một triệu thao tác. Thậm chí bộ nhớ cũng ít hơn (trước đó 3 mảng $a, b,$ Min, giờ chỉ cần 1 mảng) và code cũng gọn hơn rất nhiều. Mọi thứ đều tốt hơn, chỉ cần ta chịu khó nhìn một chút để thấy quy luật của nó 😊.
Nhận xét
Đăng nhận xét