07.1.Convex Hull Technique

Giới thiệu

Dù tên gọi có vẻ giống với bài toán tìm bao lồi tập điểm trong hình học, nhưng thực chất kỹ thuật này không hề tìm bao lồi. Tuy vậy, những kiến thức về hình học, đặc biệt là về tính hệ số góc, giao điểm và sự tưởng tượng về ý nghĩa của bao lồi sẽ giúp chúng ta hiểu được cách hoạt động của kỹ thuật này.

Tài liệu tham khảo

• Steven Halim, Competitive Programming 4, book 2, page 558 -->560

• Codeforce Tutorial, Convex Hull Trick - Geometry being useful

• USACO Guide - Convex Hull Trick

• Tài liệu chuyên đề Duyên Hải Bắc Bộ 2023

Dẫn nhập

Convex Hull Trick là một kỹ thuật được sử dụng để xác định hiệu quả phần tử nào của tập hợp các hàm tuyến tính đạt giá trị cực trị với một giá trị nhất định của biến độc lập. Kỹ thuật này có thể được sử dụng để tối ưu hóa các bài toán quy hoạch động với một số điều kiện nhất định.

Kỹ thuật Bao Lồi có thể áp dụng cho các phép truy hồi sau:

Công thức truy hồi (1)

Không gian trạng thái là O(N), cứ mỗi trạng thái chúng ta cần lặp qua N lần tính, nên độ phức tạp về thời gian tương tương O(N^2). Để dễ hiểu chúng ta quan sát hình sau: 

Hình 1 - Đường thẳng cho giá trị nhỏ nhỏ tại từng điểm x

Nguồn ảnh: Steven Halim, CP4, Book2, Page 558

Tại một vị trí Xi bất kỳ, chúng ta muốn biết đường thẳng nào trong số N đường thẳng đó cho ta giá trị nhỏ nhất. Như vậy chúng ta phải duyệt qua tất cả các Xi, cứ mỗi Xi như vậy chúng ta thế vào tính giá trị cho từng Li tại đó để tìm min.

Kỹ thuật CHT cho phép chúng ta giảm độ phức tạp này xuống còn O(NlogN). Trước hết chúng ta đưa công thức truy hồi 1 về dạng quen thuộc bằng cách đổi một số tên gọi: dp(i) <--y, g(i) <--x, h(i) <--m, như vậy công thức truy hồi 1 trở thành:

Đây là phương trình của các đường thằng, được biểu diễn tương tự như hình 1. Nếu như chúng ta có được một thứ tự giảm dần của hệ số góc của các đường thẳng này, chúng ta sẽ có được đường bao lồi min như đường gấp khúc in đậm trong hình 1. Đó chính là điều kiện tiên quyết để chúng ta sử dụng được kỹ thuật này.

Khi các đường thẳng đã cho tạo ra một đường gấp khúc lồi như trên, với hai điểm minh họa X1 và X2 như trong hình, vùng min sẽ được chia làm ba vùng: [-oo, X1] tương ứng đường L1, [X1, X2] tương ứng với L2 và [X2, +oo] tương ứng với L3. Một khi chúng ta có được những vùng này trước, với một giá trị x bất kỳ cần tính, chúng ta có thể tìm được vùng tương ứng của nó trong thời gian logN bằng binary search. 

Vấn đề ở chỗ việc tính dp(i) là tuần tự cho từng vị trí, mỗi vị trí như vậy có một đường thằng mới được thêm vào và chúng ta phải cập nhật lại vùng. Bước tạo ra vùng này nếu vét trâu vẫn cần O(N^2) thời gian.

Optimization: O(NlogN) solution when h(k) ≥ h(k+1) - hệ số góc giảm dần

Nếu các đường thẳng được xếp theo thứ tự giảm dần hệ số góc, chúng ta có thể cập nhật vùng bằng cách loại bỏ đi những đường thẳng không quan trọng trong vùng trước đó. Chúng ta quan sát hình sau:

