VOITSORT – spoj

Đề bài:

Thuật toán:

Trong bài toán này, ta nhận thấy không còn cách nào khác ngoài việc xây dựng
tất cả K hoán vị theo yêu cầu và kiểm tra từng hoán vị.

Để full điểm, ngoài việc kiểm tra như trong đề bài mô tả, ta cần có thêm
một số cái nhìn tinh tế hơn.

Thứ nhất, do lượng hoán vị cần xét là
$K \leq 10^6 < 10!$ , do vậy mọi hoán
vị cần xét dường như chỉ xoay quanh việc thay đổi thứ tự 10 phần tử cuối
cùng. Trên thực tế, sẽ có tối đa một lần có hơn 10 phần tử cuối cùng thay
đổi trong dãy hoán vị và việc này không làm ảnh hưởng nhiều tới tính hiệu
quả của nhận xét này.

Thứ hay, có thể phát biểu thuật toán T(p) với một chút khác biệt như :

  • p có không nhiều hơn 1 phần tử, T(p) = true
  • p có nhiều hơn 1 phần tử, gọi X là vị trí của phần tử lớn nhất trong p,
    pL là các phần tử bên trái của X và pL là các phần tử bên phải của X, khi đó
    T(p) = true khi:

    • T(pL) = T(pR) = true
    • Tất cả các phần tử trong pL nhỏ hơn tất cả các phần tử trong p

Cách phát biểu khác biệt này đưa ra một nhận xét tổng quát hơn: “T(p) = true
khi và chỉ khi không tồn tại 3 vị trí $i < j < k$ mà $p_k < p_i < p_j$

Cách phát biểu mới này giúp ta có một thuật toán kiểm tra T(p) hiệu quả hơn
như sau: Để đảm bảo T(p) = true, với mọi vị trí j nằm trong p, gọi R là phần
tử nhỏ nhất phía bên phải j và L là phần tử lớn nhất nhỏ hơn $p_j$ phía trái
j, ta phải đảm bảo rằng $L < R$

Tuy nhiên, trong thực tế ta chỉ cần kiểm tra điều kiện trên cho những phần
tử bị thay đổi so với hoán vị trước (khoảng 10 phần tử cuối cùng) nên thuật
toán có thể chạy trong thời gian cho phép.

Code:

#include <cstdio>
#include <vector>
using namespace std;
 
// Hàm sinh hoán vị tiếp theo trong thứ tự từ điển.
// Trả về `k` là vị trí mà hoán vị bắt đầu thay
// đổi so với hoán vị trước.
// k < 0 nếu đây đã là hoán vị cuối cùng.
int next(vector<int> &a) {
    int k, l, n = a.size();
    for (k = n-2; k>=0; k--) if (a[k] < a[k+1]) break;
    if (k<0) return k;
    for (l = n-1; l>k; l--) if (a[k] < a[l]) break;
    swap(a[k], a[l]);
    for (int i=k+1, j=n-1; i<j; i++, j--) swap(a[i], a[j]);
    return k;
}
 
bool f[1000];
int seed = 0;
int cache[1001];
 
// Kiểm tra xem tại a[i] có thỏa điều kiện L < R
// như đã giải thích ở trên hay không.
bool check(const vector<int> &a, int i) {
    int n = a.size();
    seed += 1;
    int r = 1e9;
    // Tìm R là giá trị nhỏ nhất ở bên phải a[i]
    // Đồng thời đánh dấu các giá trị xuất hiện
    // ở bên phải a[i]
    for (int j=i+1; j<n; j++) {
        cache[a[j]] = seed;
        r = min(r, a[j]);
    }
    // Tìm L là giá trị lớn nhất nhỏ hơn a[i]
    // ở bên trái a[i] => L không xuất hiện ở bên phải
    int l = 0;
    for (int j=a[i]-1; j>=1; j--) {
        if (cache[j] != seed) {
            l = j;
            break;
        }
    }
    return l < r;
}
 
// Lần lượt kiểm tra và cập nhật các phần tử
// từ a[k] trở lên, đồng thời kiểm tra xem
// tất cả các phần tử có thỏa mãn điều kiện
// L < R hay không.
bool ok(const vector<int> &a, int k) {
    int n = a.size();
    for (int i=k; i<n; i++) {
        f[i] = check(a, i);
        if (i>0) f[i] &= f[i-1];
    }
    return f[n-1];
}
 
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    vector<int> a(n);
    for (int i=0; i<n; i++) scanf("%d", &a[i]);
 
    int k = 0, count = 0;
    while (m--) {
        if (ok(a, k)) count++;
        k = next(a);
        if (k < 0) break;
    }
 
    printf("%d", count);
    return 0;
}
Khuyên dùng

 

Speak Your Mind

*