RANGE OF VALUE

Bài viết này không trình bài về một kĩ thuật giải nào cả, chỉ là một tiểu xảo. Khi giải quyết vấn đề, ta thường chú ý tới kích thước của tập hợp mà không quan tâm đến độ lớn giá trị của các phần tử. Đôi khi nó là mấu chốt để giải quyết vấn đề.

Sau khi mình học xong các giải thuật sort, có bạn nói rằng đã từng đọc đâu đó có giải thuật sort chỉ chạy trong O(N). Lúc đó mình chắc chắn không tin rồi. Nhưng sau khi tìm hiểu thì lại có giải thuật chạy trong O(N), tiếp tục đọc kĩ lại thì ra giải thuật này không tổng quát. Ta sẽ xem chi tiết nó hiện thực như thế nào.

Ví dụ 1: Cho một dãy gồm N (0<N<10^6) số a1, a2,.., aN (0<=ai<=10^6). Bạn hãy sort lại dãy theo thứ tự tăng dần.

Với các giải thuật sort tổng quát, ta so sánh các giá trị của ai và aj, nếu thằng nào nhỏ hơn thì đặt ra trước. Với cách giải cho bài toán sort trong O(N), ta không cần thực hiện một phép so sánh nào cả.

Ta sẽ quét qua tất cà các giá trị của có thể của ai, tức là từ 0->10^6 dựa vào giả thuyết 0<=ai<=10^6. Ta đếm số lần xuất hiện của 0, 1, 2,...10^6 trong dãy {aN}. Nếu có k giá trị 0 trong dãy, ta in ra k số 0, cứ tiếp tục cho 1, 2…10^6

Ví dụ với dãy {1, 5, 2, 1}. Có hai giá trị 1, ta in ra hai số 1, tiếp tục in ra một số 2, không in 3 và 4, cuối cùng là in một số 5. Kết quả là {1, 1, 2, 5}.

Cụ thể code như sau:

Nhận xét:

1.       Với cách làm này, thực tế không phải là O(N). Giả sử giá trị lớn nhất của ai là Max (trong trường hợp này Max=10^6). Độ phức tạp của giải thuật là max{N, Max}. Do trường hợp này N=Max nên ta dễ nhầm lẫn là O(N). Tuy là hai vòng for lồng nhau nhưng đừng lầm tưởng độ phức tạp là O(Max*N) nhé, vì ta có ràng buộc Tổng(b[i])=N.

2.       Nếu miền giá trị của ai lớn lên, nghĩa là giải thuật cũng chạy chậm hơn, mà bộ nhớ dùng nhiều hơn. Vì ta ko lưu dãy {aN}, mà ta lưu số lần xuất hiện của mỗi giá trị {bMax}.

Ví dụ 2:

Cho một dãy N (N<10^6) số nguyên a1, a2,…, aN (0<ai<10^5) và một số nguyên P (P<10^10). Bạn hãy tính toán có bao nhiêu cách chọn hai số nguyên khác nhau ai và aj từ dãy đã cho sao cho ai*aj=P.

Ý tưởng đầu tiên trong đầu mọi người là 2 vòng for chạy lồng nhau với độ phức tạp O(N^2), đúng không? Cách làm này đúng nhưng chạy rất chậm với N=10^6. Với N=10^6 thì ta phải tìm ra giải thuật có thể chạy trong O(N) mới có thể đáp ứng yêu cầu thời gian. Ta để ý, miền giá trị của ai nhỏ hơn 10^5. Ta có thể lưu thành dãy {bM} trong đó b[i] chứa số lần xuất hiện của giá trị i. Như vậy kết quả sẽ là Tổng(b[i]*b[P/i]) với i chạy từ 1->10^5. Vài xử lý nhỏ nhặt nữa ta sẽ có lời giải. 

Bạn có thể tham khảo lời giải bằng C++ tại đây.

Khi ta chú ý vào miền giá trị của các phần tử, ta nhìn bài toán với góc độ khác một tí, thay vì chạy qua hai vòng lặp theo N.

Ví dụ 3 (chú ý ví dụ này)

