Codeforces 607A. Getting wrong answer

Question

There are n beacons located at distinct positions on a number line. The i-th beacon has position a_i and power level b_i. When the i-th beacon is activated, it destroys all beacons to its left (direction of decreasing coordinates) within distance bi inclusive. The beacon itself is not destroyed however. Saitama will activate the beacons one at a time from right to left. If a beacon is destroyed, it cannot be activated.
Saitama wants Genos to add a beacon strictly to the right of all the existing beacons, with any position and any power level, such that the least possible number of beacons are destroyed. Note that Genos's placement of the beacon means it will be the first beacon activated. Help Genos by finding the minimum number of beacons that could be destroyed.

Here is the link to the question (http://codeforces.com/contest/607/problem/A) Screenshot of question.
My approach is to use Dp to find minimum number of objects not destroyed. dp[i]= minimum number of objects not destroyed if I have only i elements.
- Let inc is the answer when ith object is destroyed by some element present in the right side.Therefore inc = 1 + dp[i-1]

- Let exc is the answer when ith object is not destroyed by some element present in the right side. Since ith element is not destroyed, when we will detonate it, it will destroy all elements within its left limit (a[i]-b[i]). Let's say it can destroy lbd number of elements on left side. Therefore exc = lbd + dp[i-lbd].

Now dp[i] = min{ inc , exc }. Finally return dp[n].

But my code is giving wrong answer in test case 11. Can anyone help me if there is something wrong in my logic or code?
Here is my code snippet
ll = long long int
pll = pair of long int
rep(i,0,n) = loop from 0 to n

void solve(){
    ll n;
    cin>>n;
    vector<pll> a(n);
    vector<ll> b(n);
    rep(i,0,n){
        cin>>a[i].first>>a[i].second;
        b[i]=a[i].first;
    }
    sort(b.begin(),b.end());
    sort(a.begin(),a.end(),cmp);
    vector<ll> dp(n+1,0);
    rep(i,1,n+1){
        ll inc = 1+ dp[i-1];
        ll temp = a[i-1].first-a[i-1].second;
        ll lb = lower_bound(b.begin(),b.end(),temp)-b.begin();
        ll exc=(i-lb-1)+dp[lb];
        dp[i]=min(inc,exc);
    }
    cout<<dp[n]<<endl;
}

Full code link https://ideone.com/THbCLK

Answer 1

The problem

This is how you defined dp[i]:

dp[i] = minimum number of objects not destroyed if I have only i elements.

First of all, I think that there was a typo and you really meant this:

dp[i] = minimum number of objects destroyed if I have only i elements.

Second, if you only have i elements, then the i-th element can never be destroyed by any beacon to its right (since there aren't any). Hence, it is folly to consider the case where the i-th beacon is destroyed by something to its right.

The solution lies in rephrasing your subproblem (dp[i]).

---

Solution #1

Lets define dp[i] this way:

// dp[i] ... The number of beacons destroyed after lighting the i-th beacon

When we light the i-th beacon:

1. It destroys all of the beacons in its power range.
2. Some beacons may have already been destroyed before, unaffected by the i-th beacon.

Combining 1. and 2. we get the following expression for dp[i]:

// lb = Lower Bound - the index of the left-most beacon
// that is still in the power range of the i-th beacon
dp[i] = lb == 0 ? i : i - lb + dp[lb-1];

Note: At most n-1 beacons have to be destroyed. After lighting the i-th beacon, dp[i] beacons are destroyed (those left of the i-th beacon) and at most n-i-1 beacons can still be destroyed (those right of the i-th beacon).

With that in mind, this is how the final answer is produced:

ll ans = n - 1;
rep(i, 0, n) {
    ans = min(dp[i] + n - i - 1, ans);
}

Here is my "Accepted" solution, based on your code and this submission.

---

Solution #2

Lets define dp[i] this way:

// dp[i] ... The number of beacons lit after lighting the i-th beacon

When we light the i-th beacon one of two things can happen:

1. The i-th beacon is so powerful that it kills all beacons to its left, making it the only beacon that is lit
2. The i-th beacon only knocks out some of the beacons to its left

Combining 1. and 2. we get the following expression for dp[i]:

// lb = Lower Bound - the index of the first beacon left of the
// i-th beacon that is out of the power range of the i-th beacon
dp[i] = lb < 0 ? 1 : 1 + dp[lb];

In order to solve the problem one has to find the maximum dp[i]:

// minimum_number_of_beacons_destroyed = n - maximum_number_of_beacons_lit

Here is my "Accepted" solution, based on your code and this submission.

There is also an official editorial, however that solution is unclear to me.

---

Additional notes:

• The beacon that Genos adds is irrelevant - he can always place it as far to the right not to affect any of the existing beacons which is why that information adds nothing to the problem.
• Beacons have to be sorted by position in increasing order beforehand.