Đăng nhập để tham gia lộ trình luyện tập

BINARY SEARCH

Binary Search không chỉ là kỹ thuật tìm một giá trị trong mảng đã sắp xếp. Trong lập trình thi đấu, tư duy quan trọng hơn là nhận ra một ranh giới đơn điệu: trước ranh giới mọi trạng thái thuộc một phía, sau ranh giới mọi trạng thái thuộc phía còn lại. Khi đó ta không cần thử từng giá trị mà có thể loại bỏ một nửa miền tìm kiếm sau mỗi bước.

Nếu miền có kích thước $W$, Binary Search thường cần khoảng

$$O(\log W)$$

lần kiểm tra. Với Binary Search the Answer, nếu mỗi lần kiểm tra có độ phức tạp $T$, tổng thời gian thường là

$$O(T\log W).$$

Ba câu hỏi cốt lõi khi gặp một bài có khả năng dùng Binary Search là:

• miền tìm kiếm là gì;
• điều kiện đúng/sai theo tham số có đơn điệu hay không;
• cần tìm đúng giá trị, vị trí đầu tiên đúng hay vị trí cuối cùng đúng.

Một predicate đơn điệu thường có một trong hai dạng:

$$F,F,F,\ldots,F,T,T,\ldots,T$$

hoặc

$$T,T,T,\ldots,T,F,F,\ldots,F.$$

Binary Search thực chất là tìm đúng điểm đổi trạng thái đó.

Giai đoạn 1 - Tìm kiếm trên dãy đã sắp xếp: exact, lower_bound, upper_bound

Đây là nền tảng của toàn bộ chủ đề. Điều kiện bắt buộc là dữ liệu phải có thứ tự phù hợp với phép so sánh đang dùng.

Tìm đúng một giá trị

Với dãy tăng $a[0],a[1],\ldots,a[n-1]$, ta cần tìm vị trí có giá trị bằng $x$.

Tại vị trí giữa $m$:

• nếu $a[m]=x$, đã tìm thấy;
• nếu $a[m]<x$, mọi vị trí từ trái đến $m$ đều không thể là đáp án;
• nếu $a[m]>x$, mọi vị trí từ $m$ đến phải đều không thể là đáp án.

Mã giả:

trái = 0
phải = n - 1

trong khi trái <= phải:
    giữa = trái + (phải - trái) / 2

    nếu a[giữa] == x:
        trả về giữa

    nếu a[giữa] < x:
        trái = giữa + 1
    ngược lại:
        phải = giữa - 1

trả về không tìm thấy

Độ phức tạp:

$$O(\log n).$$

Tìm phần tử đầu tiên không nhỏ hơn $x$

lower_bound trả về vị trí đầu tiên thỏa

$$a[i]\ge x.$$

Ta có thể xem predicate

$$P(i)=[a[i]\ge x].$$

Vì dãy đã tăng, chuỗi giá trị của $P(i)$ có dạng

$$F,F,\ldots,F,T,T,\ldots,T.$$

Mã giả:

trái = 0
phải = n

trong khi trái < phải:
    giữa = trái + (phải - trái) / 2

    nếu a[giữa] >= x:
        phải = giữa
    ngược lại:
        trái = giữa + 1

trả về trái

Dùng khoảng nửa mở $[trái, phải)$ cho phép kết quả bằng $n$ khi không có phần tử nào thỏa.

Tìm phần tử đầu tiên lớn hơn $x$

upper_bound trả về vị trí đầu tiên thỏa

$$a[i]>x.$$

Mã giả:

trái = 0
phải = n

trong khi trái < phải:
    giữa = trái + (phải - trái) / 2

    nếu a[giữa] > x:
        phải = giữa
    ngược lại:
        trái = giữa + 1

trả về trái

Từ hai boundary này suy ra nhiều công thức thực chiến.

Số phần tử nhỏ hơn $x$:

$$\operatorname{count}(<x)=\operatorname{lower\_bound}(x).$$

Số phần tử không lớn hơn $x$:

$$\operatorname{count}(\le x)=\operatorname{upper\_bound}(x).$$

Số phần tử bằng $x$:

$$\operatorname{count}(=x) = \operatorname{upper\_bound}(x) - \operatorname{lower\_bound}(x).$$

Số phần tử thuộc đoạn giá trị $[L,R]$:

$$\operatorname{count}(L\le a_i\le R) = \operatorname{upper\_bound}(R) - \operatorname{lower\_bound}(L).$$

Predecessor và successor

Phần tử lớn nhất nhỏ hơn $x$ là phần tử ngay trước lower_bound(x), nếu vị trí đó tồn tại.

Phần tử nhỏ nhất lớn hơn $x$ chính là upper_bound(x).

Điểm dễ sai nhất ở giai đoạn này là duplicate. Khi dãy có nhiều phần tử bằng nhau, tìm thấy một vị trí bất kỳ chưa chắc đủ. Hãy xác định chính xác đề cần một vị trí bất kỳ, vị trí đầu tiên, vị trí cuối cùng hay số lượng phần tử.

Giai đoạn 2 - Tiền xử lý, tìm biên, k-th và tìm trên miền giá trị

Binary Search không nhất thiết chạy trực tiếp trên dãy gốc. Nhiều bài chỉ trở nên đơn điệu sau khi ta tiền xử lý.

Binary Search trên prefix sum

Giả sử $a_i\ge 0$ và

$$prefix[i]=a_1+a_2+\cdots+a_i.$$

Khi đó

$$prefix[1]\le prefix[2]\le\cdots\le prefix[n].$$

Nếu cần tìm vị trí đầu tiên mà tổng tiền tố đạt ít nhất $k$, ta tìm

$$\min i\;:\;prefix[i]\ge k.$$

Đây chính là lower_bound trên mảng prefix.

Mã giả:

tính prefix

với mỗi truy vấn k:
    tìm vị trí đầu tiên i sao cho prefix[i] >= k
    dùng lower_bound trên prefix

Nếu $a_i$ có thể âm, prefix không còn chắc chắn đơn điệu và cách này không còn hợp lệ.

Tiền xử lý các vị trí xuất hiện

Một mẫu phổ biến khác là lưu, với mỗi giá trị hoặc ký tự, danh sách các vị trí xuất hiện theo thứ tự tăng.

Khi đang ở vị trí $p$ và cần lần xuất hiện tiếp theo của giá trị $v$, ta tìm phần tử đầu tiên trong danh sách vị trí của $v$ lớn hơn $p$.

Mã giả:

với mỗi giá trị v:
    lưu danh sách vị trí xuất hiện của v theo thứ tự tăng

vị_trí_hiện_tại = -1

với mỗi giá trị cần ghép v:
    dùng upper_bound để tìm vị trí đầu tiên > vị_trí_hiện_tại

    nếu không tồn tại:
        kết luận không thể ghép

    cập nhật vị_trí_hiện_tại

Nếu chuỗi truy vấn dài $m$, độ phức tạp thường là

$$O(m\log n).$$

Tìm phần tử k-th bằng search-by-value

Đôi khi ta không thể hoặc không nên sinh toàn bộ tập giá trị rồi sắp xếp. Thay vào đó, ta Binary Search trực tiếp trên miền giá trị.

Giả sử ta có hàm

$$count\_le(x)=\text{số phần tử của cấu trúc có giá trị }\le x.$$

Vì $count\_le(x)$ không giảm theo $x$, phần tử nhỏ thứ $k$ là

$$\min x\;:\;count\_le(x)\ge k.$$

Mã giả:

trái = giá trị nhỏ nhất có thể
phải = giá trị lớn nhất có thể

trong khi trái < phải:
    giữa = trái + (phải - trái) / 2

    nếu count_le(giữa) >= k:
        phải = giữa
    ngược lại:
        trái = giữa + 1

trả về trái

Trọng tâm không nằm ở vòng Binary Search mà ở cách tính count_le(x) đủ nhanh.

Nếu count_le(x) mất $T$ thời gian và miền giá trị có độ rộng $W$, tổng độ phức tạp là

$$O(T\log W).$$

Giai đoạn 3 - Binary Search trên cấu trúc ẩn, đường đi và order statistics

Ở giai đoạn này, dãy cần tìm không nhất thiết tồn tại dưới dạng một vector rõ ràng. Ta tìm trên một cấu trúc mà thứ tự đã được tạo ra bởi tiền xử lý hoặc một bất biến của thuật toán.

Binary Search trên một đường đi hoặc danh sách tổ tiên đã có thứ tự

Nếu các giá trị trên một đường đi đã được sắp theo một tiêu chí đơn điệu, ta có thể tìm boundary trực tiếp trên đường đi đó.

Điều cần chứng minh không phải là toàn bộ đồ thị hay cây được sắp xếp, mà là miền đang tìm kiếm cụ thể có thứ tự đủ để áp dụng Binary Search.

Mẫu tư duy:

xác định dãy trạng thái hoặc giá trị trên đường đi

chứng minh trạng thái thỏa điều kiện chỉ đổi đúng một lần

Binary Search vị trí boundary trên dãy đó

Nếu thứ tự trên đường đi bị phá vỡ, Binary Search theo chỉ số không còn đúng.

Chọn phần tử theo thứ hạng từ cấu trúc dữ liệu

Một số cấu trúc lưu tần suất hoặc tổng prefix. Nếu cần tìm vị trí nhỏ nhất có prefix ít nhất $k$, ta có thể Binary Search trên chỉ số.

Với hàm prefix

$$S(i)=\sum_{j=1}^{i}f_j,$$

nếu $f_j\ge 0$ thì $S(i)$ không giảm.

Ta tìm

$$\min i:S(i)\ge k.$$

Mã giả:

trái = 1
phải = n

trong khi trái < phải:
    giữa = trái + (phải - trái) / 2

    nếu prefix_sum(giữa) >= k:
        phải = giữa
    ngược lại:
        trái = giữa + 1

trả về trái

Nếu mỗi truy vấn prefix_sum mất $O(\log n)$ thì việc Binary Search như trên mất

$$O(\log^2 n).$$

Một số cấu trúc có kỹ thuật select trực tiếp tốt hơn; khi đó không nên cố giữ Binary Search nếu không cần thiết.

LIS theo tư duy patience

Với bài dãy con tăng dài nhất (Longest Increasing Subsequence - LIS), ta duy trì

$$tails[len]$$

là giá trị kết thúc nhỏ nhất có thể của một dãy con tăng độ dài len + 1.

Mảng tails luôn tăng, nên có thể dùng lower_bound.

Với LIS tăng nghiêm ngặt, tại giá trị $x$ ta tìm vị trí đầu tiên thỏa

$$tails[pos]\ge x.$$

Sau đó thay tails[pos] bằng $x$.

Mã giả:

tails = rỗng

duyệt từng x trong dãy:
    pos = vị trí đầu tiên trong tails có giá trị >= x

    nếu pos nằm ngoài tails:
        thêm x vào cuối
    ngược lại:
        tails[pos] = x

đáp án = kích thước tails

Độ phức tạp:

$$O(n\log n).$$

Nếu bài yêu cầu dãy không giảm thay vì tăng nghiêm ngặt, boundary thường đổi từ lower_bound sang upper_bound. Đây là một ví dụ điển hình cho việc chỉ thay một dấu so sánh nhưng ý nghĩa bài toán thay đổi hoàn toàn.

Giai đoạn 4 - Binary Search the Answer: minimum feasible, first true

Đây là bước chuyển quan trọng từ “tìm trong dữ liệu” sang “tìm đáp án”.

Giả sử đáp án là một số nguyên $x$. Ta định nghĩa:

$$P(x)= \begin{cases} \text{true}, & \text{nếu với giới hạn }x\text{ bài toán khả thi},\\ \text{false}, & \text{ngược lại}. \end{cases}$$

Nếu $P(x)$ có dạng

$$F,F,\ldots,F,T,T,\ldots,T,$$

thì ta cần tìm first true.

Đây thường là các câu hỏi dạng:

• giá trị nhỏ nhất sao cho đủ;
• thời gian nhỏ nhất để hoàn thành;
• dung lượng nhỏ nhất;
• giới hạn lớn nhất trên từng đoạn nhưng cần tối thiểu hóa giới hạn đó;
• số thao tác nhỏ nhất để điều kiện trở nên khả thi.

Template first true trên miền nguyên

trái = LO
phải = HI

trong khi trái < phải:
    giữa = trái + (phải - trái) / 2

    nếu can(giữa) == true:
        phải = giữa
    ngược lại:
        trái = giữa + 1

trả về trái

Cận LO và HI phải bao phủ đáp án.

Tư duy decision problem

Bài tối ưu hóa thường khó vì phải “tìm tốt nhất”. Sau khi cố định $x$, bài toán thường trở thành câu hỏi đơn giản hơn:

Với giới hạn $x$, có làm được hay không?

Quy trình chuẩn là:

1. Chọn tham số đáp án $x$.
2. Viết can(x).
3. Chứng minh can(x) đơn điệu.
4. Binary Search boundary.

Ví dụ tổng quát về chia dãy thành không quá $k$ đoạn với tổng mỗi đoạn không vượt quá $x$:

can(x):
    số_đoạn = 1
    tổng = 0

    duyệt từng giá trị a:
        nếu a > x:
            trả về false

        nếu tổng + a <= x:
            tổng += a
        ngược lại:
            số_đoạn += 1
            tổng = a

    trả về số_đoạn <= k

Khi $x$ tăng, điều kiện “mỗi đoạn có tổng không quá $x$” chỉ dễ hơn, nên predicate có dạng False rồi True.

Nếu can(x) mất $O(n)$ và miền đáp án có độ rộng $W$, tổng độ phức tạp là

$$O(n\log W).$$

Mở cận trên khi chưa biết HI

Nếu chưa biết một cận trên chắc chắn nhưng biết rằng với $x$ đủ lớn thì can(x) sẽ đúng, có thể mở cận theo lũy thừa hai.

hi = 1

trong khi can(hi) == false:
    hi = hi * 2

Trong code thực tế phải chặn overflow. Nếu giới hạn số nguyên lớn, cần kiểm tra trước khi nhân hai.

Chống overflow trong predicate

Các biểu thức như

$$a\cdot b,\qquad a+b,\qquad \sum \left\lfloor\frac{x}{a_i}\right\rfloor$$

có thể vượt long long trước khi được so sánh.

Hai cách thường dùng:

• tính trung gian bằng kiểu rộng hơn;
• dừng sớm khi tổng đã đạt hoặc vượt ngưỡng cần thiết.

Ví dụ:

tổng = 0

