Kỹ thuật · Tư duyPhân táchnhị phân

B I N A R Y S P L I T T I N G
← trang chủ
✦
9 ví dụ · 5 có lời giải
prefix sum · Fenwick
bitmask · chẵn lẻ
Lưu ý

Trước khi bắt đầu

Đây không phải là một khái niệm chính thức trong sách giáo khoa, mà là một định hướng tư duy giúp tiếp cận bài toán hiệu quả hơn.

Ý tưởng

Phân tách nhị phân

Ý tưởng cốt lõi là tìm cách đơn giản hoá bài toán bằng cách phân tách không gian kết quả thành hai tập đối lập, thay vì xử lý trực tiếp với nhiều biến số phức tạp. Cách tiếp cận này giúp đưa bài toán về dạng quen thuộc và dễ giải hơn.

Khi đó, bài toán trở nên tương tự như đang xử lý trên tập nhị phân (0–1).

Hãy cùng tìm hiểu ý tưởng “phân tách nhị phân” (binary splitting) thông qua hai ví dụ sau.
Trường hợp dễ thấy nhất

Tìm kiếm nhị phân cũng là phân tách nhị phân

Cần tìm một giá trị trên dãy tăng dần. Với mỗi x đem so sánh tương đối, gọi những số ≥ x là 1 và những số nhỏ hơn là 0, thì mỗi x sinh ra đúng một dãy có dạng:

0 0 0 0 1 1 1 1

Chỉ còn hai tập hợp, và thấy ngay là cắt được cả khúc 0 ở đầu. Đây là lý do nên xem phân tách nhị phân như một phản xạ: cái kỹ thuật quen nhất trong ngành vốn đã là một trường hợp riêng của nó.

Ví dụ 1

Count Subarrays With Median K

Đề bài

Bài toán

Cho một dãy gồm n phần tử và một số nguyên X. Hãy đếm số đoạn con liên tiếp mà số trung vị của đoạn đó bằng X.

Ghi nhớ rằng:

  • Với độ dài lẻ l, trung vị là phần tử lớn thứ (l / 2) + 1.
  • Với độ dài chẵn l, trung vị là phần tử lớn thứ (l / 2).
Ràng buộc: 1 ≤ n ≤ 10^5
Link đề →
Lời giải

Ý tưởng chính

Ta sẽ định nghĩa hàm F(x) là số đoạn con có trung vị ≥ x. Khi đó, kết quả bài toán chính là:

F(X) − F(X + 1)

Lý do:

  • F(X) đếm số đoạn có trung vị lớn hơn hoặc bằng X.
  • F(X + 1) đếm số đoạn có trung vị lớn hơn hoặc bằng X + 1. ⇒ Phần chênh lệch chính là số đoạn có trung vị bằng X.

Cách tính F(x)

Với mỗi đoạn con, ta chia các phần tử thành 2 loại:

  • Nhóm nhỏ hơn x: gán giá trị −1.
  • Nhóm lớn hơn hoặc bằng x: gán giá trị +1.

Khi đó, bài toán trở thành: đếm số đoạn con liên tiếp sao cho tổng các giá trị sau khi quy đổi > 0. Đây chính là bài toán đếm số đoạn có tổng prefix sum > 0, một bài toán kinh điển.

Chi tiết

Gọi prefix[i] là tổng từ đầu đến vị trí i sau khi chuyển đổi −1/+1. Với mỗi i, ta muốn đếm số lượng j < i sao cho prefix[j] < prefix[i].

Việc đếm này có thể thực hiện hiệu quả bằng Fenwick Tree (Binary Indexed Tree) hoặc Segment Tree, với hai thao tác:

  • add(x) — thêm một giá trị prefix.
  • get(x) — đếm số lượng giá trị nhỏ hơn x.
Mặc dù có nhiều hướng tiếp cận, nhưng việc chuyển bài toán sang bài toán prefix sum nhị phân (−1, +1) giúp ta sử dụng các kỹ thuật quen thuộc để giải quyết hiệu quả.
Minh hoạ

Một ví dụ nhỏ

a = [1, 3, 2] · X = 2
Cài đặt

Code

class Solution {
    inline int lsb(int x) { return x & -x; }

    void add(int x, vector<int>& t) {
        for (x++; x < t.size(); x += lsb(x)) t[x]++;
    }

    int get(int x, vector<int>& t) {
        int s = 0;
        for (x++; x > 0; x -= lsb(x)) s += t[x];
        return s;
    }

    long long count(vector<int>& nums, int k) {
        int n = nums.size(), b = n, c = 0;
        vector<int> t(2 * n + 2); // Size to handle [-n, n] range
        add(b, t); // Initialize at offset (zero-based)
        long long r = 0;
        for (int x : nums) {
            c += x < k ? -1 : 1;
            r += get(c - 1 + b, t);
            add(c + b, t);
        }
        return r;
    }

public:
    int countSubarrays(vector<int>& nums, int k) {
        return count(nums, k) - count(nums, k + 1);
    }
};
C++ · Fenwick Tree trên prefix sum −1/+1
Ví dụ 2

Serval and Rooted Tree

Đề bài

Bài toán

Cho một cây có n đỉnh với gốc là đỉnh số 1. Mỗi đỉnh không phải lá sẽ được gán một phép toán: max hoặc min (biểu diễn lần lượt bằng 1 và 0).

Giả sử cây có k lá, hãy gán các số nguyên từ 1 đến k (mỗi số đúng một lần) vào các lá, sao cho giá trị tại gốc đạt lớn nhất có thể, theo quy tắc: mỗi đỉnh không phải lá sẽ lấy giá trị là max hoặc min của các con tuỳ theo phép toán đã gán.

Ràng buộc: 2 ≤ n ≤ 3 × 10⁵; phép toán tại mỗi đỉnh: 0 = min, 1 = max.
Link đề → · Bài nộp →
Lời giải

Ý tưởng lời giải

Giả sử đáp án cần tìm là một số X. Ta thử kiểm tra liệu có thể đặt các số ≥ X là 1, các số còn lại là 0. Khi đó:

  • Với mỗi node có phép toán max, chỉ cần ít nhất một nhánh con sinh ra giá trị 1 là đủ.
  • Với node có phép toán min, thì tất cả các nhánh con đều phải sinh ra giá trị 1.

Từ đây, bài toán trở thành: đếm số lượng tối thiểu các lá phải gán giá trị 1 (tức là ≥ X) để toàn bộ cây có thể tính ra giá trị 1 tại gốc.

Nếu số lượng lá phải gán 1 ≤ k − X + 1 (tức còn đủ số lớn hơn hoặc bằng X để gán vào lá), thì X là đáp án hợp lệ.

Kết luận

Ta có thể áp dụng nhị phân đáp án trên X từ 1 đến k và kiểm tra với mỗi X bằng cách:

  1. Biến cây thành cây nhị phân 0/1.
  2. Đếm số lượng 1 tối thiểu cần có ở lá để đảm bảo giá trị tại gốc là 1.
Mục tiêu cuối cùng là tìm giá trị lớn nhất của X sao cho điều kiện trên thoả mãn.
Minh hoạ

Một ví dụ nhỏ

cố định X · lá thành 0 hoặc 1
Ví dụ 3

Minimax Problem

Đề bài

Bài toán

Cho n mảng a₁, a₂, …, aₙ, mỗi mảng đúng m phần tử; phần tử thứ y của mảng thứ x là a[x][y].

Với một cặp mảng (i, j) ta tạo được mảng b gồm m phần tử:

b[k] = max( a[i][k], a[j][k] )

Hãy chọn cặp (i, j) sao cho min(b[k]) lớn nhất có thể.

Ràng buộc: 1 ≤ n ≤ 3 × 10⁵, 1 ≤ m ≤ 8, 1 ≤ a[x][y] ≤ 10⁹. Chú ý m rất nhỏ — đó là cái mấu.
Link đề → · Bài nộp →
Lời giải

Cố định đáp án rồi nhìn thành bảng 0–1

Giả sử cố định giá trị cần tìm là X. So sánh tương đối với X thì cả bảng chỉ còn 0 và 1. Lúc đó giá trị min lớn nhất rõ ràng là 1, và nó xảy ra khi:

b[k] = [1, 1, …, 1]

Tức là hai mảng cần tìm, ở mỗi vị trí, ghép lại bằng phép OR: vị trí nào đang là 1 thì mảng đối nghịch để 0 hay 1 đều được; nhưng vị trí nào là 0 thì mảng đối nghịch buộc phải là 1.

Vì sao m ≤ 8 là mấu chốt

Mỗi mảng sau khi quy về 0–1 chỉ còn là một bitmask m bit. Ta cố định a[i], rồi tìm xem có a[j] nào ghép lại ra toàn 1 hay không — với mỗi a[i] chỉ cần duyệt 2⁸ = 256 trường hợp là xong.

Bọc ngoài cùng là nhị phân đáp án trên X, cho ra O(log · 2^m · n). Gọn hơn thì tách làm hai phần rời nhau:

O(2^m · 2^m) + O(n · m)
Đây là phân tách nhị phân ở dạng thuần nhất: bảng số lớn tuỳ ý bị nén thành bảng 0–1, và phép max trên số biến thành phép OR trên bit.
Minh hoạ

Một ví dụ nhỏ

