This is a post about one very interesting Divide-and-conquer technique. I call this the “All but one” trick because that's an accurate description of what it can be used for. I learned about this in the Brazilian ICPC Summer School in 2018, thanks to Tomasz Idziaszek and thought it would be a good addition to this blog. In this post, I will briefly explain the technique and show its application in one problem.

This is by no means a complete tutorial about Divide and Conquer and I will assume that the reader is at least familiar to some of the key concepts of the technique and the well-known applications such as Merge Sort and Binary Search.

The problem it solves

This trick is useful to solve the following kind of problem: Imagine there is a structure S with N elements. To build S, you add elements one at a time. You would like to know what S would look like if, for each element, we considered S without it. However, it is computationally expensive to remove an arbitrary single element.

A naive approach to this problem that is very straightforward is to rebuild S multiple times without each element. Even though this approach works, a lot of computations are wasted because many times we have almost the same state for S. After analyzing this, a question arises: is there a more efficient way to do it?

If removing the last addition to S is fast, then the answer is yes. It uses a clever observation that follows nicely into a Divide-and-Conquer Algorithm.

The algorithm

The idea for the algorithm can be described as follows: if we have a set of N elements, we split into two sets of roughly equal size. Then, for one of the halves, we will add all of its elements to S. Notice that by doing this, we arrive at the same conceptual problem for the other half: find S without a single element for each element.

Hence, we can continue the procedure until we arrive with a set of a single element. When that happens, we can answer the query about S without that element. The only missing point with that idea is that we need to answer the query for every element and not only for a single one. To solve this, we just need to change a few things when we recurse up.

The changes are:

• Remove all additions that were made in the step when we recurse up.

• Add the elements of the half that were not added at first, and recurse to the half that was added at first.

• Lastly, we need to undo those add operations when we recurse back to maintain the fact that calling the Divide and Conquer function does not alter the state of S.

Now the algorithm works because we can guarantee that we will arrive at a situation with a single element for every element and that when that happens all the other elements will have been added to S.

If the operation of adding has a complexity of O(K) and the operation of undoing has a complexity of O(L), then the algorithm has an overall complexity of O(N*(K+L)*log(N)). A pseudo-implementation of the algorithm is given below.

void DivideAndConquer(int s, int e){

    // Base case: single element
    if(s == e){
        // Answer your query !
        return ;
    }

    int m = (s+e)/2; // we will split the set into two

    /* 
    First part: add elements of the right,
    recurse to the left and undo
    */

    for(int i = m+1; i<=e; i++){
        // Adding elements of the right half
        add(i);
    }

    DivideAndConquer(s, m); // recursing to the left half

    for(int i = e; i>=m+1; i--){
        // undo all the operations of addition
        undo();
    }

    /*
    Second part: add elements of the left,
    recurse to the right and undo
    */

    for(int i = s; i<=m; i++){
        // Adding elements of the left half
        add(i);
    }

    DivideAndConquer(m+1, e); // recursing to the right half

    for(int i = m; i >= s; i--){
        // undo all the operations of addition
        undo();
    }

}

Example Problem

The problem we will analyze is Voltage from the Japanese Olympiad in Informatics Spring Camp (JOI SC 2014). You may find the problem statement and a place to submit here and the original problem statement in Japanese here.

A synthesis of the problem statement is : There is a circuit with N nodes and M resistors. Each node can be set either to low or high voltage, and current cannot flow through resistors connected to nodes of the same voltage. Calculate how many resistors can be removed such that if we remove only that resistors, there is current flowing in all other resistors.

Reduction to the trick and solution

The problem can be reduced to the following one: check if without an edge E, the graph is bipartite.

The structure to verify if a graph is bipartite while adding edges is a modified Disjoint Set Union-Find. I will not be going into many details, but you may find more explanation about it in this CodeChef discussion.

Removing an arbitrary edge from the DSU is fairly difficult, but removing the last one is not due to the stack-like structure of the DSU. Hence, the problem we have fits in the range of the applications of the trick and can be solved in O(N*log(N)^2). The implementation using the technique follows: