Module 1: Trie

Trie

Module 2: Sparse Table

Sparse table

Module 3: Segment Tree

Segment tree
Maximum subarray sum on a given segment

Module 4: Segment Tree Lazy propagation

Segment Tree with Lazy Propagation

Module 5: More on trees

Euler order of visiting vertices
DP on a tree (Tree DP)

Module 6: Binary jumping

Binary Lifting (Jumps)
Lowest common ancestor

Module 7: Cyclic Games

Games on Cyclic Graphs

Module 8: Divide & Conquer

Divide and conquer

Module 9: SQRT Techniques

SQRT Decomposition
SQRT heuristics
Mo’s Algorithm

Divide and conquer - Preparation to IOI Part 4

Home Courses Resources Problems National Olympiad Contests Leaderboard

...

Home/Courses/Preparation to IOI Part 4/Module 8: Divide & Conquer/Divide and conquer

Divide and conquer

Divide and conquer

Introduction

Divide and conquer is an algorithmic technique in which a problem is solved using the “Divide, conquer, and combine” strategy.

A typical “Divide and conquer” algorithm solves a problem using the following three steps:

Divide: splitting the problem into smaller subproblems.
Conquer: solving the subproblems by recursive calls until they are solved.
Combine: combining the subproblems to obtain the final solution to the original problem.

Application

Problem statement

Given an array $a_1, a_2, \ldots, a_n$ of numbers. It is required to sort the array in using the “Divide and conquer” technique.

n

O(NlogN)

Solution

Let’s implement a function $sort(a)$ that takes an array as input and returns a sorted array.

If $n = 1$ , then we simply return $a$ , since an array of one element is sorted.
If $n \ne 1$ . Let $m = \lfloor \frac{n}{2} \rfloor$ , split the array into 2 parts $a[1 \ldots m]$ and $a[m+1 \ldots n]$ . Sort these parts separately by recursively calling $sort(a[1 \ldots m])$ and $sort(a[m+1 \ldots n])$ . Store their results in $L$ and $R$ respectively. Merge the 2 sorted arrays into one in $O(|L| + |R|)$ and return the result.

Implementation

vector<int> sort(vector<int> a) {
    if (a.size() <= 1) {
        return a;
    }
    int m = a.size() / 2;

    vector<int> L = sort(vector<int>(a.begin(), a.begin() + m));
    vector<int> R = sort(vector<int>(a.begin() + m, a.end()));

    vector<int> res;
    merge(L.begin(), L.end(), R.begin(), R.end(), back_inserter(res));
    return res;
}