duyệt từng phần tử:
    tổng += đóng_góp

    nếu tổng >= mục_tiêu:
        trả về true

Không cần tiếp tục tính một tổng mà ta chỉ quan tâm nó đã đạt ngưỡng hay chưa.

Giai đoạn 5 - Maximum feasible, max-min, k-th và oracle tham lam hoặc chuỗi

Nếu predicate có dạng

$$T,T,\ldots,T,F,F,\ldots,F,$$

ta cần tìm last true.

Các bài dạng này thường hỏi:

• khoảng cách nhỏ nhất lớn nhất có thể;
• chiều cao lớn nhất vẫn thỏa điều kiện;
• sản lượng lớn nhất có thể tạo ra;
• số lượng tối đa có thể xóa hoặc chọn;
• tham số lớn nhất mà một cấu hình vẫn khả thi.

Template last true

Để tránh vòng lặp khi còn hai giá trị, lấy mid lệch phải:

$$mid=\left\lfloor\frac{L+R+1}{2}\right\rfloor.$$

Mã giả:

trái = LO
phải = HI

trong khi trái < phải:
    giữa = trái + (phải - trái + 1) / 2

    nếu can(giữa) == true:
        trái = giữa
    ngược lại:
        phải = giữa - 1

trả về trái

Mẫu max-min

Một lớp bài rất quan trọng là:

Chọn cấu hình sao cho giá trị nhỏ nhất giữa các phần tử được chọn là lớn nhất.

Ta thử một ngưỡng $d$ và hỏi:

Có thể tạo cấu hình mà mọi khoảng cách hoặc chất lượng đều ít nhất $d$ hay không?

Nếu có thể với $d$, chắc chắn có thể với mọi $d'<d$. Vì vậy predicate là True rồi False.

Mẫu greedy:

can(d):
    chọn phần tử đầu tiên
    vị_trí_cuối = vị trí vừa chọn
    số_lượng = 1

    duyệt các ứng viên theo thứ tự:
        nếu khoảng cách từ ứng viên đến vị_trí_cuối >= d:
            chọn ứng viên
            vị_trí_cuối = ứng viên
            số_lượng += 1

    trả về số_lượng >= số_lượng_cần

Phần phải chứng minh là greedy “chọn sớm nhất có thể” không làm giảm khả năng chọn thêm về sau.

Binary Search kết hợp subsequence hoặc string oracle

Một bài chuỗi có thể hỏi số phần tử tối đa được xóa nhưng chuỗi còn lại vẫn giữ một tính chất, chẳng hạn một mẫu vẫn là subsequence.

Ta Binary Search số lượng xóa $k$.

Predicate:

$$P(k)=\text{“sau khi xóa }k\text{ vị trí, điều kiện vẫn đúng”}.$$

Thông thường:

$$P(0),P(1),\ldots$$

đúng đến một ngưỡng rồi sai.

Kiểm tra một chuỗi là subsequence có thể làm bằng two pointers trong $O(n)$.

can(k):
    đánh dấu k vị trí đầu tiên trong thứ tự xóa

    con_trỏ = 0

    duyệt chuỗi gốc:
        bỏ qua vị trí đã bị xóa

        nếu ký tự hiện tại khớp ký tự cần ở con_trỏ:
            tăng con_trỏ

    trả về con_trỏ đã đi hết chuỗi mẫu

Tổng thời gian thường là

$$O(n\log n)$$

nếu miền $k$ có kích thước $O(n)$.

K-th dưới góc nhìn boundary

Bài k-th cũng là một dạng first true:

$$\text{k-th} = \min x:\ count\_le(x)\ge k.$$

Do đó tư duy first true, last true và search-by-value thực ra cùng một nền tảng: tìm boundary của một predicate đơn điệu.

Giai đoạn 6 - BSTA kết hợp greedy, sorting, scheduling và phân hoạch

Từ giai đoạn này, phần Binary Search thường rất ngắn. Phần khó nằm trong can(x).

Một lời giải đúng cần hai chứng minh độc lập:

• predicate theo $x$ là đơn điệu;
• oracle can(x) trả lời đúng bài toán quyết định.

Nếu thiếu một trong hai, toàn bộ Binary Search có thể sai dù template hoàn toàn đúng.

Greedy feasibility

Một mẫu thường gặp:

1. sort dữ liệu theo một tiêu chí;
2. cố định threshold $x$;
3. greedily xây một phương án;
4. kiểm tra có hoàn thành mục tiêu không.

Mã giả:

sort dữ liệu theo thứ tự cần thiết

can(x):
    khởi tạo trạng thái greedy

    duyệt các đối tượng theo thứ tự:
        nếu đối tượng có thể dùng mà vẫn tôn trọng x:
            chọn hoặc gán đối tượng

    trả về đã đạt đủ mục tiêu hay chưa

Ta phải chứng minh vì sao lựa chọn greedy hiện tại không làm mất một nghiệm tốt hơn về sau. Thường dùng một trong các kiểu lập luận:

