TWO POINTERS

Two pointers là kĩ thuật đơn giản, code ngắn, nhưng hiệu quả. Nó ít được biết đến vì nó rất ít được dùng khi làm ứng dụng và trong chương trình dạy.

Không mất thời gian, ta bắt đầu bằng một ví dụ:
Bạn được giao nhiệm vụ phân tích trên đóng dữ liệu, dữ liệu là dãy số tự nhiên có N phần tử a0, a1, …, a(N-1) , bạn phải tính có bao nhiêu dãy con liên tiếp thỏa mãn tổng của chúng lớn hơn hoặc bằng S(S>0).

Chẳng hạn với dãy số {1, 2, 5, 4, 2}, S=8. Dãy con liên tiếp là dãy được trích từ dãy ban đầu và các phần tử được lấy ra phải liên tiếp nhau. Ta có các dãy con sau thỏa mãn {1, 2, 5}, {1, 2, 5, 4}, {1, 2, 5, 4, 2}, {2, 5, 4}, {2, 5, 4, 2}, {5, 4}, {5, 4, 2}.

Tui chắc chắn bạn đã nghĩ ra cách để tìm ra có bao nhiêu dãy con như thế. Bạn hãy code ra, chạy thử trên bộ dữ liệu này  input . Nếu code của bạn chạy trong 1s mà cho ra kết quả là 302572338891 thì bạn ko cần đọc tiếp bài viết này, và bạn có thể cho mình xin code tham khảo J. Nếu code của bạn không thể chạy cho dữ liệu lớn như vậy hoặc chạy sai kết quả, thì bạn cứ tiếp tục đọc nhé.

Có phải cách của bạn là:

Với cách này chạy ra kết quả đúng, nhưng trong trường hợp xấu nhất nó mất thời gian O(N^2), khó mà ra kết quả trong 1s với N=10^6.

Vấn đề ở đoạn code trên chính là nó cộng lại nhiều lần. Sau khi vòng lặp thứ nhất i=0, nó đã tính Run=a0+a1+…+a(N-1). Đến i=1, nó lại cộng Run=a1+a2+…+a(N-1). Ta phải tìm cách giảm thiểu số lần tính lại nhưng vẫn đảm bảo kết quả đúng.

Ta muốn số lần cộng vào biến Run được giảm xuống, vì thế giá trị của biến Run ở lần chạy trước phải được sử dụng lại ở lần chạy sau, có như thế thì mới giảm số lần chạy được. Bạn thử suy nghĩ một lát rồi hãy tiếp tục đọc.

Và đây là lời giải của tui cho bài toán này:

Ý tưởng đoạn code trên là với mỗi chỉ số end, ta tìm chỉ số start lớn nhất sao cho a[start]+a[start+1]+…+a[end] >=S. Như thế sẽ có start+1 chuỗi con thỏa mãn điều kiện có chỉ số cuối là end. Các dãy đó là {a0, a1, .., a[end]}, { a1,a2 .., a[end]}, {a[start], a[start+1], .., a[end]}. Vì thế ta cộng dồn vào kết quả start+1.

Nhìn vào đoạn code thứ hai, ta thấy vẫn có 2 vòng lặp chạy lồng nhau. Nhưng trên thực tế đoạn code này chỉ chạy trong (2*N) cho tất cả các trường hợp, thay vì chạy trong (N^2) như đoạn code thứ nhất. Ta bắt đầu phân tích:

1. Vòng lặp for sẽ chạy trong N
2. Vòng lặp while có số lần chạy khá phức tạp, nhưng ta để ý: nếu ta cộng tất cả lần chạy của vòng lặp while, thì chính là số lần chạy của biến start từ 0 đến N-1. Với mỗi lần  chạy của vòng lặp for, ta không xác định được số lần chạy của vòng lặp while. Tuy nhiên, tổng số lần chạy của vòng while luôn nhỏ hơn N vì giá trị biến start chạy không thể lớn hơn end, đồng nghĩa không thể lớn hơn N.

Ý tưởng:
Ý tưởng của kĩ thuật này là có hai biến chạy song song nhau, ở đây là start và end. Số lần chạy của biến này không phụ thuộc vào biến kia. Và yêu cầu bài toán thường là tìm dãy con liên tiếp có tính chất: nếu ta có dãy con thỏa mãn A, thì thêm vào một phần tử cũng vẫn thỏa mãn A. Biến start có nhiệm vụ giữ chỉ số đầu của dãy con, biến end giữ chỉ số cuối của dãy con. Tùy bài toán mà ta cho biến start chạy rồi tìm biến end tương ứng, hoặc cho biến end chạy rồi tìm biến start tương ứng. Trong ví dụ trên là biến end chạy và ta tìm biến start tương ứng thỏa tính chất a[start]+a[start+1]+…+a[end] >=S.

Trước khi kết thúc ta xét thêm một ví dụ:

Một bản nhạc hơi dài có N (N=10^6) nốt nhạc, độ cao mỗi nốt nhạc là hi (từ 0 đến 20). Ta cần tìm ra đoạn nhạc có chiều dài nhỏ nhất mà trong đó độ chênh lệch độ cao giữa nốt cao nhất và nốt thấp nhất phải lớn hơn hoặc bằng H (từ 0 đến 20). Nhiệm vụ trước tiên là tìm ra chiều dài nhỏ nhất đó, sau khi có chiều dài nhỏ nhất thì việc in ra các dãi con là dễ dàng.

Nhận xét: bài toán cũng thuộc dạng tìm dãy con liên tiếp. Nếu ta có một dãy thỏa điều kiện độ chênh lệch độ cao giữa nốt cao nhất và nốt thấp nhất phải lớn hơn hoặc bằng H, ta thêm vào một phần tử vào dãy này, thì ta có một dãy mới cũng thỏa tính chất đó ( diễn đạt khác đi [max{ai, x} -min{ai, x}] >= [max{ai} -min{ai }] >= H ).

Cách giải thì tương tự ví dụ trên, nên sẽ không được giải thích lại.

Tổng kết:
Nếu bạn chưa bao giờ dùng kĩ thuật này, tui nghĩ bạn cũng chưa thật sự hiểu nó. Bạn hãy tự giải lại bài toán trên. Bài viết cũng chỉ gợi ý tưởng cho bạn, chứ thực sự mình cũng chưa đủ trình độ để có thể viết một bài cho bạn hiểu liền.
Nếu hứng thú bạn có thể thực hành nhiều hơn về kĩ thuật này tại 
http://codeforces.com/problemset/tags/two%20pointers


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