CODEWITHSUNDEEP
arraysalgorithmmathdynamic-programming
Madhu
Madhu

Reputation: 27

Count Sub arrays with condition?

I have an array of N integers and M pairs (a,b) -> a,b are indices of array.

I have to count the number of non-empty contiguous subsequences (subsegments) of array A having N elements such that no segment includes the both elements of any of M pairs (in simple words subtract number of segments having both elements of any pair from M from total segments)?

Example : 

 N=5 , M=1 -> pair (1,4) then ans=13 .
 {(1),(2),(3),(4),(5),(1,2),(2,3),(3,4),(4,5),(1,3),(2,4),(3,5),(2,5)}

My tried solution : I have tried to apply dynamic programming but didn't get through it, then tried to think greedy then too am not getting it.

Upvotes: 1

Views: 973

Answers (1)

Badf
Badf

Reputation: 335

Here is O(n + m) solution.

For each index i we are going to find first index j to the left so that we can't have segment starting on j or earlier, and ending on i or further. If we have these indices we can easily achieve our answer, by adding i - left[i] for each index to the answer.

How to find it ?

First, make all first[i] equals to 0. Then read all pairs (a,b) (let's say a <= b) and make left[b] equals to max(left[b], a).

After this let's use dynamic programming. Going from left to the right for each index i > 1, left[i] = max(left[i], left[i - 1]).

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1000000;
int n, m;
int LEFT[MAXN + 5];

int main() {
    ios_base::sync_with_stdio(0);

    cin >> n >> m;

    for(int i = 1; i <= n; i++)
        LEFT[i] = 0;

    for(int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        if(a > b) swap(a, b);
        LEFT[b] = max(LEFT[b], a);
    }

    long long answer = 0;
    for(int i = 2; i <= n; i++)
        LEFT[i] = max(LEFT[i], LEFT[i - 1]);
    for(int i = 1; i <= n; i++)
        answer += i - LEFT[i];
    cout << answer << endl;
}

Upvotes: 1

Related Questions