NPAIRS - Editorial

PROBLEM LINK:

Practice
Div1
Div2
Div3

Setter: Mradul Bhatnagar
Tester: Samarth Gupta
Editorialist: Ajit Sharma Kasturi

DIFFICULTY:

SIMPLE

PREREQUISITES:

None

PROBLEM:

We are given a string of length N consisting of only numeric characters. We need to find the number of pairs i, j where 1 \leq i \lt j \leq N and j-i = \mid S_j - S_i \mid.

EXPLANATION:

  • The main observation in this problem is to find the maximum possible value of \mid S_j - S_i \mid. The maximum possible value is 9 when S_i =0, S_j=9 or S_i = 9, S_j=0.

  • So, it is enough that we check for pairs i, j where i \lt j and j-i \leq 9.

  • We can theerefore iterate over i from 1 to N, and iterate over j from i+1 to \min (i+9, N) and check the condition j-i = \mid S_j - S_i \mid holds true or not. If it is true, we increment our answer.

  • We will also fit our solution in the time limit because the number of pairs we are considering is O(9 \cdot N) which takes linear amount of time to run.

TIME COMPLEXITY:

O(N) for each testcase.

SOLUTION:

Editorialist's solution
#include <bits/stdc++.h>
using namespace std;

int main()
{
     int tests;
     cin >> tests;
     while (tests--)
     {
          int n;
          cin >> n;
          string s;
          cin >> s;

          int ans = 0;

          for (int i = 0; i < n; i++)
          {
               for (int j = i + 1; j <= min(i + 9, n - 1); j++)
               {
                    if (abs(s[j] - s[i]) == j - i)
                         ans++;
               }
          }

          cout << ans << endl;
     }
     return 0;
}

Setter's solution

#include <bits/stdc++.h>    
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//using namespace __gnu_pbds; 
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb  push_back
#define show(x) cout<<(#x)<<" : "<<x<<endl;
#define ll  long long
#define ld  long double
#define fill(a,val) memset(a,val,sizeof(a))
#define mp  make_pair
#define ff  first
#define ss  second
#define pii pair<ll,ll>
#define sq(x) ((x)*(x))
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define endl "\n"
#define int long long 
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
const ll MOD     = 1000*1000*1000+7;
const ll INF     = 1ll*1000*1000*1000*1000*1000*1000 + 7;
const ll MOD2    = 998244353;
const ll N       = 1000*100 + 10;
const ll N2      = 70;
const ld PI  = 3.141592653589793;
//template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);} 
ll power(ll x,ll y,ll p ){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
ll lcm(ll a , ll b){return (a*b)/gcd(a,b);}

signed main()
{
    fastio();
    //cout<<fixed<<setprecision(20);
    //CHECK for LONG LONG and LONG DOUBLE
    //*comment for all except cc/cf    
    #ifndef ONLINE_JUDGE    
           freopen("input.txt","r",stdin);
           freopen("output.txt","w",stdout);
    #endif//*/
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;	
        string s;
        cin>>s;
        int ans = 0;
        for (int j = 0; j < n; ++j)
        {
        	for(int k = 1 ; k < 10 ; k++)
        	{
        		int i = j-k;
        		if(i < 0) break;

        		if(k == (abs(s[i]-s[j])) )
        		{
        			ans++;
        		}

        	}
        }

        cout<<ans<<endl;

    }
    printclock;
    return 0;
}


Tester's solution
#include <bits/stdc++.h>
using namespace std;

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;
            }
            assert(l<=x&&x<=r);
            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,' ');
}
 
void readEOF(){
    assert(getchar()==EOF);
}

int main() {
	// your code goes here
	int t = readIntLn(1, 1000);
	int sum = 0;
	while(t--){
	    int n;
	    cin >> n;
	    sum += n;
	    assert(sum <= 2e5);
	    string s;
	    cin >> s;
	    for(auto j : s)
	        assert('0' <= j && j <= '9');
	    int ans = 0;
	    for(int i = 0; i < n ; i++)
	        for(int j = i + 1 ; j < min(i + 10, n) ; j++)
	            if(j - i == abs(s[j] - s[i]))
	                ans++;
	    cout << ans << '\n';
	}
    //readEOF();
	return 0;
}


