Pointers for solving this challenging Dynamic Programming task

Question

I have been stuck on a problem in the PEG Online Judge, called Dominos, which you can find here:

http://wcipeg.com/problem/domino

Abridged Description:

We are given a list of dominos with different heights and locations, arranged horizontally. A domino at position x with height h, once pushed to the right, will knock all dominoes at positions x+1, x+2, ..., x+h rightward as well. Conversely, the same domino pushed to the left will knock all dominoes at positions x-1, x-2, ..., x-h leftward.

What is the minimum number of pushes we can do to topple all dominos?

Example:

              |
  |           |
| | |   | |   |
1 2 3 4 5 6 7 8

Answer is 2. Push the domino at location 1 rightward, the domino at location 8 leftward.

Constraints:

The input starts with a single integer N ≤ 100,000, the number of dominoes, followed by N pairs of integers. Each pair of integers represents the location and height of a domino. (1 ≤ location ≤ 1,000,000,000, 1 ≤ height ≤ 1,000,000,000) No two dominoes will be in the same location.

Memory Limit: 64mb

Time Limit: 1.00s

NOTE: 60% of test data has N ≤ 5000.

There is a brute-force solution which solves the problem only for 60% of the input.

It looks like there should be a subquadratic, or even linear solution using dynamic programming in order to get AC for the largest input size.

Any hints would be appreciated.

There is a hint from the author, which I could not quite understand, in case it is helpful:

Make a recursive function f(n) that gives the minimum # of moves required to topple the first n dominoes.

Now how do you relate f(n) to previous values of f? Domino #n has two choices: go left (in which case it topples other dominoes over) or go right (in which case another domino to its left topples it over). Try working from there.

Thanks!

Answer 1

Here is an O(N log N) solution:

1. Let's figure out how to compute what is the leftmost domino that falls if we push the i-th domino to the left (let's denote is as L[i]). The first idea that comes to one's mind is to run simple simulation. But that would be way too slow. I claim that we can just maintain a stack of "interesting" domino indices when we iterate from left to right. The pseudo code for it looks like this:

   s = Empty stack of dominos
   for i = 0 .. n - 1
       while we can knock s.top() domino by pushing the i-th to the left
           s.pop()
       the s.top() is the rightmost domino we cannot hit 
       (if s is empty, we can hit all of them)
       s.push(i-th domino)
   

   This code runs in linear time (each domino is pushed exactly once and popped at most once). It might seem not very intuitive (I will not write a full formal proof here because it would be too long), but working through small examples manually can help to understand why it is correct.
   In fact, this technique is worth understanding because it is commonly used in competitive programming (when something moves from right to left and we need to find the leftmost element that satisfies some condition for each right element. I know that it sounds sort of vague).

2. We can compute the R[i] (how far we can go if we push the i-th domino to the right) in linear time in the same manner.

3. Now we know what happens if we choose to push any domino in any direction. Cool!

4. Let's use dynamic programming to compute the answer. Let f(i) be minimum number of actions we need to make so that all dominoes up to i-th inclusively are knocked down and the rest is still untouched. The transitions are quite natural: we either push the domino to the left or to the right. In the former case we make a transition f(j) + 1 -> f(i), where L[i] - 1 <= j < i. In the latter case the transition is f(i - 1) + 1 -> f(R[i]). This solution is correct because it tries all possible actions for each domino.

5. How to make this part efficient? We need to support two operations: updating a value in a point and getting a minimum in a range. A segment tree can handle them in O(log N). It gives us an O(N log N) solution.

If this solution seems too hard, you can first try and implement a simpler one: just run the simulation to compute the L[i] and R[i] and then compute the dynamic programming array by definition (without a segment tree) to get a really good understand of what these things mean in this problem (it should get 60 points). Once you're done with that, you can apply the stack and the segment tree optimization to get a full solution.

In case some of the details are unclear, I provide an implementation of a correct solution so that you can look them up there:

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

vector<int> calcLeft(const vector<pii>& xs) {
    int n = xs.size();
    vector<int> res(n, 1);
    vector<int> prev;
    for (int i = 0; i < xs.size(); i++) {
        while (prev.size() > 0 && xs[prev.back()].first >= xs[i].first - xs[i].second)
            prev.pop_back();
        if (prev.size() > 0)
            res[i] = prev.back() + 2;        
        prev.push_back(i);
    }
    return res;
}

vector<int> calcRight(vector<pii> xs) {
    int n = xs.size();
    for (int i = 0; i < xs.size(); i++)
        xs[i].first = -xs[i].first;
    reverse(xs.begin(), xs.end());
    vector<int> l = calcLeft(xs);
    reverse(l.begin(), l.end());
    for (int i = 0; i < l.size(); i++)
        l[i] = n + 1 - l[i];
    return l;
}

const int INF = (int) 1e9;

struct Tree {

    vector<int> t;
    int size;

    Tree(int size): size(size) {
        t.assign(4 * size + 10, INF);
    }

    void put(int i, int tl, int tr, int pos, int val) {
        t[i] = min(t[i], val);
        if (tl == tr)
            return;
        int m = (tl + tr) / 2;
        if (pos <= m)
            put(2 * i + 1, tl, m, pos, val);
        else
            put(2 * i + 2, m + 1, tr, pos, val);
    }

    void put(int pos, int val) {
        put(0, 0, size - 1, pos, val);
    }

    int get(int i, int tl, int tr, int l, int r) {
        if (l == tl && r == tr)
            return t[i];
        int m = (tl + tr) / 2;
        int minL = INF;
        int minR = INF;
        if (l <= m)
            minL = get(2 * i + 1, tl, m, l, min(r, m));
        if (r > m)
            minR = get(2 * i + 2, m + 1, tr, max(m + 1, l), r);
        return min(minL, minR);
    }

    int get(int l, int r) {
        return get(0, 0, size - 1, l, r);
    }
};

int getCover(vector<int> l, vector<int> r) {
    int n = l.size();
    Tree tree(n + 1);
    tree.put(0, 0);
    for (int i = 0; i < n; i++) {
        int x = i + 1;
        int low = l[i];
        int high = r[i];
        int cur = tree.get(x - 1, x - 1);
        int newVal = tree.get(low - 1, x - 1);
        tree.put(x, newVal + 1);
        tree.put(high, cur + 1);
    }
    return tree.get(n, n);
}


int main() {
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<pii> xs(n);
    for (int i = 0; i < n; i++)
        cin >> xs[i].first >> xs[i].second;
    sort(xs.begin(), xs.end());
    vector<int> l = calcLeft(xs);
    vector<int> r = calcRight(xs);
    cout << getCover(l, r) << endl;
    return 0;
}