• exchange argument: thay lựa chọn của một nghiệm bất kỳ bằng lựa chọn greedy mà không làm nghiệm tệ hơn;
• earliest finish / smallest feasible: chọn phương án kết thúc sớm nhất để chừa nhiều không gian nhất;
• dominance: trạng thái greedy luôn không kém bất kỳ trạng thái khả thi khác theo tiêu chí cần duy trì.

Scheduling với threshold

Một bài scheduling có thể được chuyển thành:

Với giới hạn $x$, có thể xếp mọi công việc sao cho deadline hoặc tải không vượt quá $x$ hay không?

Nếu việc tăng $x$ chỉ làm điều kiện dễ hơn, ta có first true.

Nếu việc tăng $x$ làm điều kiện khó hơn, ta có last true.

Điều quan trọng là xác định đúng chiều đơn điệu trước khi viết code.

Phân hoạch dãy

Một mẫu rất điển hình là tối thiểu hóa giá trị lớn nhất của các nhóm.

Với threshold $x$, greedy quét trái sang phải và tạo ít nhóm nhất có thể. Khi đó:

• nếu số nhóm tối thiểu vẫn lớn hơn $k$, $x$ quá nhỏ;
• nếu số nhóm tối thiểu không quá $k$, $x$ khả thi.

Điều này tạo predicate False rồi True.

Mã giả:

can(x):
    nhóm = 1
    tổng = 0

    duyệt a:
        nếu a > x:
            trả về false

        nếu tổng + a <= x:
            tổng += a
        ngược lại:
            nhóm += 1
            tổng = a

    trả về nhóm <= k

Nếu có thể tách một nhóm thành nhiều nhóm nhỏ hơn mà vẫn hợp lệ, điều kiện “không quá $k$ nhóm” thường đủ để suy ra tồn tại cách dùng đúng số nhóm theo yêu cầu. Tuy nhiên điều này phải được kiểm tra theo đề cụ thể, không được mặc định cho mọi bài.

Ước lượng độ phức tạp oracle

Nếu sort trước trong

$$O(n\log n),$$

mỗi can(x) là $O(n)$ và Binary Search cần $O(\log W)$ lần, tổng là

$$O(n\log n+n\log W).$$

Nếu can(x) đã là $O(n\log n)$ thì tổng có thể thành

$$O(n\log n\log W),$$

vì vậy cần kiểm tra giới hạn thật kỹ.

Giai đoạn 7 - Bisection trên số thực: hình học, vật lý và sai số

Với số thực, ta không có khái niệm “phần tử kế tiếp” như miền nguyên. Ta thu hẹp một đoạn $[L,R]$ cho đến khi đủ chính xác.

Nếu cần minimum feasible và can(x) chuyển từ False sang True:

trái = LO
phải = HI

lặp cố định khoảng 80 lần:
    giữa = (trái + phải) / 2

    nếu can(giữa):
        phải = giữa
    ngược lại:
        trái = giữa

trả về phải

Nếu cần maximum feasible, hướng cập nhật đổi lại.

Vì sao nên dùng số vòng lặp cố định

Với double, sau khoảng 60 đến 100 lần chia đôi, sai số đoạn đã rất nhỏ trong hầu hết bài thi.

Sau $t$ vòng:

$$R_t-L_t=\frac{R_0-L_0}{2^t}.$$

Ví dụ với $t=80$, hệ số thu nhỏ là

$$2^{-80},$$

rất nhỏ so với precision của phần lớn bài.

Dùng fixed iterations tránh nhiều lỗi:

• vòng lặp do điều kiện EPS không co như mong muốn;
• phụ thuộc mạnh vào cách chọn EPS;
• khó dự đoán số vòng;
• lỗi khi hai số double quá gần nhau.

Tìm nghiệm của hàm đơn điệu

Nếu $f(x)$ liên tục và đơn điệu, cần tìm nghiệm

$$f(x)=0,$$

ta xác định dấu hoặc điều kiện ở mid để giữ nửa đoạn còn chứa nghiệm.

Mã giả:

lặp cố định:
    giữa = (trái + phải) / 2

    nếu nghiệm nằm trong nửa [trái, giữa]:
        phải = giữa
    ngược lại:
        trái = giữa

Không được chỉ nhìn công thức rồi chia đôi. Phải biết hàm tăng hay giảm và điều kiện nào cho biết nghiệm nằm ở nửa nào.

Bisection kết hợp hình học

Nhiều bài hình học có dạng:

• thử bán kính $r$;
• thử chiều rộng $w$;
• thử diện tích $A$;
• thử góc $\theta$;
• thử độ cao hoặc độ võng.

Sau khi cố định tham số, các đại lượng còn lại có thể tính trực tiếp.

Mẫu:

can(x):
    dùng công thức hình học suy ra cấu hình tương ứng với x
    kiểm tra cấu hình có thỏa yêu cầu hay không

Điều kiện cần là đại lượng kiểm tra phải thay đổi đơn điệu theo $x$ trong miền đang xét.

Bisection kết hợp mô phỏng vật lý

Trong bài vật lý, can(x) có thể là một simulation.

can(x):
    mô phỏng hệ thống với tham số x
    tính trạng thái cuối hoặc đại lượng quan sát được
    trả về trạng thái đã vượt / chưa đạt / đủ điều kiện

Khi simulation dùng nhiều phép toán số thực, nên tránh so sánh bằng ==. Hãy dựa vào bất đẳng thức và số vòng bisection cố định.

Output precision

Nếu đề yêu cầu $p$ chữ số sau dấu phẩy, thường nên tính với precision dư ra rồi in đúng định dạng.

Đừng nhầm:

• sai số của thuật toán;
• số chữ số in;
• quy tắc làm tròn hoặc cắt bỏ của đề.

Ba vấn đề này là khác nhau.

Giai đoạn 8 - BSTA kết hợp graph: connectivity, BFS, Dijkstra, state space

Đây là một mẫu decomposition rất quan trọng:

Fix một threshold $x$, biến bài tối ưu thành một bài graph quyết định.

Binary Search nằm bên ngoài. Bên trong là BFS, Dijkstra, DSU hoặc một graph oracle khác.

Threshold graph

Giả sử mỗi cạnh có thuộc tính $w$. Với một threshold $x$, ta chỉ giữ cạnh thỏa một điều kiện như

$$w\le x$$

hoặc

$$w\ge x.$$

Khi $x$ thay đổi, tập cạnh thường chỉ tăng hoặc chỉ giảm. Đó là nguồn gốc của monotonicity.

Mã giả:

can(x):
    xây hoặc duyệt ngầm graph chỉ với các cạnh hợp lệ theo x

    chạy thuật toán graph cần thiết

    trả về điều kiện đích có đạt hay không

BSTA + BFS

Nếu sau khi cố định $x$, graph trở thành không trọng số, ta có thể dùng BFS.

Ví dụ cấu trúc:

can(x):
    tạo queue
    đánh dấu trạng thái bắt đầu

    trong khi queue chưa rỗng:
        lấy trạng thái hiện tại

        duyệt các chuyển tiếp hợp lệ dưới threshold x:
            nếu chưa thăm:
                đánh dấu
                đưa vào queue

    trả về đích đã được thăm

Nếu BFS là $O(V+E)$, tổng độ phức tạp thường là

$$O((V+E)\log W).$$

BSTA + Dijkstra

Nếu sau khi fix threshold vẫn phải tối ưu tổng trọng số đường đi, ta có thể:

1. loại các cạnh vi phạm threshold;
2. chạy Dijkstra trên phần graph còn lại;
3. kiểm tra khoảng cách có thỏa giới hạn hay không.

Mã giả:

can(x):
    chạy Dijkstra

    khi xét cạnh:
        bỏ qua cạnh không hợp lệ theo threshold x

    trả về dist[đích] <= giới_hạn

Nếu Dijkstra là

$$O((V+E)\log V),$$

toàn bộ lời giải có thể là

$$O((V+E)\log V\log W).$$

Đây là lý do phải ước lượng oracle trước khi chọn Binary Search.

BSTA + DSU

Nếu điều kiện chỉ là hai đỉnh có liên thông dưới một threshold hay không, DSU có thể phù hợp.

Mỗi lần can(x):

can(x):
    khởi tạo DSU

    duyệt các cạnh hợp lệ theo x:
        union hai đầu cạnh

    trả về hai đỉnh cần kiểm tra thuộc cùng tập

Cách này đơn giản nhưng nếu phải rebuild DSU rất nhiều lần thì tổng chi phí có thể lớn. Với nhiều truy vấn offline, giai đoạn 10 sẽ có kỹ thuật hiệu quả hơn.

Multi-source preprocessing rồi BSTA

Một mẫu mạnh là:

1. dùng BFS hoặc Dijkstra nhiều nguồn để tính một đại lượng an toàn cho mọi đỉnh;
2. Binary Search một threshold $x$;
3. trong can(x), chỉ đi qua các đỉnh đủ an toàn.

Ví dụ, nếu $safe[v]$ là khoảng cách từ $v$ đến nguy hiểm gần nhất, với threshold $x$ chỉ cho phép đỉnh thỏa

$$safe[v]\ge x.$$

Khi $x$ tăng, tập đỉnh hợp lệ chỉ giảm, tạo predicate đơn điệu.

Giai đoạn 9 - BSTA kết hợp matching, max flow, DP và oracle phức hợp

Ở đây Binary Search chỉ là lớp ngoài. Oracle có thể rất nặng.

Công thức quan trọng nhất là:

$$\text{Tổng thời gian} = O(\log W\cdot T_{\text{oracle}}).$$

Nếu oracle đã gần giới hạn thời gian, thêm một hệ số $\log W$ có thể làm lời giải không còn khả thi.

Threshold + bipartite matching

