SUBARRAYLEN-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: TheScrasse
Tester: Manan Grover, Lavish Gupta
Editorialist: Devendra Singh

DIFFICULTY:

To be calculated

PREREQUISITES:

None

PROBLEM:

You are given an array A of length N.

Determine the count of subarrays of A which contain their length as an element.

Formally, count the number of pairs (L, R) (1\le L\le R\le N) such that: (R-L+1) \in \{A_L, A_{L+1}, \ldots, A_R\}.

EXPLANATION:

Let us iterate over the elements of array A and for each element A_i count the number of pairs (L, R) (1\le L\le i\le R\le N) such that: (R-L+1) = A_i. The number of subarrays of a particular length which contain the element A_i can be found using the following equations:
Left limit for the start of such subarrays = max( 1,\: i - A_i +1)
Right limit for start of such subarrays = min(i, N - A_i+1)
Therefore the number of such subarrays is equal to Right limit-Left limit+1. But this does not account for the overcounting of subarrays. Same subarray could be counted more than once for two same values of array A. For index i = 1\:\: to\:\: N , to avoid overcounting, we will not count the subarrays which have been counted before due to some index j such that A_j=A_i.
Let last_{A_i} represent the index of last occurrence of A_i (initially 0), then the new left limits and right limits are:
left limit = max(last_{A_i} + 1, i - A_i + 1),
right limit = min(i, N - A_i+1)
Therefore the number of such subarrays is equal to Right limit-Left limit+1.
Sum of such subarrays for each index i =\: 1\: to\: N is the answer to the problem

TIME COMPLEXITY:

O(N) for each test case.

SOLUTION:

Setter's solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);

            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }

            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }

            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
int sumN=0;
void solve()
{
    int n=readInt(1,200000,'\n');
    sumN+=n;
    assert(sumN<=500000);
    int A[n+1]={0};
    for(int i=1;i<=n;i++)
    {
        if(i==n)
            A[i]=readInt(1,n,'\n');
        else
            A[i]=readInt(1,n,' ');
        adj[A[i]].pb(i);
    }
    int prev[n+1]={0};
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        ll exceed=i+A[i]-1-n;
        exceed=max(exceed,(ll)0);
        ll total=i-prev[A[i]];
        total=min(total,(ll)A[i]);
        total-=exceed;
        total=max(total,(ll)0);
        ans+=total;
        prev[A[i]]=i;
    }
    cout<<ans<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int T=readInt(1,1000,'\n');
    //cin>>T;
    while(T--)
        solve();
    assert(getchar()==-1);
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
const int N = 2e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
int last[N];
void sol(void)
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        last[i] = -1;
    vll v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];
    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        ll l = max(last[v[i]] + 1, i - v[i] + 1), r = min(i, n - v[i]);
        last[v[i]] = i;
        if (r >= l)
            ans += (r - l + 1);
    }
    cout << ans << '\n';
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int test = 1;
    cin >> test;
    while (test--)
        sol();
}
3 Likes

My code is failing test case 5 and 8. Could you please tell those test cases, I am not able to figure out.

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int ans=0;
        unordered_map<int,int> m;
        for(int i=0;i<n;i++)
        {
            int temp;
            cin>>temp;
            int left=max(0,i-temp+1);
            if(m.find(temp)!=m.end() && m[temp]>=left)
            {
                left=m[temp]+1;
            }
            int right=min(n-1,i+temp-1);
            ans+=(right-left+1-temp+1>0)?right-left+1-temp+1:0;
           // cout<<ans<<endl;
            m[temp]=i;
        }
        cout<<ans<<endl;
    }
}

1 Like

This is also failing 5 and 8. Please help someone.

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int ans=0;
        unordered_map<int,int> m;
        for(int i=0;i<n;i++)
        {
            int temp;
            cin>>temp;
            int left=max(0,i-temp+1);
            if(m.find(temp)!=m.end() && m[temp]>=left)
            {
                left=m[temp]+1;
            }
            int right=min(i,n-temp);
            ans+=(right-left+1>0)?right-left+1:0;
           // cout<<ans<<endl;
            m[temp]=i;
        }
        cout<<ans<<endl;
    }
}

Same. Please specify the test cases that are being used.

1 Like

As answer could be quite large you should use long long instead of int.

1 Like

Thanks, it worked. Sorry for being such a noob :slight_smile:

1 Like

Try changing the data type of left and right from int to long long int. Integer overflow may be creating the problem here as the limit of the total length of the array is pretty large.