Thuật toán Ternary Search

Thuật toán Ternary Search

Ternary Search - Tìm kiếm tam phân là một kỹ thuật trong khoa học máy tính dùng để tìm kiếm giá trị lớn nhất (maximum) hay nhỏ nhất (minimum) của một unimodal function, và đây cũng là một ví dụ ứng dụng lớp thuật toán Chia để trị (divide and conquer)

Xét bài toán tìm maximum của hàm f() trên đoạn [A,B]:

- Điều kiện bài toán: Tồn tại một số vị trí x sao cho:

+ Với mọi a,b mà A ≤ a < b ≤ x thì f(a) < f(b)

+ Với mọi a,b mà x ≤ a < b ≤ B thì f(a) > f(b)

- Nhận xét bài toán:

Giả sử tồn tại 2 vị trí m1,m2 (A < m1 < m2 < B) thì ta có 3 trường hợp:

+ f(m1) > f(m2) → kết quả nằm trong đoạn [A,m2]

+ f(m1) < f(m2) → kết quả nằm trong đoạn [m1,B]

+ f(m1) == f(m2) → kết quả nằm trong đoạn [m1,m2]

Code :

int l = 1, r = n; int del = 5; int m1,m2; while ( abs( r - l ) > del ) {     m1 = l + ( r - l ) / 3;     m2 = r - ( r - l ) / 3;     if ( a[ m1 ] > a[ m2 ] ) r = m2;     else     if ( a[ m1 ] < a[ m2 ] ) l = m1;     else     { l = m1; r = m2; } }

Độ phức tạp: O(logN)

Bài tập áp dụng:

1. Elections (Mem SQL Round 2 - Problems C) link problem

Bạn sắp tranh cử lãnh đạo của một thành phố nhỏ và muốn thắng cử. Bạn có danh sách n người sẽ đi bầu cử. Mỗi người sẽ gồm 2 chỉ số: ứng viên mà người đó sẽ bầu (a[i], a[i] = 0 là bầu cho bạn) và số tiền bạn cần hối lộ để người đó bầu mình (b[i], b[i] = 0 nếu a[i] = 0). Tuy nhiên, bạn muốn tối thiểu hóa số tiền phải chi nhưng vẫn đảm bảo thắng cử.

Yêu cầu: Cho danh sách người bầu cử, in ra chi phí cần thiết.

Input:

● Dòng đầu số nguyên n (n ≤ 10^5).

● Dòng i trong n dòng sau chứa 2 số nguyên a[i] và  b[i] (0≤ a[i] ≤ 10^5, 0 ≤ b[i] ≤ 10^4).

Output:

● In ra số tiền bạn cần chi để thắng cử.

Example:

ELECTIONS.INP	ELECTIONS.OUT
5 1 2 1 2 1 2 2 1 0 0	3

Thuật toán sơ khai:

- Hãy định nghĩa “mức ứng cử” là số người tối thiểu bầu cho mình và không có ứng cử viên nào vượt qua mức đó được - ký hiệu là T ( 1 ≤ T ≤ n).

+ Nếu ta chọn mức ứng cử là T, thì những ứng viên có số người bầu cho mình >= T bạn chắc chắn phải mua chuộc 1 số trong đó để số người theo các ứng viên phải đảm bảo

+ Để cho chi phí tối thiểu, dĩ nhiên bạn sẽ chọn những người mà b[i] nhỏ nhất mà theo các ứng viên bạn buộc phải mua chuộc để cho đạt điều kiện

+ Nếu số người bạn mua chuộc vẫn chưa đủ >= T bạn buộc phải mua thêm 1 lượng người cho đủ, gọi x là số người bạn đã mua chuộc, bạn cần mua thêm (T-x) người nữa, và cũng để tối ưu bạn lấy (T-x) người b[i] nhỏ nhất trong số các người mà bạn chưa mua chuộc.

+ Duyệt hết các giá trị T, ta sẽ có đáp án

+ Complex: O(n*numA)  ( num A là số ứng cử viên )

