AITC2G12 - Editorial

editorial
1

PROBLEM LINK:

Practice

Contest Link:

Setter: Rahul Kumar

Tester: Rahul Kumar

Editorialist: Anushwar Sharma

DIFFICULTY:

Simple

PREREQUISITES:

Basic observations, Array.

PROBLEM:

Given an array of N elements A_1,A_2,A_3...A_N. A pair (A_i,A_j) is said to be good if i<=j and A_i-A_j=A_i*A_j.
Find the number of good pairs in the array.

You have to print the Chef’s data at every checkpoint.

EXPLANATION

You need to observe and find that there are only two possible pairs one is (0,0) and the other is (-2,2). Other than these two pairs as the values of A_i and A_j increases (in negative as well as positive),

the right-hand side part i.e, A_i*A_j will increase rapidly. Note that (2,-2) will not be satisfied because it will make LHS 4 and RHS -4.

Then you have to find the two pairs in the array. For finding pairs of (0,0), i<=j is given so for every zero in the array you will get one pair.

then pair of one zero with other remaining zeros, pair of second zero with remaining zeros, and so on. If we have a total of z zeros the sum of pairs will be z+(z-1)+(z-2)...1 i.e, equal to z*(z+1)/2.

For (-2,2),

we will keep a record of the no. of -2 found. One -2 will pair with all 2 which will come after it. So we will increase the count every time we get -2 and when one 2 is found

then all -2 will pair with it i.e,(-2,2). So we add the no. of -2s in total s.

Tn the last we add the pairs of (0,0) also in s.

SOLUTION:

Editorialist's Solution 
#include<bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long int
#define vi vector<int>
#define w(x) int x; cin>>x; while(x--)
#define pb push_back 

int32_t main() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif   
    fio
    int T;
    cin>>T;
    while(T--)
    {
        ll n,s=0,a=0,b=0,z=0;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            ll x;
            cin>>x;
            if(x==-2)
                a++;
            if(x==2)
                s=s+a;
            if(x==0)
                z++;
        }
    s=s+z*(z+1)/2;
        cout<<s<<"\n";
    }
}

Note: If you are a beginner, don’t be scared of the few lines that have been written at the top. Just focus on the code starting from the variable declaration and if you don’t understand any shorthand terminology mentioned in the code, look at the top “#define” , where we have defined all the constants used in the code.

Feel free to share your approach, if you want to(even if it’s the same). Suggestions are welcomed as always had been. :slight_smile: