Nested loops complexity reduction

help
,
1

Question Link:- https://codeforces.com/contest/1520/problem/D

My Solution

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int main()

{

    fast

    int t;

    cin>>t;

    while(t--)

    {

       ll n;

       cin>>n;

       ll count=0;

       ll arr[n];

       for(ll i=0;i<n;i++){

           cin>>arr[i];

       }

       for(ll i=0;i<n;i++){

            for(ll j=i+1;j<n;j++){

                if(arr[j]-arr[i]==j-i){

count++;

                }

            }

       }

       cout<<count<<endl;

    } 

    return 0;

}

I was getting an TLE on test 4 /5.
As Time limit was 2 seconds ,my code was O(n^2) hence it must have passed all the test cases .
Kindly Help(Correct my code).

1 Like
2

Your approach is too naive to pass.

3

Observe that a_j - a_i = j - i implies a_j - j = a_i - i. Therefore you can store the values of a_j - j in a map. Now for same values of a_j - j, you need to add {cnt \choose 2} to answer where cnt is the count of values.
Do you want the code or you want to try it once more?

1 Like
4

Yeah senior, I agree. But Can’t this code can be easily passed in 2 secs?
The sum over all test cases were 2*10^5

5

I Will try, senior.

6

But there were 10^4 test cases , i.e. overall complexity is \mathcal{O}(TN^2) hence 10^4 \times 2 \times 10^5 =2 \times 10^9 which is more than 2\times 10^8. Your code’s estimated runtime would be 10 seconds.

7

Though, I think 10^8 iterations can be done in one second in CPP. Correct me if i am wrong.

8

Yes and so in 2 seconds 2\times 10^8 operations can be processed. But you are doing 2\times 10^9. In fact more than that as \displaystyle \sum N\le2\times10^5 so \displaystyle \sum N^2 would be of the order 10^{10} which is anyways more than 2\times 10^8

2 Likes
9

Got it.