→ Nhận xét: Với n nhỏ ta có thể dễ duyệt dễ dàng, nhưng với yêu cầu đề là : n<=10^5 và numA <=10^5 thì ta cần phải cải tiến thêm 1 chút để thuật toán tốt hơn.

Trong chuyên đề này, dĩ nhiên ta sẽ hướng tới “Ternary Search”.

- Bài toán đặt ra là tìm minimum, vậy để có thể Ternary Search, dãy phải thỏa điều kiện:

+ Tồn tại một số vị trí x sao cho: Với mọi a,b mà A ≤ a < b ≤ x thì f(a) > f(b) và với mọi a,b mà x ≤ a < b ≤ B thì f(a) < f(b) .

→ Ta cần khảo sát xem bài này có thuộc tính chất đó không.

Nhận xét:

- Với mức ứng cử nhỏ, hầu như ta phải mua chuộc tát cả các người bầu cử, khi ta tăng dần mức ứng cử thì số người phải bầu cử ta giảm → số tiền phải mua chuộc giảm.

- Sau khi giảm đến cực tiểu, số tiền lại bị tăng lên do ta phải lấp đầy mức ứng cử, tức là các ứng viên khác có lẽ đã thua phiếu nhưng ta phải đảm bảo đủ số người bầu theo yêu cầu thuật toán.

→ Hàm T() thỏa điều kiện và dĩ nhiên ta có thể áp dụng Ternary Search Min trên hàm này

→ Complex:  O(logN * num A).

Solution: Code

Bài 2: Những con kiến đáng gét (C11 Contest) link problem

Nhà của yenthanh132 dạo này có rất nhiều kiến, mua bao nhiêu quà bánh, kẹo mức gì về chưa kịp ăn là đã bị chúng bu lạ xơi tái ngay. Khổ nổi chúng dường như biết tổ chức theo kiểu quân đội, hay đi kiếm ăn theo từng cụm, lại thường kết hợp với đánh du kích. Nhớ lúc nào đang thấy chúng bò đầy nhà, thế mà sau khi yenthanh132 đi mua bình xịt kiến về là chúng biến mất tâm. @@

Quyết không chịu thua, yenthanh132 quyết tâm tiêu diệt hết lũ kiến trong nhà "một lần và mãi mãi". Thế là yenthanh132 đã nghĩ ra được một kế sách hoàn hảo... đầu tiên anh ta mua một sợi dây dài vô tận và căn ra giữa nhà (nhà yenthanh132 rộng lắm nên dây dài cỡ nào mắc từ đầu nhà đến cuối nhà vẫn còn đc :) ) và sau đó phủ một lớp đường lên sợi dây. Xong việc, yenthanh132 bỏ ra ngoài đi ăn KFC với bạn bè. Đến lúc về, không ngoài dự đoán của yenthanh132 lũ kiến háu ăn đang bu đầy trên sợi dây. Lần này đã có chuẩn bị từ trước nên yenthanh132 lúc về đã tranh thủ mượn được từ tohuuquan một chai thuốc xịt kiến xịn rồi, đảm bảo xịt 1 lần là chết ngay.

Sau khi quan sát thì yenthanh132 đã tính được có tất cả N con kiến trên sợi dây, nếu ta xem sợi dây là trục Ox, nút trái của sợi dây là –oo, nút phải sợi dây là +oo thì con thứ i hiện tại đang ở tọa độ a[i]. Mỗi con kiến đang bò theo 1 hướng với một vận tốc cố định v[i]. v[i] là số dương nếu con kiến đang bò từ trái sang phải với vận tốc là v[i] (đơn vị/s), v[i] là số âm nếu con kiến đang bò từ phải sang trái với vận tốc là –v[i]. Như vậy tại thời điểm t nào đó thì con kiến thứ i sẽ có vị trí là p[i] = a[i] + t*v[i].yenthanh132 chỉ có thể dùng chai thuốc xịt kiến để xịt một lần lên một vị trí nào đó trên sợi dây để giết chết toàn bộ các con kiến một lượt (vì nếu sau lần đầu xịt mà còn các con kiến còn sống thì chúng sẽ phát hiện ra mai phục và chạy trốn ngay). Giả sử yenthanh132 xịt thuốc lên điểm có tọa độ x với liều lượng thuốc là E vào một thời điểm nào đó thì các con kiến có tọa độ nằm trong đoạn [x – E; x + E] sẽ bị tiêu diệt, nếu một thời điểm nào đó cả N con kiến đều đến cùng một vị trí thì ta chỉ cần xịt lên đúng 1 điểm đó với một lượng thuốc rất nhỏ, trường hợp này ta có thể xem như E = 0 (Xem ví dụ để hiểu rõ hơn). Do chai thuốc xịt kiến này là đồ mượn nên yenthanh132 cũng muốn xài tiết kiệm…