Cho dãy N số nguyên a1, a2,…, aN (N<10^5 và 0<= ai<=10). Đối với mỗi số, bạn phải in ra có tất cả bao nhiêu số có thứ tự trước nó và nhỏ hơn nó. Cụ thể là với mỗi ai, ta phải đếm có bao nhiêu số trong dãy {a1, a2, .., ai-1} nhỏ hơn ai.

Cách giải thì tương tự như trên, chỉ cần ghi nhận lại số lần lặp lại của các giá trị từ 0->10. Bạn tự code bài này thử nge, có thể xem code bằng C++ tại đây. Điều mình muốn nói ở đây là hai nhận xét sau:

Nhận xét 1

Đối với ví dụ trên, nếu miền giá trị của ai là [-10, 10], rõ ràng ta không thể đếm được số lượng của các giá trị âm, vì trong các ngôn ngữ lập trình thông dụng, không cho phép ta truy xuất chỉ số âm. Ví dụ ta không thể gọi b[-1]++; Tuy nhiên ta có một kĩ thuật giải quyết vấn đề này: dịch chuyển các giá trị một đoạn 10, lúc này miền giá trị là [0, 20]. Khi ta cộng thêm 10, nó không làm ảnh hưởng bản chất của bài toán, vì ta chỉ quan tâm thứ tự của chúng, chứ ko quan tâm giá trị thật của chúng (ai < aj) <=> (ai+10 < aj+10). Đối với ví dụ 2 thì áp dụng chiêu này là ko được rồi, nó cần giá trị thật của ai.

Tới đây ta vẫn làm như trên, code được viết bằng C++ tại đây.

Nhận xét 2:

Ta xét bài toán khó hơn, giá trị của ai trong [0, 10^9]. Rõ ràng thì cách làm này không khả thi. Thứ nhất là bộ nhớ, thứ hai là thời gian chạy. Ta nhận thấy rằng, dù ai nằm trong [0, 10^9], nhưng N<10^5. Vì vậy, chỉ có tối đa 10^5 giá trị trong [0, 10^9] sẽ xuất hiện trong dãy {aN}. Song song đó, ta không quan tâm giá trị thực của chúng, mà ta chỉ quan tâm thứ tự (sự lớn bé) của chúng. Ta sẽ chuyển các giá trị của {aN} từ [0, 10^9] thành [0, N].

Ví dụ ta có dãy 5 phần tử {1, 10^7, 7, 10^7, 10^9} thì kết quả là 0, 1, 1, 2, 4. Ta sẽ chuyển dãy đã cho thành {1, 3, 2, 3, 4} thì kết quả vẫn không thay đổi 0, 1, 1, 2, 4. Vì thứ tự của chúng vẫn không thay đổi: số đầu tiên vẫn nhỏ nhất, số thứ hai thì lớn nhì,…,số cuối cùng vẫn lớn nhất.

Để làm được việc này, ta có thể dùng binary search, tuy nhiên nên dùng các util của các ngôn ngữ lập trình, chẳng hạn map của C++, hay Hashtable của Java…

Tới đây, bài toán của ta là: Cho dãy N số nguyên a1, a2,…, aN (N<10^5 và 1<= ai<=N). Đối với mỗi số, bạn phải in ra có tất cả bao nhiêu số có thứ tự trước nó và nhỏ hơn nó. 
Để giải bài toán này, ta cần dựa vào miền giá trị của ai và một cấu trúc dữ liệu để giải quyết nó. Cấu trúc dữ liệu đó là Binary Index Tree. Ta sẽ tìm hiểu về nó trong bài viết sau về các cấu trúc dữ liệu hay dùng. Bạn có thể tham khảo trước lời giải bằng C++ tại đây, chú ý cách chuyển từ dãy cũ sang dãy mới. Ý tưởng ở đây là ta dùng một hashtable để giữ mapping giữa giá trị cũ và mới.

Tổng kết:

Với bài viết này, tôi chỉ muốn bạn chú ý vào miền giá trị của vấn đề cần giải quyết. Cùng một vấn đề, miền giá trị khác nhau thì độ khó của bài toán khác nhau hẳn.Vì thế ta nên chú ý vào miền giá trị của các phần tử, đôi khi cũng cho ta góc nhìn khác về bài toán.

Người viết: Dương Thành Phong