Một mẫu điển hình:

1. thử threshold $x$;
2. dựng cạnh giữa hai phía nếu cặp đó thỏa threshold;
3. kiểm tra có matching đủ lớn hay không.

Mã giả:

can(x):
    tạo graph hai phía rỗng

    với mỗi cặp ứng viên (u, v):
        nếu cặp này hợp lệ dưới threshold x:
            thêm cạnh u - v

    chạy thuật toán matching

    trả về kích thước matching >= yêu_cầu

Monotonicity thường đến từ việc khi nới threshold, số cạnh chỉ tăng. Nếu có matching khi ít cạnh, thêm cạnh không thể làm mất matching cũ.

Threshold + max flow

Tương tự, threshold $x$ quyết định những cạnh nào xuất hiện hoặc capacity nào được phép.

can(x):
    xây network ứng với x
    chạy max flow
    trả về max_flow >= nhu_cầu

Cần đặc biệt cẩn thận với việc dựng lại network ở mỗi lần kiểm tra. Nếu graph lớn, chi phí khởi tạo cũng đáng kể.

BSTA + DP

Có những bài mà sau khi fix $x$, ta cần một DP quyết định.

Ví dụ:

can(x):
    khởi tạo trạng thái DP

    duyệt các trạng thái:
        chỉ cho phép chuyển nếu điều kiện với x thỏa

    trả về trạng thái mục tiêu có đạt được không

Đơn điệu phải được chứng minh ở mức tập chuyển trạng thái hoặc tính khả thi, không phải chỉ vì đáp án nhìn có vẻ tăng hoặc giảm.

Nếu threshold lớn hơn làm tập chuyển tiếp rộng hơn, khả năng đạt đích không thể giảm. Khi đó ta có dạng False rồi True.

Oracle nhiều tầng

Một can(x) có thể gồm:

• tiền xử lý cục bộ;
• sort;
• graph;
• matching;
• DP.

Không nên nghĩ rằng “Binary Search chỉ có khoảng 60 vòng nên chắc chắn nhanh”. Nếu mỗi vòng là một thuật toán nặng, tổng chi phí có thể rất lớn.

Hãy rút gọn oracle trước:

• tiền xử lý phần không phụ thuộc $x$ ra ngoài;
• tái sử dụng dữ liệu bất biến;
• dừng sớm khi đã đủ kết luận;
• tránh rebuild cấu trúc không cần thiết.

Giai đoạn 10 - Parallel Binary Search, offline search và tổng hợp nâng cao

Khi có rất nhiều truy vấn độc lập, mỗi truy vấn đều cần tìm một boundary trên cùng một chuỗi sự kiện, chạy Binary Search riêng cho từng truy vấn có thể lặp lại quá nhiều công việc.

Parallel Binary Search (PBS) xử lý nhiều Binary Search đồng thời.

Ý tưởng Parallel Binary Search

Giả sử có $Q$ truy vấn. Mỗi truy vấn $q$ có khoảng ứng viên

$$[L_q,R_q].$$

Ở mỗi vòng:

1. tính mid cho mọi truy vấn chưa chốt;
2. gom các truy vấn theo mid;
3. replay các sự kiện theo thứ tự một lần;
4. khi đến một mid, trả lời tất cả truy vấn đang chờ ở đó;
5. cập nhật nửa trái hoặc nửa phải cho từng truy vấn.

Mã giả khái quát:

với mỗi truy vấn q:
    L[q] = cận trái
    R[q] = cận phải

trong khi còn truy vấn chưa xác định:
    xóa các bucket

    với mỗi truy vấn q chưa chốt:
        mid[q] = (L[q] + R[q]) / 2
        đưa q vào bucket[mid[q]]

    khởi tạo lại cấu trúc dữ liệu
    event = đầu tiên

    duyệt mốc t theo thứ tự:
        áp dụng các event đến t vào cấu trúc dữ liệu

        với mỗi truy vấn q trong bucket[t]:
            nếu predicate(q, cấu_trúc_hiện_tại) đúng:
                R[q] = t
            ngược lại:
                L[q] = t + 1

Nếu mỗi vòng replay toàn bộ $M$ sự kiện và có khoảng $O(\log M)$ vòng, tổng chi phí thường gần

$$O((M+Q)\log M)$$

nhân với chi phí cập nhật hoặc truy vấn của cấu trúc dữ liệu đang dùng.

PBS kết hợp DSU

Nếu cạnh xuất hiện theo thời gian và nhiều truy vấn hỏi “thời điểm đầu tiên $u$ và $v$ liên thông”, ta có thể replay cạnh theo thời gian bằng DSU.

Predicate của truy vấn:

$$P_q(t)=\text{“sau khi thêm các cạnh đến thời điểm }t,\ u_q\text{ và }v_q\text{ connected”}.$$

Một khi hai đỉnh đã connected, thêm cạnh về sau không thể làm chúng mất liên thông. Vì vậy predicate là False rồi True.

