Tác giả: Lê Hùng Sơn - Đại học FPT
Rời rạc hóa là một lĩnh vực lớn có đối tượng nghiên cứu là các tập hợp rời rạc trong khoa học máy tính. Ứng dụng của của phương pháp rất lớn và thường được sử dụng trong rất nhiều kỳ thi lớn. Trong phạm vi chuyên đề ta chỉ xét một số ví dụ để hiểu rõ thêm phương pháp này.
Khi giải thuật lập trình ta hay quen gọi phương pháp rời rạc hóa là nén số. Thật vậy, đúng như tên gọi, bản chất của phương pháp ta hiểu nôm na là đưa các vùng dữ liệu lớn về vùng dữ liệu nhỏ để dễ xử lý, sao cho vẫn thỏa mãn yêu cầu của bài toán đặt ra.
Kỹ thuật bổ trợ trong phương pháp này là đánh lại số thứ tự hay còn được gọi là nén số, được thực hiện như sau:
Ví dụ: a = {100, 100, 2000, 1500, 900000} → b = {1,1,3,2,4}
val[i] = a[i], pos[i] = i (pos để lưu vị trí đi kèm giá trị a[i])val[ ] chú ý khi swap(val[i],val[j]) nhớ swap(pos[i],pos[j]).dem = 0, last = max, duyệt các giá trị val[i] nếu last khác val[i] thì: dem++, last = val[i]; ở mỗi bước ta cập nhật b[pos[i]] = dem.Kết thúc quá trình trên, ta nhận được mảng b[] là nén từ mảng a[] với độ phức tạp thao tác nén này là .
Cho n số nguyên số nguyên với và 2 số , . Hãy đếm xem có bao nhiêu cặp thỏa .
Input:
Output:
Example:
C11SEQ.INP
4 2 4
1 2 3 4
C11SEQ.OUT
4
Tiếp theo, ta có:
Nhận xét 1: là 2 số cố định.
Nhận xét 2: Quan hệ <= hay >= cho ta thấy: không cần quan tâm giá trị của các số mà chỉ cần đảm bảo quan hệ <= hay >= là được. Ví dụ: 1 < 5 ta có thể nén thành 1 < 2 chả ảnh hưởng kết quả bài toán.
Nhận xét 3: Quá lắm chỉ có phần tử cho tất cả các giá trị: , với thì đây là con số nhỏ.
Từ 3 nhận xét trên ta sẽ tìm cách đưa về các mảng nhỏ không quá phần tử để dễ dàng quản lý:
Ta lập một mảng mới có 3*n phần tử: n phần tử dạng , n dạng , n dạng , nhớ lưu vị trí đi kèm.
Bây giờ tiến hành sort mảng đó lại, và ta tiến hành đánh số lai mảng đó, gọi các mảng là các giá trị sau khi đánh số lại của .
Ta tiến hành duyệt các vị trí i, dùng 1 cây Segment Tree hoặc Binary Indexed Tree để quản lý và đếm:
Độ phức tạp: .
Ngoài cách này ra, ta còn 1 cách dùng Phương pháp chia để trị, sẽ có trong các tài liệu sắp tới.
Code tham khảo (pascal):
// Code phần nén số:
// ở đây thay vì dùng 3 mảng p1[i], p2[i], p3[i] mình tận dụng luôn mảng a:
// * a[i] = p1[i], a[n + i] = p2[i], a[2*n + i] = p3[i]
procedure unzip;
var i,j,del:longint;
begin
sort(1,3*n);
A[3*n+1].val:=high(longint);
i:=1; del:=0;
repeat
inc(del);
j:=i;
while A[i].val=A[j].val do
begin
B[A[j].pos]:=del;
inc(j);
end;
i:=j;
until i=3*n+1;
end;
// Phần tính toán kết quả bằng Binary Indexed Tree
for i:=n downto 2 do
begin
update(B[i]);
res:=res+get(B[i-1+2*n])-get(B[i-1+n]);
end;
Cho dãy số nguyên và số hãy tìm số m nhỏ nhất sao cho có thể chia dãy đã cho thành k phần, mỗi phần là 1 đoạn các phân tử liên tiếp, và phải đảm bảo tổng mỗi phần không quá m.
Input:
Output:
Example:
QBSEGPAR.INP
9 4
1 1 1 3 2 2 1 3 1
QBSEGPAR.OUT
5
Nhận xét 1: Bài toán yêu cầu tìm m nhỏ nhất, theo kinh nghiệm thì khi bài toán bảo tìm giá trị nhỏ nhất hay lớn nhất nhưng không xác định được từ dữ liệu bài thì ta nên nghĩ đến chặt nhị phân. Vùng giá trị chặt có thể chọn từ là vừa hợp, cái này là tùy chọn, còn tối ưu nhất chỉ cần chặt trong khoảng .
Nhận xét 2: Nếu ta có 1 giá trị m xác định, ta chia được ít nhất là a đoạn, chia nhiều nhất là b đoạn, nếu tồn tại k mà thì luôn có cách chia k đoạn thỏa mãn. Để xác định được a và b ta dùng phương pháp Quy hoạch động.
Chặt nhị phân không khó, ở đây khó là phương pháp _quy hoạch động _cho thỏa mãn thời gian. Công thức sơ khai như sau:
Khởi tạo: fmax[0] = 0, fmin[0] = 0, fmax[i] = -max (i != 0), fmin[i] = INF (i != 0).
Công thức:
fmax[i] = max(fmax[i], fmax[j] + 1) với j < i và S[i] - S[j] <= m.fmin[i] = min(fmin[i], fmin[j] + 1) với j < i và S[i] - S[j] <= m.Nhận thấy độ phức tạp đây là không thể đáp ứng được thời gian yêu cầu là 1s nhưng ở trường hợp quá bí ý tưởng đây không phải giải pháp tồi giúp lấy được một ít điểm lẻ.
Để nhanh được chỉ có cách là cải tiến sao cho tính mảng Quy hoạch động được nhanh, ở đây ta để ý quan hệ chỉ cần biến đổi thành → giải pháp đã phần nào sáng sủa hơn và nếu tinh ý thì đây chỉ là bài toán 1 chiều, "một nửa" của ví dụ 1 ở trên thôi → Bây giờ ta chỉ cần rời rạc hóa nó đi thay vì , ta có mảng lưu các giá trị và , ta sẽ tính dựa vào 1 cây Binary Indexed Tree cho đơn giản thay vì đếm như bài trên, vấn đề ở đây chỉ là tìm max min, và update max, min.