03.2. Chia để trị

Giới thiệu

Chia để trị là một là một tư tưởng đúng hơn là một giải thuật cụ thể. Tư tưởng chính của nó là chia nhỏ một bài toán lớn, phức tạp thành những bài toán nhỏ hơn đơn giản hơn để giải quyết (trị) từng phần đó, sau đó kết hợp kết quá của các bài toán con này lại để cho ra kết quả bài toán lớn ban đầu.

TÀI LIỆU THAM KHẢO

1. VNOI - tìm kiếm nhị phân

2. GeeksforGeeks - Binary search algorithm

3. Tài liệu chuyên đề Duyên Hải Bắc Bộ 2021

4. Competitive Programming 4, Steven Halim, chapter 3

Các bước thực hiện chia để trị:

• Bước 1. Chia nhỏ (chặt nhỏ) bài toán

• Bước 2. Tìm neo (cơ sở đệ quy), tức là bài toán con nhỏ nhất mà tại đó ta có thể giải một cách dễ dàng.

• Bước 3. Tìm công thức hồi quy, là cách thức ta kết hợp kết quả của các bài toán con thành kết quả của bài toán lớn hơn.

Mô hình chia để trị:

DAC(a, i, j)

{

    if(small(a, i, j))

      return(Solution(a, i, j))

    else 

      mid = divide(a, i, j)               // f1(n)

      b = DAC(a, i, mid)                 // T(n/2)

      c = DAC(a, mid+1, j)            // T(n/2)

      d = combine(b, c)                 // f2(n)

   return(d)

}

Thời gian thực hiện giải thuật trên:

   O(1) if n is small

 T(n) =     f1(n) + 2T(n/2) + f2(n)

Nguồn: GeeksforGeeks

Ví dụ 1:

Xét bài toán tìm max của dãy arr có n phần tử số nguyên.

Cách 1 - Chặt tuần tự

Bước 1: Chặt nhỏ bài toán

Ta thấy rằng max của một dãy có n số nguyên chính là max của một dãy có n-1 số và số thứ n. Điều này đưa ta đến một cách chặt nhỏ dãy trên từng phần tử từ cuối về đầu. Cách này người ta gọi là chặt tuần tự.

Bước 2: Giải từng bài toán con (trị)

Bài toán con ở đây chính là max của n-1 phần tử, với n giảm dần cho đến khi về 1 (trường hợp neo, hay cơ sở đệ quy). Trường hợp neo là khi mảng chỉ còn 1 phần tử thì max là chính nó, ta trả về ngay phần tử đó.

Bước 3: Công thức hồi quy

Lưu ý rằng công thức hồi quy có thể là một  công thức tính toán, một cách thức lựa chọn hay một cách kết hợp nào đó để từ kết quả các bài toán con ta đưa được về kết quả của bài toán lớn hơn.

Trong trường hợp bài toán này, cách kết hợp đó là khi đã tìm ra max của n-1 phần tử đầu, ta đem max đó so sánh với phần tử thứ n. Nếu arr[n] > max thì ta thay lại max là arr[n], trả về giá trị của max.

Các bước trên được thể hiện bằng đoạn code dưới đây:

#include <iostream>

using namespace std;

int n, arr[1000];

int findmax(int arr[], int l, int r){

    if(l==r) return arr[r];

    else{

        int res = findmax(arr,l,r-1);

        if (res < arr[r]) res = arr[r];

        return res;

    }

}

int main(){

    cin>>n;

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

        cin>> arr[i];

    }

    cout<<findmax(arr,0,n-1);

    return 0;

}

Thời gian thực hiện giải thuật trên vẫn là O(n) do cách ta chặt tuần tự, nên số lần chặt là n-1 lần, mỗi lần chặt chúng ta thực hiện một phép so sánh.

Cách thứ 2 - Chặt nhị phân

Bước 1 - Chặt nhỏ bài toán

Bây giờ chúng ta quan sát lại, sẽ thấy rằng max của dãy a có n phần tử cũng là max của nữa đầu so với max của nữa sau. Như vậy chúng ta sẽ chặt mảng làm đôi, tìm max1 của nữa đầu, max2 của nữa sau rồi so sánh max1 và max2 để tìm ra max.

Bước 2 - Giải từng bài toán con (trị)

Việc chặt nhỏ dãy ra thành hai nữa cuối cùng sẽ dẫn đến bài toán cơ sở là chỉ còn một phần tử. Lúc này max là chính nó.