PBS kết hợp Fenwick hoặc range update

Nếu sự kiện là cộng thêm giá trị lên nhiều vị trí và mỗi truy vấn hỏi thời điểm đầu tiên tích lũy đạt ngưỡng, ta replay sự kiện bằng Fenwick Tree hoặc cấu trúc range-update phù hợp.

Điểm quan trọng là các truy vấn chia sẻ cùng một timeline. PBS tận dụng việc đó để tránh chạy lại toàn bộ timeline riêng cho từng truy vấn.

Search trên version hoặc persistent structure

Một cấu trúc persistent có thể lưu nhiều phiên bản theo threshold hoặc theo prefix sự kiện.

Khi đó mỗi can(x) không nhất thiết phải rebuild cấu trúc từ đầu; ta truy vấn đúng version tương ứng.

Tuy nhiên, nếu cấu trúc persistent có phép lấy trực tiếp phần tử k-th hoặc order statistic, hãy dùng thao tác chuyên biệt thay vì ép thêm một lớp Binary Search không cần thiết.

Ranh giới với các kỹ thuật gần giống

Binary Search Tree là một cấu trúc dữ liệu, không đồng nghĩa với Binary Search.

Binary Lifting dùng nhảy theo lũy thừa hai trên tổ tiên hoặc successor; nó có tinh thần chia đôi nhưng là một kỹ thuật khác.

Ternary Search phù hợp với hàm unimodal; Binary Search the Answer phù hợp với predicate đơn điệu. Hai điều kiện nền tảng khác nhau.

Two Pointers hoặc Sliding Window có thể giải một số bài mà Binary Search cũng giải được, nhưng nếu có lời giải $O(n)$ rõ ràng thì không nên cố dùng phương án $O(n\log n)$ chỉ vì quen Binary Search.

Một công thức trực tiếp $O(1)$ hoặc một cấu trúc order-statistics chuyên biệt cũng nên được ưu tiên nếu nó giải đúng bài toán gọn và nhanh hơn.

Ghi chú về invariant và tính đúng

Binary Search không nên được học như một đoạn code cố định. Điều cần giữ là invariant.

Với first true trên miền nguyên $[L,R]$, một cách nhìn an toàn là:

• đáp án luôn nằm trong đoạn hiện tại;
• nếu can(mid) đúng, boundary không thể nằm bên phải mid, nên giữ nửa trái kể cả mid;
• nếu can(mid) sai, boundary phải nằm bên phải mid, nên bỏ luôn mid.

Với last true:

• nếu can(mid) đúng, boundary không thể nằm bên trái mid, nên giữ nửa phải kể cả mid;
• nếu can(mid) sai, boundary phải nằm bên trái mid, nên bỏ mid.

Sự khác nhau của hai template nằm ở hướng boundary và cách chọn mid.

Ghi chú về cận và miền tìm kiếm

Cận tốt giúp Binary Search vừa đúng vừa dễ chứng minh.

Với bài minimum feasible, LO thường là một lower bound hiển nhiên, còn HI là một giá trị chắc chắn đủ lớn để khả thi.

Với bài maximum feasible, LO thường là một giá trị chắc chắn khả thi, còn HI là giới hạn tối đa có thể.

Không nên chọn cận theo cảm giác nếu không chứng minh được nó bao phủ đáp án.

Nếu miền gần $10^{18}$, tính mid bằng

$$mid=L+\left\lfloor\frac{R-L}{2}\right\rfloor$$

thay vì trực tiếp dùng

$$\frac{L+R}{2}$$

để tránh overflow trong các ngôn ngữ dùng số nguyên hữu hạn.

Ghi chú về monotonicity

Đây là điều kiện sống còn của Binary Search the Answer.

Đừng chỉ nhìn vài test rồi cho rằng can(x) đơn điệu. Cần lập luận theo logic bài toán.

Với first true, thường chứng minh:

$$P(x)=true\Rightarrow P(y)=true\quad\forall y>x.$$

Với last true, thường chứng minh:

$$P(x)=true\Rightarrow P(y)=true\quad\forall y<x.$$

Nếu một predicate có thể đổi trạng thái nhiều lần, Binary Search boundary không áp dụng được.

Ghi chú về tổng độ phức tạp

Binary Search trên mảng:

$$O(\log n).$$

Nhiều truy vấn độc lập trên dãy đã sort:

$$O(q\log n).$$

Binary Search the Answer với oracle $O(n)$:

$$O(n\log W).$$

BSTA với Dijkstra:

$$O((V+E)\log V\log W).$$

BSTA với một oracle tổng quát có chi phí $T$:

$$O(T\log W).$$

Bisection số thực với số vòng cố định $K$:

$$O(KT),$$

trong đó $K$ thường là một hằng số khoảng 60 đến 100.

Tư duy quan trọng nhất là không chỉ hỏi “Binary Search mất bao lâu”, mà phải hỏi “mỗi lần check mất bao lâu, và check được gọi bao nhiêu lần”.