Yêu cầu: Hãy giúp yenthanh132 tính xem liều lượng thuốc tối thiểu E mà anh ta cần dùng để tiêu diệt được toàn bộ lũ kiến, biết rằng yenthanh132 có thể xịt thuốc ngay lập tức hoặc quyết định đợi một khoảng thời gian thích hợp để xịt thuốc tiêu diệt toàn bộ lũ kiến.

Input:

• Dòng đầu tiên chứa số N là số lượng các con kiến.
• Dòng thứ 2 chứa N số nguyên a[i] (i từ 1 đến N) là vị trí hiện thời của N con kiến
• Dòng thứ 3 chứa N số nguyên v[i] (i từ 1 đến N) là vận tốc của N con kiến.

Output:

• Một số thực duy nhất là giá trị liều lượng E nhỏ nhất mà yenthanh132 cần sử dụng. In ra kết quả làm tròn đến 3 chữ số thập phân.

Limit:

• Trong 50% số test có 2 ≤ N ≤ 100.
• Trong tất cả các test có 2 ≤ N ≤ 105.
• -109  ≤ a[i], v[i] ≤ 109

Example:

C11ANT.INP	C11ANT.OUT
2 1 2 1 -1	0.000

Note:

• Ban đầu, 2 con kiến đang ở tại vị trí 1 và 2
• Sau 0.5s, 2 con kiến gặp nhau tại vị trí 1.5
• Tận dụng lúc đó yenthanh132 đã xịt một phát với lượng thuốc E = 0 (rất nhỏ, xem như gần bằng 0) tại X = 1.5
• Thế là anh đã giết được một lúc 2 con kiến.

Hướng giải:

- Đầu tiên hãy nhận xét: Với khoảng thời gian ban đầu các con kiến đi về hai hướng khác nhau sẽ làm co lại khoảng cách, đến một mức nào đó khoảng cách lại bị dãn ra đến cực đại.

→ Đây là một hàm f() lõm, vấn đề ta là tìm min sao cho nhanh trên dãy này.

→ Vì liên quan đến số thực nên ta cần tìm một sai số nhỏ hợp lý, ở đây tôi đề xuất là : (10^-16).

Thuật giải:

→ Dùng ternary search trên khoảng thời gian chờ, với mỗi khoảng thời gian T ta xem xét E = ((a[i]+v[i]*T) max - (a[i]+v[i]*T) min)/2.

→ Tìm được E nhỏ nhất là kết quả bài toán.

Complex: O(log*n).

Solution: Code

Bài tập tự giải:

Bài 3: Cubes

Cho n tháp mỗi tháp là tập hợp các khối cube đặt lên nhau, độ cao mỗi tháp là số cube xây dựng nên nó. Drgz yêu sự cân đối do đó ông muốn thay đổi chiều cao các tháp sao cho cuối cùng chiều cao các tháp là bằng nhau. Mỗi bước ông có thể:

• Chuyển 1 cube từ 1 tháp qua tháp khác.
• Loại bỏ 1 cube trong một tháp
• Thêm 1 cube vào một tháp (cube đó được lấy từ một tập vô hạn)

Hãy tìm số lượng bước tối thiểu để Drgz đạt được mong muốn của mình.

+ 1<= n, a[i] <= 1000

Example

Input:

5

3 2 2 5 4

Output:
3