Bước 3 - Kết hợp - Công thức hồi quy.

Vì mỗi lần chặt ta phân mảng làm hai nữa nên khi kết hợp, ta phải lấy max hai bên rồi so sánh hai max này để lấy ra max lớn nhất.

Giải thuật trên được thể hiện qua đoạn code dưới đây:

#include <iostream>

using namespace std;

int n;

int a[1000];

int findmax(int a[], int l, int r){

    if(l==r) return a[r];

    else{

        int mid = (l+r)/2;

        int max1 = findmax(a,l,mid);

        int max2 = findmax(a,mid+1,r);

        if (max1 > max2) return max1;

        else return max2;

    }

}

int main(){

    cin>>n;

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

        cin>> a[i];

    }

    cout<<findmax(a,0,n-1);

    return 0;

}

Độ phức tạp giải thuật vẫn là O(n). Do cách chặt nhị phân và xử lý cả hai bên, nên số lần chặt là: 1 + 2 +4 + ...+ n/2. Tổng cấp số nhân này sẽ ra n-1, mỗi thao tác hồi quy ta thực hiện một phép so sánh.

Ví dụ 2: Closest Pair of Point (Cặp điểm gần nhất)

Nguồn: GeekforGeeks

Tóm tắt: Cho một cặp N điểm trên mặt phẳng, tìm cặp điểm có khoảng cách gần nhất.

Input: 

• Dòng đầu chứa số nguyên N

• N dòng tiếp theo, mỗi dòng chứa một cặp số nguyên là tọa độ x, y của điểm thứ i

Output:

Một số thực duy nhất là khoản cách ngắn nhất giữa các cặp điểm

Ví dụ:

input:

6

2 3

12 30

40 50

5 1

12 10

3 4

output:

1.41421

Cách giải "vét trâu" bằng cách vét tất cả các cặp điểm rồi tìm ra cặp có khoảng cách ngắn nhất có độ phức tạp N^2. Cách tiếp cận chia để trị được tiến hành qua các bước sau đây:

Tiền xử lý:

Sắp xếp mảng p[] theo thứ tự tăng dần theo tọa độ x.

Chia để trị:

Bước 1. Tìm midle = p[n/2]

Bước 2. Chia mảng p[] ra hai nữa, một nữa bắt đầu từ p[0] đến p[n/2], nữa còn lại từ p[n/2 +1] đến p[n-1]

Bước 3. Thực hiện đệ quy để tìm min nữa trái và nữa phải, đạt là dl và dr, lấy min của dl và dr ta được d.

Bước 4. Từ ba bước trên, chúng ta đã tìm ra cận trên d của khoản cách nhỏ nhất, bây giờ chúng ta cần tìm khoản cách giữa các cặp điểm mà một điểm thuộc nữa bên này, một điểm thuộc nữa bên kia. Bằng cách dựng một đường thằng đứng tại hoành độ n/2, tìm tất cả các điểm có khoản cách x từ nó đến đường thằng này nhỏ hơn d. Lưu tất cả các điểm đó và mảng strip[].

Bước 5. Sort mảng strip[] theo tung độ y. Bước này tốn O(nlogn).

Bước 6. Tìm minDistance trong strip[]. Bước này mới nhìn có vẽ tốn O(n^2) nhưng thực chất chỉ cần O(n), vì mỗi điểm ta chỉ cần tìm khoản cách với 5 đến 7 hàng xóm gần nhất của nó.

Bước 7. So sánh d và minDistance để tìm lời giải cuối cùng.

Thuật toán trên thể hiện bằng mã C++ như sau: 

// A divide and conquer program in C++

// to find the smallest distance from a

// given set of points.

#include <bits/stdc++.h>

using namespace std;

// A structure to represent a Point in 2D plane

class Point

{

    public:

    int x, y;

};

/* Following two functions are needed for library function qsort().

Refer: http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ */

// Needed to sort array of points

// according to X coordinate

int compareX(const void* a, const void* b)

{

    Point *p1 = (Point *)a, *p2 = (Point *)b;

    return (p1->x - p2->x);

}

// Needed to sort array of points according to Y coordinate

int compareY(const void* a, const void* b)

{

    Point *p1 = (Point *)a, *p2 = (Point *)b;

    return (p1->y - p2->y);

}

// A utility function to find the

// distance between two points

float dist(Point p1, Point p2)

{

    return sqrt( (p1.x - p2.x)*(p1.x - p2.x) +

                (p1.y - p2.y)*(p1.y - p2.y)

            );

}

// A Brute Force method to return the

// smallest distance between two points

// in P[] of size n

float bruteForce(Point P[], int n)

{

    float min = FLT_MAX;

    for (int i = 0; i < n; ++i)

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

            if (dist(P[i], P[j]) < min)

                min = dist(P[i], P[j]);

    return min;

}

// A utility function to find

// minimum of two float values

float min(float x, float y)

{

    return (x < y)? x : y;

}

// A utility function to find the

// distance between the closest points of

// strip of given size. All points in

// strip[] are sorted according to

// y coordinate. They all have an upper

// bound on minimum distance as d.

// Note that this method seems to be

// a O(n^2) method, but it's a O(n)

// method as the inner loop runs at most 6 times

float stripClosest(Point strip[], int size, float d)

{

    float min = d; // Initialize the minimum distance as d

    qsort(strip, size, sizeof(Point), compareY);

    // Pick all points one by one and try the next points till the difference

    // between y coordinates is smaller than d.

    // This is a proven fact that this loop runs at most 6 times

    for (int i = 0; i < size; ++i)

        for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j)

            if (dist(strip[i],strip[j]) < min)

                min = dist(strip[i], strip[j]);

    return min;

}

// A recursive function to find the

// smallest distance. The array P contains

// all points sorted according to x coordinate

float closestUtil(Point P[], int n)

{

    // If there are 2 or 3 points, then use brute force

    if (n <= 3)

        return bruteForce(P, n);

    // Find the middle point

    int mid = n/2;

    Point midPoint = P[mid];

    // Consider the vertical line passing

    // through the middle point calculate

    // the smallest distance dl on left

    // of middle point and dr on right side

    float dl = closestUtil(P, mid);

    float dr = closestUtil(P + mid, n - mid);

    // Find the smaller of two distances

    float d = min(dl, dr);

    // Build an array strip[] that contains

    // points close (closer than d)

    // to the line passing through the middle point

    Point strip[n];

    int j = 0;

    for (int i = 0; i < n; i++)

        if (abs(P[i].x - midPoint.x) < d)

            strip[j] = P[i], j++;

    // Find the closest points in strip.

    // Return the minimum of d and closest

    // distance is strip[]

    return min(d, stripClosest(strip, j, d) );

}

// The main function that finds the smallest distance

// This method mainly uses closestUtil()

float closest(Point P[], int n)

{

    qsort(P, n, sizeof(Point), compareX);

    // Use recursive function closestUtil()

    // to find the smallest distance

    return closestUtil(P, n);

}

// Driver code

int main()

{

    Point P[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};

    int n = sizeof(P) / sizeof(P[0]);

    cout << "The smallest distance is " << closest(P, n);

    return 0;

}

// Nguồn: This code is contributed by rathbhupendra dẫn từ GeeksforGeeks.com

Độ phức tạp:

Gọi thời gian thực hiện giải tuật là T(n).

• Đệ quy việc chia mảng làm 2: 2T(n/2)

• Tìm mảng strip[]: O(n)

• Thực hiện sort: O(nlogn)

• Tìm minDistance: O(n)

Tổng: T(n) = 2T(n/2) + O(n) + O(nlogn) + O(n) 

                   = 2T(n/2) + O(nlogn)

                   = T(n*logn*logn)

Đề dễ hiểu bước biến đổi này, chúng ta hình dung độ phực tạp của bước sắp xếp mảng strip[], quá trình này lặp lại mỗi level khi ta gộp mảng trong quá trình chia để trị (logn bước) nên tổng thời giản là O(logn*nlogn) = O(n(logn)^2)

Ví dụ 3. SPOJ - Binary search 1

Tóm tắt:

Cho dãy số A gồm N số nguyên đã được sắp xếp tăng dần và Q truy vấn, mỗi truy vấn là một số nguyên X. Với mỗi truy vấn, hãy tìm vị trí xuất hiện của X trong A? Nếu không tồn tại giá trị X trong A, in ra -1.

Input:

-  Dòng đầu ghi N, Q

-  Dòng thứ hai ghi N số nguyên  

-  Q dòng tiếp theo mỗi dòng ghi một số nguyên X

Output:

      - Với mỗi truy vấn, hãy in kết quả trên một dòng 

ví dụ:

Ràng buộc:

-10^9 <= ai <= 10^9, 0 < N <= 10^5, 0 < Q <= 5*10^5 

Gợi ý:

• Sol1: Tìm kiếm tuần tự. Yêu cầu đánh giá độ phức tạp + cài đặt sol1

• Sol2: Tìm vị trí phần tử x trên dãy A đã sắp xếp tăng dần. Nếu không tồn tại x trong A, in ra -1.

Tìm kiếm nhị phân: tìm x, trên dãy A, từ phần tử low tới high. 

Nguồn: Tài liệu duyên Hải Bắc Bộ 2021

Ví dụ 4.  Leetcode - Find First and Last Position of Element in Sorted Array

Tóm tắt:

Cho dãy A được sắp xếp tăng dần . Có Q truy vấn, mỗi truy vấn là một số nguyên k:

-        Với mỗi k, hãy in ra số đầu tiên bé nhất có giá trị lớn hơn hoặc bằng k gọi là P

Ví dụ:

Dãy A = {1,2,2,3,4,4,4,5,6,6}

Với k = 2

à số đầu tiên nhỏ nhất có giá trị lớn hơn hoặc bằng tại vị trí id=2; Dãy số: A={1,2,2,3,4,4,4,5,6,6}

Input:

-   Dòng đầu ghi N, Q

-  Dòng thứ hai ghi N số nguyên  

-  Q dòng tiếp theo mỗi dòng ghi một số nguyên x.

Output:

-        Với mỗi truy vấn, hãy in kết quả trên một dòng là số P; nếu không tồn tại giá trị lớn hơn hoặc bằng k, in ra -1

Ví dụ: 

Input:

10 2

1 2 2 3 4 4 4 5 6 6

2

4 

Output:

2

5 

Gợi ý:

Sol1: Tìm tuần tự

Sol2 cải tiến : Tìm x đầu tiên nhỏ nhất có giá trị >=x

-        ans = -1

-        Khi L<=R

o   giữa = (L+R)/2;

o   Nếu a[giữa]<x thì tìm x trong [giữa+1, R]

o  

Else tìm x trong [L, giữa-1], ans = giữa

-        return ans

Nguồn: Tài liệu duyên Hải Bắc Bộ 2021

Ví dụ 5. Leetcode - Sqrt(x)

Tóm tắt:

Cho số nguyên x, tìm giá trị căn bậc hai của x lấy phần nguyên.

Yêu cầu: Không sử dụng hàm thư viện.

Input:

-        Số nguyên x

Output:

-        Một số nguyên là kết quả.

Ví dụ:

Input       | Output

------------------------

50          | 7

------------------------

10          | 3

Gợi ý:

-        Biết rằng giá trị cần tìm sẽ trong đoạn [0,x] à L=0; R=x: Gọi phần nguyên kết quả sqrt(x) là k thoả mãn k*k>=x; tìm k đầu tiên, nhỏ nhất thoả mãn k*k>=x

> Nếu mid*mid<=x thì tìm ở [mid+1, R]; ans=mid

      > Ngược lại tìm trong [L, mid-1] 

Nguồn: Tài liệu duyên Hải Bắc Bộ 2021

Ví dụ 6. VNOJ - Đào vàng

Tóm tắt:

Có N thoải vàng đặt trên một hàng ngang ở các vị trí a1, a2,...aN. Người đào vàng dùng một lực đập R tại vị trí X thì sẽ lấy được tất cả các thoải vàng trong đoạn [X - R; X+R]. Người đào có thể đập tối đa k lần với lực đập giống nhau, lực đập càng nhỏ thì điểm thu được càng cao. Hãy tìm lực đập nhỏ nhất để lấy được hết N thoải vàng.

Input:

• Dòng đầu là hai số nguyên N, k

• N dòng tiếp theo, mỗi dòng là vị trí của một thoải vàng

Output:

• Lực đập R nhỏ nhất trong tối đa k lần đập để lấy hết N thoải vàng.

Ví dụ:

Input:

6 1

2

20

6

5

4

17

Output:

9

Ràng buộc và giải thích xem tại bài gốc trên VNOJ

Gợi ý:

• Sắp xếp vị trí các thoải vàng tăng dần

• Chắt nhị phân theo lực đập.

• Mỗi giá trị của R ta check xem với k lần đập có lấy hết toàn bộ các thoải vàng hay không.

• Việc check cho một giá trị R có thoải mãn hay không ta thực hiện như sau:

  • Bắt đầu từ a1, ta cộng 2R xem phủ tới a mấy trong lần đập đầu.

  • Tăng k lên và tại vị trí a mới đó ta lại cộng 2R, tiếp tục như vậy đến khi phủ được tới aN trả về True

  • Nếu sau k lượt đập mà không phủ tới aN thì trả về False.

Nguồn: Tuyển sinh 10, 2023-2024, TP.HCM

Ví dụ 7. LQĐ OJ - Đếm cặp đôi

Tóm tắt:

Cho dãy số 𝐴 gồm 𝑛 phần tử nguyên dương 𝐴1, 𝐴2,…, 𝐴𝑛. Mỗi phần tử có giá trị không vượt quá 109 và 𝑛≤105. Một cặp số được gọi là cặp tương đồng với 𝑥, nếu cặp số này có tổng bằng số 𝑥 cho trước nào đó.

Yêu cầu: Hãy đếm xem trong dãy số 𝐴 có bao nhiêu cặp số (𝐴𝑖; 𝐴𝑗) tương đồng với 𝑥 (có nghĩa là 𝐴𝑖+𝐴𝑗=𝑥) với 𝑖<𝑗.

Input:

·   Dòng đầu tiên chứa dãy số 𝑛,𝑥 (𝑛≤105,𝑥≤106).

·   Dòng thứ 2 chứa 𝑛 phần tử của dãy số 𝐴 (𝐴𝑖≤109).

Output:

·   Ghi ra một số nguyên là cặp đôi tương đồng của dãy số.

Ví dụ:

Input              | Output

----------------------------

7 6                | 4

1 2 4 3 4 5 3      |

Gợi ý:

Sols1 trâu: xét mọi cặp (i,j); kiểm tra điều kiện và đếm O(n^2)

Sols2 cải tiến – TKNP: O(nlogn)

-        Sắp xếp lại dãy tăng dần

-        Với mỗi vị trí i, tìm vị trí j thoả mãn a[j]=x-a[i] bằng TKNP

Sols3 – đếm phân phối 

Nguồn: Tài liệu duyên Hải Bắc Bộ 2021

Ví dụ 8. LQDOJ - Tập xe

Tóm tắt:

Cô giáo trường tiểu học 𝑋 đang dạy 𝑛 học sinh tập xe đạp, các học sinh được đánh số từ 1 tới 𝑛, học sinh thứ 𝑗 có trọng lượng là 𝑎𝑗. Có một xe đạp duy nhất với tải trọng là 𝑚, hai học sinh chỉ có thể cùng lên xe nếu tổng trọng lượng của hai học sinh không vượt quá 𝑚.

Cô giáo tự hỏi có bao nhiêu cách chọn hai học sinh khác nhau cho cùng lên xe, sau nhiều giờ tính toán không có kết quả, cô quyết định hỏi các chuyên gia lập trình giải bài toán Counting Student Pairs (CSP)

Yêu cầu: Đếm số cặp chỉ số 𝑖,𝑗 trong đó 𝑖<𝑗 và 𝑎𝑖+𝑎𝑗≤𝑚

Input:

-        Dòng 1 chứa hai số nguyên dương 𝑛,𝑚 (𝑚≤106)

-        Dòng 2 chứa 𝑛 số nguyên dương 𝑎1,𝑎2,…𝑎𝑛 (∀𝑖:𝑎𝑖≤106)

Output:

-        Ghi một số nguyên duy nhất là đáp số

Ví dụ:

Input        |Output

---------------------

5 6          |6

1 2 3 4 5    |

Giới hạn:

-        SubTask1: 𝑛≤104. (60% test)

-        SubTask2: 𝑛≤105. (20% test)

-        SubTask3: 𝑛≤106. (20% test)

Gợi ý: Tìm nhị phân

Với mỗi a[i], tìm vị trí j cuối cùng (lớn nhất) thoả mãn điều kiện a[j]<=m-a[i] (upper_bound, lower_bound) 

Nguồn: Tài liệu duyên Hải Bắc Bộ 2021

Ví dụ 9. VNOJ - Hang động

Nhiệm vụ:

Nhiệm vụ 1. Careful Accent (Kattis)

Nhiệm vụ 2. The Monkey and Boiled Bamboo (Online Judge)

Nhiệm vụ 3. Bit Maps (Online Judge)

Nhiệm vụ 4. Exact Sum (Online Judge)

Nhiệm vụ 5. Small Factors (Online Judge)

Nhiệm vụ 6. Traveling Monk (Kattis)

Nhiệm vụ 7. Thực hiện contest ngắn: Practice Divide and Conquer

Nhiệm vụ 8. Thực hiện contest ngắn: Practice Binary Search