KMP

Đề bài: Cho xâu T, P độ dài <= 1e6. Tìm các vị trí xuất hiện xâu P trong T.

Code C++:

#include <iostream>
#include <cstring>
using namespace std;

int b[1000000 + 5];

int main() {
    string t, p;
    cin >> t >> p;
    
    int i = 0, j = -1;
    b[0] = -1;
    while(i < p.size()) {
        while(j >= 0 && p[i] != p[j]) j = b[j];
        i++; j++;
        b[i] = j;
    }
    
    i = 0; j = 0;
    while(i < t.size()) {
        while(j >= 0 && t[i] != p[j]) j = b[j];
        i++; j++;
        if (j == p.size()) {
            cout << i - j + 1 << ' ';
            j = b[j];
        }
    }
    
    return 0;
}

Độ phức tạp: O(length(T) + length(P))

Lưu ý: Code này đã được dùng để nộp bài SUBSTR trên SPOJ (http://vn.spoj.com/problems/SUBSTR/)

Ghi chú:
– Ý nghĩa mảng b: Xâu con 0..b[i]-1 trong P là tiền tố và đồng thời là hậu tố dài nhất của xâu con 0..(i-1) trong P. (Lưu ý P[b[i]] có thể giống hoặc khác P[i] )
Update 4/3/2017:
– Trạng thái kết thúc của KMP cho biết xâu con chung dài nhất là tiền tố của P và hậu tố của T
– Biến đếm j của xâu P chạy đến đâu có nghĩa là xâu con tiền tố độ dài j+1 của P có xuất hiện trong T

Happy coding,

LIS – Dãy con tăng dài nhất

Đề bài: Tìm độ dài dãy con tăng dài nhất của dãy số A có N phần tử

Code C++:

#include <iostream>
using namespace std;

const int MAXN = 1e5 + 5;

int n, a[MAXN], h[MAXN];

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    
    int L = 1;
    h[1] = 1;
    for(int i = 2; i <= n; i++) {
        int lo = 1, hi = L;
        while(lo <= hi) {
            int mi = (lo + hi) / 2;
            if (a[h[mi]] < a[i]) lo = mi + 1;
            else hi = mi - 1;
        }
        h[lo] = i;
        L = max(L, lo);
    }
    
    cout << L;
    
    return 0;
}

Độ phức tạp: O(NlogL), với L là độ dài của dãy con tăng dài nhất.

Lưu ý: Bài này đã được dùng để nộp bài LIS trên SPOJ (http://vn.spoj.com/problems/LIS/)

Ghi chú:
– Sau khi ra khỏi vòng lặp tìm kiếm nhị phân, thì lo là vị trí của phần tử cần được thay thế.
– Lúc này, h[1] đến h[lo] sẽ là index của các phần tử trong mảng a tạo thành dãy con dài nhất kết thúc ở a[i].
– Từ tính chất này, chúng ta có thể in được dãy con tăng dài nhất bằng cách sử dụng mảng truy vết trace[i] với ý nghĩa: trace[i] là index của phần tử ở ngay trước a[i] trong dãy con tăng dài nhất kết thúc ở a[i]. Sau khi ra khỏi vòng lặp while, trace[i] = lo – 1;

Happy coding,

Kickstart Practice Round 2017 – Problem B

Link đề bài

Tóm tắt đề:
Có N người bầu cử cho người A, có M người bầu cử cho người B (0 <= M < N <= 2000), kết quả cuối cùng thì người A sẽ luôn thắng. Đến ngày bầu cử, tất cả (N+M) người sẽ xếp thành 1 hàng ( có (N+M)! cách sắp xếp ). Cứ sau mỗi một lượt bỏ phiếu của một người thì người chủ trì sẽ cho biết ai đang thắng (số phiếu của thắng > số phiếu người còn lại, không được <=).
Tính xác suất để người A luôn thắng tại mọi thời điểm bỏ phiếu.

Sample test
Input: 

2
2 1
1 0
Output:
0.33333333
1.00000000

Solution: http://ouo.io/ghgS6k

Source code: http://ouo.io/tZ8Oza

[NTUCoder] Capxach – Cặp xách

Đề bài: http://laptrinh.ntu.edu.vn/Problem/Details/5568

Lời giải:
+ Thực ra bài này không khó nhưng mình vẫn mắc phải cái lỗi sơ đẳng nên cứ note lại vậy
+ Quy hoạch động f[x] là số cách chọn để có được khối lượng x, khởi tạo f[0] = 1, implement với 2 vòng for đơn giản
+ Chú ý:
=> Nếu dể vòng for khối lượng ở ngoài, vòng for cặp xách ở trong sẽ cho kết quả sai do bị trùng cách chọn cặp xách
=> Cách viết đúng phải là vòng for cặp xách ở ngoài, for khối lượng ở trong => như vậy việc xây dựng f[x] tại thời điểm cặp xách thứ i sẽ chỉ phụ thuộc vào cặp xách j <= i => không bị trùng cách chọn

[NTUCoder] UOCLE – Ước lẻ

Đề bài: http://laptrinh.ntu.edu.vn/Problem/Details/3267

 Lời giải:
+ Đầu tiên ta chứng minh: Số tự nhiên N có số ước là lẻ <=> N là số chính phương.
Thực vậy, phân tích N thành thừa số nguyên tố: N = p1^a1 * p2^a2 … * pm^am, như vậy số ước của N = (a1 + 1) * (a2 + 1) * .. * (am + 1). Muốn tích này lẻ thì mỗi thừa số (ai + 1) phải lẻ => ai chẳn => N có thể được viết dưới dạng N = [p1^(a1/2) * .. * pm^(am/2)] ^ 2 => N chính phương
+ Vậy Số số có ước lẻ nhỏ hơn bằng N = Số số chính phương nhỏ hơn bằng N = sqrt(N) (Các số chính phương này có được bằng cách bình phương các số từ 1..sqrt(N))