m = 4 · so với X thì bảng chỉ còn 0–1
Ví dụ 4

1-Trees and Queries

Đề bài

Bài toán

Cho cây n đỉnh và q truy vấn, mỗi truy vấn là bộ năm số x, y, a, b, k.

Sau khi nối thêm cạnh giữa hai đỉnh x và y, hãy trả lời: có đi được từ a đến b bằng đường đi dài đúng k hay không? Được phép đi qua một cạnh hoặc một đỉnh nhiều lần.

Ràng buộc: 3 ≤ n ≤ 10⁵, 1 ≤ q ≤ 10⁵, x ≠ y, 1 ≤ k ≤ 10⁹.
Link đề → · Bài nộp →
Lời giải

Chỉ còn là chuyện chẵn lẻ

Xét gốc là 1, dựng LCA, gọi d[u] là khoảng cách từ u tới gốc.

Vì được đi lại một cạnh nhiều lần, nếu có đường đi từ A đến B dài C thì luôn đi được độ dài C + 2Z với Z ≥ 0. Đây chính là chỗ bài toán gãy làm hai tập: độ dài chẵn và độ dài lẻ. Vậy đi được độ dài K khi và chỉ khi:

K ≡ C (mod 2) và C ≤ K

Có ba đường đi phải xét:

  1. Đường từ A đến B.
  2. Đường từ A đến x, cộng y đến B, cộng 1.
  3. Đường từ A đến y, cộng x đến B, cộng 1.

Độ dài giữa hai điểm thì lấy bằng công thức quen:

dist(A, B) = d[A] + d[B] − 2 · d[LCA(A, B)]
Chỉ cần một trong ba đường thoả cả hai điều kiện là in YES.
Minh hoạ

Một ví dụ nhỏ

C = 2 ⇒ đi được 2, 4, 6, … nhưng không đi được 3
Ví dụ 5

Range Flip Find Route

Đề bài

Bài toán

Cho bảng H × W, mỗi ô ở trạng thái block (#) hoặc unblock (.).

Được phép chọn bộ (r₁, c₁) và (r₂, c₂) rồi đảo trạng thái mọi ô (x, y) thoả r₁ ≤ x ≤ r₂ và c₁ ≤ y ≤ c₂.

Tìm số bộ phải chọn ít nhất để đi được từ ô (1, 1) đến ô (H, W), biết chỉ được đi sang phải hoặc xuống dưới.

Ràng buộc: 2 ≤ H, W ≤ 100.
Link đề → · Bài nộp →
Lời giải

Đếm số lần đổi loại trên đường đi

Bảng chỉ có hai loại ô — block và unblock — nên quy bài toán về đếm:

D = số lần đổi loại nhỏ nhất trên đường đi (1, 1) → (H, W)

Rồi chia đúng hai trường hợp theo tính chẵn lẻ của D:

  • D chẵn ⇒ ô (1, 1) và ô (H, W) cùng loại. Kết quả là D / 2, và nếu ô (1, 1) là # thì cộng thêm 1.
  • D lẻ ⇒ không cần quan tâm ô (1, 1) là # hay không, chỉ cần (D + 1) / 2 lần đổi.
Hai loại ô đã là tập 0–1 sẵn; việc còn lại chỉ là đi tìm đường có ít lần chuyển tập nhất.
Minh hoạ

Một ví dụ nhỏ

bảng 2 × 2 · đường đi (1,1) → (1,2) → (2,2)
Ví dụ 6

Dr. Evil Underscores

Đề bài

Bài toán

Cho n số nguyên a₁, a₂, …, aₙ. Hãy chọn số nguyên X sao cho max(a[i] ⊕ X) nhỏ nhất có thể, và in ra giá trị nhỏ nhất đó.

Ràng buộc: 1 ≤ n ≤ 10⁵, 0 ≤ a[i] ≤ 2³⁰ − 1.
Link đề → · Bài nộp →
Lời giải

TBU

Trong sổ, mục lời giải của bài này bỏ trống — chỉ có đề và một bài nộp. Tôi giữ nguyên chỗ trống thay vì viết bù bây giờ.

Gợi ý duy nhất còn lại là cái mốc 2³⁰: bài này xét theo từng bit, mà xét bit thì lại đúng là chia thành hai tập 0 và 1.
Minh hoạ

Một ví dụ nhỏ

a = [1, 2, 3] · tách theo bit cao nhất
Ví dụ 7

Dat Bae

Đề bài

Bài toán

Có N máy tính, ID từ 0 đến N − 1, mỗi máy lưu một bit thông tin.

Mỗi thao tác TEST_STORE gửi lên một chuỗi N bit; mỗi máy đọc phần của mình rồi gửi lại, theo đúng thứ tự bit đã gửi. Có B máy bị hỏng, nên chuỗi trả về chỉ còn độ dài N − B.

Hãy tìm ID của B máy hỏng, với số thao tác hỏi tối đa là F.

Ràng buộc: 1 ≤ T ≤ 100, 2 ≤ N ≤ 1024, 1 ≤ B ≤ min(15, N − 1). Test set 1 cho F = 10; test set 2 chỉ cho F = 5.
Google Code Jam 2019 · Qualification Round
Lời giải

TBU

Trong sổ, mục lời giải của bài này bỏ trống — chỉ có đề và một bài nộp. Tôi giữ nguyên chỗ trống thay vì viết bù bây giờ.

N ≤ 1024 = 2¹⁰ và F = 10 ở test set đầu — con số khớp nhau một cách khó bỏ qua: mỗi lần hỏi là một bit của ID.
Minh hoạ

Một ví dụ nhỏ

N = 8 · mỗi lần hỏi lấy một bit của ID
Ví dụ 8

Mind Control

Đề bài

Bài toán

Cho dãy n số a₁, a₂, …, aₙ. Mỗi người chơi lần lượt lấy số đầu tiên hoặc số cuối cùng của dãy còn lại. Bạn là người đi ở lượt thứ m.

Bạn được phép thay đổi cách chọn của tối đa k người. Hỏi giá trị lớn nhất bạn chắc chắn lấy được, bất kể những người còn lại chọn thế nào.

Ràng buộc: 1 ≤ t ≤ 1000, 1 ≤ m ≤ n ≤ 3500, 0 ≤ k ≤ n − 1, 0 ≤ a[i] ≤ 10⁹, tổng n ≤ 3500.
Link đề → · Bài nộp →
Lời giải

TBU

Trong sổ, mục lời giải của bài này bỏ trống — chỉ có đề và một bài nộp. Tôi giữ nguyên chỗ trống thay vì viết bù bây giờ.

Minh hoạ

Một ví dụ nhỏ

a = [2, 9, 2, 3, 8, 5] · bạn đi lượt m = 4
Ví dụ 9

Wrong Answer on test 233

Đề bài

Bài toán

Cho n câu hỏi one-choice, mỗi câu có k lựa chọn và đúng một đáp án đúng; đáp án câu thứ i là h[i]. Trả lời đúng được 1 điểm, sai được 0.

n câu được đặt trên vòng tròn, và vì lỗi chương trình nên mỗi câu bị dịch đi một vị trí: câu i thành câu i mod n + 1.

Có kⁿ tập trả lời. Hãy đếm số tập trả lời mà điểm sau khi dịch cao hơn điểm với bộ đáp án ban đầu.

Ràng buộc: 1 ≤ n ≤ 2 × 10⁵, 1 ≤ k ≤ 10⁹, 1 ≤ h[i] ≤ k. Kết quả lớn nên nhớ lấy mod.
Link đề → · Bài nộp →
Lời giải

TBU

Trong sổ, mục lời giải của bài này bỏ trống — chỉ có đề và một bài nộp. Tôi giữ nguyên chỗ trống thay vì viết bù bây giờ.

Chỗ nối với chủ đề có lẽ là ở chữ “cao hơn”: mỗi câu chỉ đóng góp +1, 0 hay −1 vào phần chênh lệch, nên bài toán thu về việc đếm dấu của một tổng.
Minh hoạ

Một ví dụ nhỏ

mỗi câu chỉ đổi điểm đi −1, 0 hoặc +1
Tổng kết

Vì sao cách này hiệu quả

Qua năm ví dụ trên, có thể thấy rằng trong một số trường hợp, ta có thể áp dụng một chiến lược tiếp cận bài toán bằng cách phân chia kết quả thành hai tập đối lập, từ đó đơn giản hoá không gian bài toán.

Việc chia thành hai tập này giúp ta quy đổi bài toán ban đầu thành một bài toán con có cấu trúc quen thuộc hơn — thường là các bài toán đã có lời giải phổ biến hoặc mang tính chất “well-known”, cho phép ta áp dụng những phương pháp giải quyết hàn lâm và hiệu quả hơn.

Một lưu ý về cách xếp

Không phải bài nào cũng là nhị phân đáp án

1-Trees and Queries và Range Flip Find Route được xếp vào chủ đề này trong sổ, dù lời giải của chúng dựa vào tính chẵn lẻ và hai loại ô hơn là vào nhị phân đáp án. Tôi giữ đúng cách xếp đó — cái chung của cả chín bài là bước quy về hai tập đối lập, còn tập ấy là “≥ X / < X”, “chẵn / lẻ” hay “block / unblock” thì tuỳ bài.