DIVIDE AND CONQUER ON ARRAY

Thuật toán chia để trị: ta chia bài toán cần giải quyết thành nhiều bài toán con, giải quyết từng bài toán con, sau đó ta tổng hợp lại để giải bài toán lớn. Thuật toán chia để trị được biết đến tiêu biểu qua giải thuật merge-sort… Mặc dù nó được ứng dụng khá nhiều, nhưng nó không có một cách giải quyết tổng quát cho các bài toán. Ta phải hiểu tư tưởng của nó và áp dụng vào từng trường hợp cụ thể.

Trong bài viết này, tôi sẽ trình bày một trường hợp áp dụng thuật toán chia để trị, tuy chỉ là một trường hợp áp dụng, nhưng dạng này ta gặp rất thường xuyên. Ta sẽ đi đi từ bài toán tổng quát, rồi áp dụng vào ví dụ cụ thể.

Bài toán tổng quát: ta tìm một dãy con liên tiếp trong dãy đã cho để thỏa mãn một tính chất nào đó.

Cách giải quyết: Thông thường với kích thước của dãy khoảng N=10^3, ta dùng hai vòng lặp chạy lồng nhau với độ phức tạp O(N^2) để xét tất cả dãy con và tìm ra dãy con phù hợp nhất.

Khi N lớn hơn một chút, tầm khoảng N=10^5, ta phải có một giải thuật chạy tốt hơn mới giải quyết được. Tôi đã trình bày ở bài viết “two pointers” có thể giải quyết bài toán tìm dãy con liên tiếp trong O(N), tuy nhiên cách làm này không giải quyết mọi bài toán. Bài viết này sẽ trình bày một cách giải quyết khác cho bài toán tìm dãy con liên tiếp nhưng với độ phức tạp O(NlogN).

Ý tưởng giải quyết như sau, với một dãy {a} có N phần tử.

• Nếu dãy đó có 1 phần tử: ta xét trực tiếp phần tử đó thỏa mãn yêu cầu hay không.
• Nếu dãy đó nhiều phần tử, ta sẽ chia ra hai dãy con, mỗi dãy có N/2 phần tử {a1} và {a2}, trường hợp N lẻ thì kích thước hai dãy con chênh lệch nhau một. Kết quả cần tìm sẽ là:
•  Kết quả sẽ nằm hoàn toàn trong {a1},
• Hoặc kết quả sẽ nằm hoàn toàn trong {a2},
• Hoặc kết quả là một dãy liên tiếp nằm trên hai dãy con, một phần là dãy liên tiếp ở cuối {a1} và một phần là dãy liên tiếp nằm ở đầu {a2}.

Để tìm lời giải cho dãy {a1} và {a2}, ta lại tiếp tục chia ra làm hai dãy con. Tương tự vậy cho đến khi tìm được lời giải.

Mã giả:

Độ phức tạp:

Gọi f(N) là độ phức tạp khi tìm lời giải cho dãy {a}.

ð  Độ phức tạp cho việc tìm lời giải cho {a1} là f(N/2) và {a2} là f(N/2).

Gọi g(N) là độ phức tạp cho việc xét trường hợp kết quả nằm ở cả hai dãy con.

Vậy f(N) = 2*f(N/2) + g(N).

Nếu g(N) = O(N), ta có công thức truy hồi quen thuộc f(N) = 2*f(N/2) + O(N), trong trường hợp này độ phức tạp f(N) = O(NlogN).

Vì vậy nếu ta cố gắng giải quyết trường hợp kết quả nằm ở cả hai dãy con {a1} và {a2} trong O(N) thì ta có thể giải quyết cả bài toán với độ phức tạp trong O(NlogN). Ta sẽ xét những ví dụ để hiểu rõ hơn.

Nhìn vào mã giả, để bài toán này, ta chỉ cần tìm cách giải cho trường hợp kết quả nằm ở hai dãy con {a1} và {a2}, thể hiện ở câu Condiser tail of {a1} and head of {a2} trong mã giả, vì hai trường hợp kia chỉ là câu lệnh gọi đệ quy. Nhưng phải giải trường hợp này trong O(N), trong một vài trường hợp ta cũng có thể giải chúng trong O(NlogN) vẫn ok. Như vậy ta đã thấy mấu chốt của vấn đề là ở đâu, tập trung giải quyết nó thì coi như cả bài toán giải được giải quyết.

Ví dụ 1: Theo số liệu thống kê của một công ty về tình hình kinh doanh trong N (1<=N<=10^5) ngày, hằng ngày công ty này có doanh thu là ai (-10^6 <= ai <=10^6), ai có giá trị âm nghĩa là có chi nhiều hơn thu. Người ta cần phân tích xem khoảng thời gian nào công ty có doanh thu là nhiều nhất. Cụ thể là ta cần tìm một dãy con liên tiếp trong dãy {aN} sao cho tổng của chúng là lớn nhất.

Áp dụng bài toán tổng quát nêu ở trên vào trường hợp này. Ta cần giải quyết trường hợp kết quả nằm ở hai dãy con {a1} và {a2}. Rõ ràng để kết quả lớn nhất, thì mỗi phần bên mỗi dãy con cũng lớn nhất.

• Đối với dãy con {a1}, ta chạy từ cuối dãy {a1} cho đến đầu dãy {a1}, mỗi lần chạy ta cộng thêm một phần tử và cập nhật lại tổng có giá trị lớn nhất. Cách làm này chạy trong N/2.
• Đối với dãy con {a2}, ta chạy từ đầu dãy {a2} qua, chạy cho hết dãy và chọn ra dãy con có tổng lớn nhất. Cách làm này cũng chạy trong N/2.
• Tổng hai dãy con tìm được ở trên chính là kết quả cho trường hợp kết quả nằm ở hai dãy. Ta chú ý trường hai dãy con đó có tổng là âm, thì ta ko cần cộng lại hai thằng, mà chỉ lấy thằng lớn nhất.

ð  Ta thấy với cách làm này ta chỉ chạy trong O(N) để giải quyết trường hợp kết quả nằm ở hai dãy con. Như vậy ta hoàn toàn có thể giải quyết bài toán cho toàn bộ dãy trong O(NlogN).

Ý tưởng thì đã xong, ta bắt tay vào hiện thực. Bạn có thể xem code tại đây.

Thật ra bài này có cách làm đơn giản hơn, chỉ chạy trong O(N). Ta để ý nếu ta có dãy con a[i,i+1,…,j] là dãy con có tổng lớn nhất, tức là ai+a(i+1)+…+aj là lớn nhất. Thì rõ ràng các dãy con a[i,i+1,..,k] luôn có tổng lớn hơn hoặc bằng 0, với mọi k<j (nếu tổng này có giá trị nhỏ hơn 0 thì dãy con a[k+1,…,j] có tổng lớn hơn dãy a[i,i+1,…,j], mâu thuẩn với giả thuyết). Từ nhận xét này ta chạy từ trái qua phải, cộng dồn các giá trị ai vào, mỗi lần chạy ta coi tổng này có phải là giá trị lớn nhất hay không. Trong trường hợp tổng này nhỏ hơn hoặc bằng 0 thì ta bỏ nguyên cả đoạn đầu, ta tiếp tục chạy qua phải từ vị trí làm cho tổng nhỏ hơn 0. Do đây không phải là mục đích chính của bài viết, nên tôi không giải thích thêm về cách làm này, bạn có thể xem code đã cải tiến.

Ví dụ 2: Cho một dãy số {aN} có kích thước N (1<=N, ai<=10^5), ta cần tìm các dãy con liên tiếp có kích thước lớn nhất trong dãy sao cho tổng các phần tử đã chọn chia hết cho k (2<=k<=10^5). Nếu có nhiều dãy con thỏa mãn, ta cần in ra tất cả các dãy con như thế, với mỗi dãy con chỉ cần in ra chỉ số đầu và cuối.

Bài toán có 2 ý, ý thứ nhất là ta tìm kích thước dài nhất mà tồn tại dãy con có tổng chia hết cho k, ý thứ hai là in ra các dãy con có kích thước như thế và thỏa mãn tổng chia hết cho k. Nếu ta không tách ra, việc giải quyết vấn đề của ta sẽ hơi khó khăn một chút. Việc đầu tiên là ta giải quyết ý thứ nhất, tìm kích thước dài nhất có thể. Sau khi có được chiều dài này thì việc in ra tất cả các dãy con như thế dễ dàng hơn.

Cũng như ví dụ 1, ta áp dụng bài toán tổng quát vào, vấn đề là cần giải quyết trường hợp dãy dài nhất nằm ở cả hai dãy con. Nếu ta có tổng dãy con bên phải chia k dư x, thì ta cần dãy con dài nhất bên trái chia k dư k-x. Như vậy tổng hai dãy này sẽ chi hết cho k. Bài này ta kết hợp chút xíu quy hoạch động.

Giả sử N1 là chiều dài dãy con {a1}. Gọi f[x] là chỉ số nhỏ nhất cũa dãy con {a1} mà tổng a[f[x], f[x]+1,….,N1] chia k dư x, tức là ta đang lưu lại dãy con dài nhất tính từ bên phải của dãy {a1} mà chia k dư x.

• Đối với dãy con {a1}, ta chạy từ cuối dãy {a1} đến đầu dãy. Mỗi lần chạy đến phần tử thứ i, ta cộng dồn phần tử ai vào tổng S1, giả sử tổng này chia k dư x. Ta cập nhật lại f[x] = i.
• Đối với dãy con {a2}, ta chạy từ đầu dãy cho đến hết dãy. Đến mỗi phần tử ai ta cũng cộng vào tổng S2. Giả sử S2 chia k dư x. Ta xét f[k-x] có giá trị không, nếu có thì ta có một dãy con có tổng chia hết cho k là a[f[k-x],f[k-x]+1,…,i] có kích thước là (i-f[k-x]+1). Qua mỗi lần chạy ta cập nhật lại kích thước dài nhất có thể.
• Việc còn lại là in kết quả ra, tới đây thì chắc dễ dàng hơn ta chỉ thực hiện trâu bò là được, vì việc in ra tất cả dãy con có chiều dài cụ thể chỉ trong độ phức tạp O(N).

Nói thì nhiều như vậy chứ thật sự nó chỉ tập trung vào tìm cách giải quyết trường kết quả nằm ở cả hai dãy con trong O(N). Bạn hãy tự code bài này, có thể so sánh với code mình tại đây.

Trong đoạn code của mình có vài điểm lưu ý:
- Nếu dãy con bên phải chia hết cho k, thì ta tìm dãy con dài nhất bên trái chia hết cho k, chứ không phải tìm dãy con bên trái chia k dư k.
- Việc lưu dãy từ 1->N, chứ không phải từ 0->(N-1). Mục đích của mình là đánh dấu nếu f[x] =0, tức là không có dãy con bên trái chia k dư x. Và dùng hàm memset() của C++ để reset lại giá trị của dãy f[]. Nếu bạn bạn dùng vòng for để reset giá trị của dãy thì chạy rất lâu. 

Tổng kết:

Đối với bài toán tìm dãy con liên tiếp, ta đã có phương pháp “two pointers” để giải quyết, nhưng nó không thể giải hết các bài toán dạng tìm dãy con liên tiếp, ta đã tìm hiểu cách áp dụng chia để trị vào giải quyết dạng này. Tuy mình trình bày hơi dài dòng nhưng mấu chốt cũng chỉ giải quyết một trường hợp kết quả nằm ở cả hai dãy con.

Bài viết đã trình bày một bài toán áp dụng chia để trị để giải quyết, mình cũng hy vọng có ai đó sẽ chia sẻ thêm về việc dùng giải thuật chia để giải quyết bài toán khác.

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