Hình 2 - Cập nhật range khi thêm đường mới

Nguồn ảnh: Steven Halim, CP4, page 558

Nhìn lại hình 1 khi đường gấp khúc min của chúng ta là L1, L2, L3, nhưng khi L4 được thêm vào, đường gấp khúc min bây giờ là L1, L2 và L4. L3 trở thành đường không quan trọng và đã bị loại ra. Việc loại một đường thẳng nằm trong đường gấp khúc thực hiện như sau:

Khi chúng ta thêm đường L4, chúng ta xét thấy giao điểm của L4 và L3 (là đường cuối cùng trong đường gấp khúc) nằm bên trái giao điểm của L3 và L2 (đường kế cuối) thì lúc này đường L3 không còn quan trọng nữa, vì hệ số góc các đường thẳng giảm dần nên nếu đều này xảy ra nghĩa là L3 sẽ luông nằm hoàn toàn trên đường gấp khúc. 

Khi loại L3 ra rồi chúng ta cứ lần ngược về xét tương tự để loại những đường không quan trọng khác.

Có thể một số bạn sẽ thắc mắc việc tìm giao điểm hai đường thẳng để xét những điều trên là phức tạp. Tuy nhiên, nó lại rất đơn giản vì chúng ta chỉ cần biết điểm nào nằm bên trái điểm nào nên chúng ta chỉ cần xét hoành độ x. Ví dụ cần lấy hoành độ giao điểm của đường L1 với phương trình y  = m1.x + c1 và đường L2 với phương trình y = m2.x + c2. Vì giao điểm có cùng tung độ y nên hoành độ là nghiệm phương trình m1.x + c1 = m2.x + c2 ==> x = (c2 - c1)/(m1 - m2).

Đoạn code sau đây mô tả quá trình thêm một đường thẳng mới vào đường gấp khúc min. Trong đó có dùng một struct tlines để mô tả các đoạn thẳng, mỗi đoạn có ba thành phần m, c, p tương ứng là hệ số góc, chặn và giao điểm của nó với đường thẳng trước đó trong đường gấp khúc.

struct tline {

       int m, c;

       double p;

};

vector <tline> lines;

double getX(int m1, int c1, int m2, int c2){

        return (double)(c1 - c2)/(m2 - m1);

}

void addLine(int m, int c){

         double p = -INF;

         while(!lines.empty()){

                    p = getX(m, c, lines.back().m, lines.back().c);

                    if( p < lines.back().p - EPS) lines.pop_back();

         }

         lines.push_back((tline){m, c, p});

}

Nguồn: Steven Halim, CP4, book 2, page 559

Đường thằng đầu tiên được add vào sẽ có p = -INF; mỗi đường thẳng sẽ được add vào là lấy ra không quá một lần, Vector lines chứa các đường quan trọng thuộc đường gấp khúc min theo thứ tự giảm dần của hệ số góc.

Khi có được đường gấp khúc lines, với mỗi x cần truy vấn, chúng ta sẽ binary search để tìm đường trong lines cho cho giá trị y nhỏ nhất. Các em tham khảo đoạn code sau:

int getBestY(int x){

      int k = 0;

      int L = 0, R = lines.size() - 1;

      while (L <= R){

                 int mid = (L+R)  >> 1;

                 if (lines[mid].p <= x+EPS)

                        k = mid, L = mid +1;

                 else

                        R = mid - 1;

      }

      return lines[k].m*x + lines[k].c;

}

Nguồn: Steven Halim, CP4, book 2, page 560

Trong hàm main, chúng ta thực hiện truy vấn như sau:

int ans = 0;

for (int i = 1; i<=n; i++){

         if(i>1) ans = getBestY(g[i]);

         addLine(h[i], ans);

}

cout<<ans<<"\n";

Nguồn: Steven Halim, CP4, book 2, page 560

Optimization: O(N) solution when h(k) ≥ h(k+1) and g(k) ≤ g(k +1)

Nếu chúng ta có thêm điều kiện g(k) <= g(k+1), chúng ta sẽ biết được rằng chỉ số các đường trong đường gấp khúc sẽ không giảm trừ khi chúng ta thêm đường mới (làm một số đường trong đó có khả năng bị loại). Lúc này chúng ta có thể dùng kỹ thuật hai còn trỏ (two pointer), một con giữ vị trí sau cùng mà chúng ta dùng lấy giá trị min_y, một con chạy tới xem chúng ta cần di chuyển bao nhiêu chỉ số để đến vị trí x cần truy vấn. Như vậy từ độ phức tạp logN của binary search, chúng ta giảm xuống được O(1) cho thao tác tìm min_y.

Các em tham khảo đoạn code sau:

int getBestYFaster(int x){

           static int k = 0;

           k = min(k, (int)lines.size() - 1);

           while(k+1 < (int)lines.size() && lines[k+1].p <= x+EPS) ++k;

           return lines[k].m*x + lines[k].c;

}

Nguồn: Steven Halim, CP4, book 2, page 560

Bài tập ví dụ

Bài 1. E. The Fair Nut and Rectangles 

Tóm tắt:

Trên mặt phẳng tọa độ cho n hình chữ nhật. Hình chữ nhật thứ i có tọa độ góc trái-dưới là (0,0) và tọa độ góc trên-phải là (xi, yi). Mỗi hình chữ nhật được gán một giá trị ai  - trọng số của nó. Không có hai hình chữ nhật lồng nhau.

Giá trị của một tập hợp S các hình chữ nhật được tính bằng diện tích phần mặt phẳng tọa độ bị phủ bởi các hình chữ nhật này trừ đi tổng trọng số các hình chữ nhật trong tập S.

Yêu cầu: Hãy tìm tâp S có giá trị lớn nhất

Input:

·      Dòng 1: Số nguyên dương n (n<=10^6)

·      Dòng 2... n+1: Dòng i+1 chứa ba số nguyên xi, yi, ai thể hiên hình chữ nhật thứ i có đỉnh trên-phải là (xi, yi) và có trọng số ai. (1<=xi, yi <=10^9; 0<= ai <= xi*yi)

Output: In ra một số nguyên - Giá trị lớn nhất của một tập S các hình chữ nhật 

Ví dụ:

Phân tích:

Trước tiên chúng ta sắp xếp các hình chữ nhật tăng dần theo hoành độ x, như vậy mặc định tung độ y của chúng cũng giảm dần do điều kiện đề bài đưa ra là không có hai hình chữ nhật lồng nhau.

Đặt f[i] là Giá trị lớn nhất khi hình chữ nhật cuối cùng là hình i. Ta có công thức qui hoạch động: 

Xét các đường thằng Lj(z) = f[j] + xj *z, khi j tăng thì xj cũng tăng --> chúng ta có thể áp dũng kỹ thuật bao lồi dưới cho tập đường thẳng này. Kết hợp điều kiện - yi tăng để giảm thời gian tính toán xướng O(N) nhưng phân tích ở trên.

Nguồn: Tài liệu chuyên đề DHBB 2023 - Convex Hull Trick

Code tham khảo các em có thể xem tại:

Codeforce Tutorial: https://codeforces.com/blog/entry/63823?mobile=true

USACO Guide: https://usaco.guide/plat/convex-hull-trick?lang=cpp

Một số bài khác

Một số bài khác cùng chủ đề được phân tích rất chi tiết các em có thể tham khảo tại: https://robert1003.github.io/2020/02/17/dp-opt-convex-hull-trick.html

Nhiệm vụ:

Nhiệm vụ 1: Thực hiện contest ngắn - Luyện tập Convex Hull Trick 1