Pointers for solving this complex dynamic programming problem

Question

I ran into a problem in an online PEG judge called Dominos, which you can find here:

http://wcipeg.com/problem/domino

Short description:

We are given a list of dominoes with different heights and locations located horizontally. Dominoes at position x with a height h once pressed to the right will knock all dominoes at positions x + 1, x + 2, ..., x + h to the right. Conversely, the same domino shifted to the left knocks all the dominoes in positions x-1, x-2, ..., xh to the left.

What is the minimum number of clicks we can do to overthrow all dominoes?

Example:

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

Answer 2 . Push dominoes to position 1 to the right, dominoes to position 8 to the left.

Limitations:

Input starts with a single integer N ≤ 100,000, the number of dominoes, and then N pairs of integers. Each pair of integers represents the location and height of the dominoes. (1 ≤ location ≤ 1,000,000,000, 1 ≤ height ≤ 1,000,000,000) There are no two dominoes in the same place.

Memory limit: 64 MB

Time Limit: 1.00 s

NOTE. 60% of test data have N ≤ 5000.

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

It seems like there must be a sub-quadratic or even linear solution using dynamic programming to get AC for the largest input size.

Any clues would be appreciated.

There is a hint from the author that I could not understand if this is useful:

Make a recursive function f (n), which gives the minimum number of steps to overthrow the first Russian dominoes.

Now, how do you relate f (n) to previous f values? Domino #n has two choices: go left (in this case, it overthrows the other dominoes) or go right (in this case, another domino to the left of it overthrows). Trying to work from there.

Thanks!

Answer 1

Here is the O(N log N) solution:

• Let us know how to calculate what is the left-most domino that falls if we push the i-th domino to the left (denote it as L[i] ). The first idea that comes to mind is to run a simple simulation. But that would be too slow. I argue that we can simply maintain a stack of “interesting” domino indices when we repeat from left to right. The pseudocode 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 works in linear time (each domino is pushed exactly once and pushed no more than once). This may not seem very intuitive (I will not write a complete formal proof here because it will be too long), but working with small examples manually can help to understand why this is correct.
  Actually, this method is worth understanding, because it is usually 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 fuzzy )

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

• Now we know what will happen if we choose any domino in any direction. Cool!

• Let us use dynamic programming to calculate the answer. Let f(i) be the minimum number of actions that need to be done so that all dominoes up to i-th including i-th knocked down, and the rest remains untouched. Transitions are quite natural: we either push the dominoes to the left or to the right. In the first case, we make the transition f(j) + 1 -> f(i) , where L[i] - 1 <= j < i . In the latter case, the transition f(i - 1) + 1 -> f(R[i]) . This decision is right because it tries all possible actions for each domino.

• How to make this part effective? We need to support two operations: updating the value at a point and getting a minimum in the range. The segment tree can process them in O(log N) . This gives us a solution of O(N log N) .

If this solution seems too complicated, you can first try and implement a simpler option: just run the simulation to calculate L[i] and R[i] , and then calculate the dynamic programming array by definition (without a segment tree) until you get a really good understanding what these things mean in this problem (he should get 60 points). Once you are done with this, you can apply the stack and segment tree optimization to get a complete solution.

If some details are not clear, I provide you with the right solution so that you can look at them 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; } 

Answer 2

This problem can be solved in O (N) without segtree

As noted by Kraskevich, we need to find a minimum in the range from L[i] - 1 to i - 1 . we can save a list of an interesting position and its dp value, in which both positions and the dp value are in ascending order.

When we want to request a minimum from a range, we can easily scan the list from the back and find the smallest point of interest within the range.

After we updated dp[x] , we will put all the points in the list with a larger dp than dp[x] (since this is no longer interesting) and add (x, dp[x]) to the list as new interesting moment.

This runs in linear time.

 int getCover(vector<int> l, vector<int> r) { int n = l.size(); vector<int> dp(n + 1, INF); dp[0] = 0; vector<pii> st; st.emplace_back(0, 0); for (int i = 0; i < n; i++) { int x = i + 1; int low = l[i]; int high = r[i]; int cur = dp[i]; while (st.size() > 1) { pii second_last = st[st.size() - 2]; // if the 2nd last point is within range // then the last point will no longer be interesting if (second_last.first >= low - 1) { // remove the last point st.pop_back(); } else { // the 2nd last point is out of range break; } } dp[x] = min(st.back().second + 1, dp[x]); // continue to pop all the points that are no longer interesting. while (!st.empty() && st.back().second >= dp[x]) { st.pop_back(); } // insert new interesting point st.emplace_back(x, dp[x]); dp[high] = min(dp[high], cur + 1); } return dp[n]; } 

Answer 3

you will create a 2D array in which each cell contains a pair (L, R) that denotes a domino omitted by a certain position

The initial position indicated by pressing (left, right) by each domino:

  1 2 3 4 5 6 7 8 <0, 2> <1, 1> <2, 0> <0, 0> <0, 1> <1, 0> <0, 0> <2, 0> 

With this, you do not minimize the array by taking a step that will reduce your array to <0, 0> pairs. In this case, move 1 to R, 3 to L, or 8 to L.

1 to R New Array:

  1 2 3 4 5 6 7 8 <0, 0> <0, 0> <0, 0> <0, 0> <0, 1> <1, 0> <0, 0> <2, 0> 

We only have 1 Move left, to 8 to L, so New Array:

  1 2 3 4 5 6 7 8 <0, 0> <0, 0> <0, 0> <0, 0> <0, 0> <0, 0> <0, 0> <0, 0> 

Providing a 2D array:

  1 2 3 4 5 6 7 8 <0, 0> <0, 0> <0, 0> <0, 0> <0, 1> <1, 0> <0, 0> <2, 0> // initial <0, 0> <0, 0> <0, 0> <0, 0> <0, 1> <1, 0> <0, 0> <2, 0> // pushed 1 to R <0, 0> <0, 0> <0, 0> <0, 0> <0, 0> <0, 0> <0, 0> <0, 0> // pushed 8 to L 

Since all cells are now & lt 0, 0>, we are sure that all dominoes have fallen and no one has stopped.