Please comment below if you have any questions, alternate solutions, or suggestions. :slight_smile:

3 Likes

my solution

I would like to know why mine gets tle.
the given condition in i-j = abs(s[i]-s[j]) which also means that either i+s[i] = j+s[j] or i-s[i] = j-[s[j]
could you please help me to get my solution under time limit with my approach.

If I’m not mistaken, the time complexity of your code is O(N^2) as you use count while iterating through s2.

O(N^2) will not pass as N \leq 10^5

2 Likes

An alternate solution I found was as follows :

the basic problem here is find all the elements that have
i-j=|S[i]-S[j]|
so, this will lead to two possibilities :
i-S[i] = j-S[j] or i+S[i]=j+S[j]
so count the number of occurrences of X such that X = i+S[i] and X = i-S[i] (I Stored them in a hash map)
now for each value of X , if X>1, find the number of combinations of X that create a pair and add it to your counter.

Here is my cpp code :

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

int main() {
	// your code goes here
	long long int t;
	cin>>t;
	while(t--){
	    long long n,cnt=0;
	    cin>>n;
	    string s;
	    cin>>s;
	    vector<int> a(n);
	    map<int,int> mp;
	    map<int,int> mn;
	    for(int i=0;i<n;i++){
	        a[i]=s[i]-'0';
	        mp[a[i]+i]++;
	        mn[a[i]-i]++;
	    }
	    for (auto i = mp.begin(); i != mp.end(); i++){
	        if(i->second>1){
	            int sec = i->second;
	            cnt+=(sec*(sec-1)/2);
	        }
	    }
	    for (auto i = mn.begin(); i != mn.end(); i++){
	        if(i->second>1){
	            int sec = i->second;
	            cnt+=(sec*(sec-1)/2);
	        }
	    }
	    cout<<cnt<<"\n";
	   }

	return 0;
}

#include<bits/stdc++.h>
#define ll long long int
using namespace std;

int fect(int n)
{
return (n==1 || n==0) ? 1: n * fect(n - 1);
}
int np(int n, int r)
{
return fect(n) / (fect(n - r));
}
int main()
{
ll t;
cin>>t;
while(t–)
{
ll e;
cin>>e;
string k;
cin>>k;
int s=0;
int a[e];
for(ll i=0;i<e;i++)
{
int f=k[i]-‘0’;
a[i]=i-f;
}
sort(a,a+e);
int y=1;
for(ll i=0;i<e-1;i++)
{
if(a[i]==a[i+1])
{
y++;
}
else
{
if(y>1)
{
s+=np(y,2);
}
y=1;
}

  }
  if(y>1)
          {
              s+=np(y,2);
          }
  for(ll i=0;i<e;i++)
  {
      int f=k[i]-'0';
       a[i]=i+f;
  }
  sort(a,a+e);
  int p=1;
  for(ll i=0;i<e-1;i++)
  {
      if(a[i]==a[i+1])
      {
         p++;
      }
      else
      {
          if(p>1)
          {
              s+=np(p,2);
          }
          p=1;
      }
  }
  if(p>1)
          {
              s+=np(p,2);
          }
          p=1;
  cout<<s/2<<endl;

}
}

Same idea , but different implementation . Here , it’s my solution . Hope you like it ! :slightly_smiling_face:
Solution: 52360976 | CodeChef.

The solution given by the editor, is also O(N^2) only na…, how is it O(9N), or O(N)?
what I understood from the editor has given as the solution as:
for(int i=1;i<N;i++)
{
for(int j=i+1;j<min(i+9,N);j++)
{
…comparision condition…
}
}

Now, as i itself starts from 1, so min(i+9,N) will always be N…
So, even the editorial solution is O(N^2)…, how it is O(9N) or O(N)?

Please explain…

thanks man, this is exactly what i was seeking
:slight_smile:

it is of O(9.N) in worst case as in second loop j is traversing upto min(i+9 , N) in which when you will take a big constraints it will give O(9.N) which is also equivalent to O(N).
You can also say that the second loop will only run for 9 times at worst.

Go and check out my HASH MAP solution with a logic that j-i=|Sj-Si| will result into either
j-i = Sj-Si or i-j = Sj-Si.

this will result into either Sj-j = Si-i or Sj+j = Si+i.

hence we will store occurences of Si-i and Sj-j for every 1 <= i <= N.

https://www.codechef.com/viewsolution/52386085

Clean solution that works for arbitrary sequences (doesn’t rely on the digits being values from 0-9):

for (int step = 0; step < 2; step++) {
    map<int, int> freq;
    for (int i = 0; i < n; i++)
        freq[a[i] - i]++;
    for (auto [k, v] : freq)
        ans += nc2(v);

    reverse(all(a));
}

(Link to submission)

1 Like

Where it fails??
WA:-Solution: 52336407 | CodeChef

@ultradluffy8 I am still not getting that how will it be O(9N)…

The solution given by the editor, is also O(N^2) only na…, how is it O(9N), or O(N)?
what I understood from the editor has given as the solution as:
for(int i=1;i<N;i++)
{
for(int j=i+1;j<min(i+9,N);j++)
{
…comparision condition…
}
}

Lets analyze:
Now, as i itself starts from 1, so min(i+9,N) will be as follows…
min(1+9,N)=10–>loop j runs 10 times.
min(2+9,N)=11–>loop j runs 11 times.
min(3+9,N)=12–>loop j runs 12 times.
min(4+9,N)=13–>loop j runs 13 times.
…continuing…
min(N-9+9,N)=N–>loop j runs N times.
min(N-8+9,N)–>loop j runs N times.
min(N-7+9,N)–>loop j runs N times.
…till min(N+9,N)–>where loop j runs N times.

So how is it that, loop j will run at “most 9” times?

Please explain…

@anyone?

PS: I haven’t really done with the hash map, so I am not commenting on the solution given by other guys. As soon as I will complete it, I will revisit the solution of hash map as well.

Here’s a similar approach but with a break statement and nested for loops.

// Don't Just copy the code, Understand it first.
// -- theskyspace(Insta profile also) ;)

#include <bits/stdc++.h>
using namespace std;
#define deb(x) cout << #x << " = " << x << endl;
#define deb2(x,y) cout << #x << " = " << x << " , " << #y << " = " << y << endl;
typedef long long ll;
typedef pair<int , int> pairs;
ll M = 10e8 + 7;


void solve(){
    // Let's start
    ll n;
    string s;
    ll count = 0;
    cin >> n >> s;



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

            if (j-i > 9)
            {
                break;
            }
            

            if(j-i == abs(s[j] - s[i])){
                count++;
            }
        }
        
    }

    cout << count << endl;
    
  
}






//Driver's code
int main(){
    // Stdin and stdout.
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
   
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    
    return 0;
}

https://www.codechef.com/viewsolution/52354450
can anyone help me with this code I’m not able to find why it is giving WA what is flaw in the logic?

it is like that it max to max run to 9 elements further because after that difference between i and j is always greater than 9 and we can never obtain the required solution therefore no need of running it N^2 times :)…

1 Like

@prit_esh_07 Yeah, I got the thing that diff of j-i is max 9.
But in order to travel the whole string, i.e, upto the size of the string(or we can say the last element of the string…), it is basically N–>size of the string. I am talking abt inner loop , or loop j btw…

@ajit123q could you explain the solution which you have given…, sorry but I still fail to understand that how will the j loop, min(i+9,N) will not be O(N)…

or anyone plz?

the thing is that u dont’t have to traverse j to whole N u have to ensure condition upto 9 elements ahead for every i just think in that manner .

@prit_esh_07 ya, sorry I wasn’t considering that j is running from i+1… :sweat_smile:, so yeah, no issues now!

:v: