POSPROD-Editorial

devendra7700 · April 11, 2022, 10:16pm

PROBLEM LINK:

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

Setter: Utkarsh Gupta
Tester: Nishank Suresh, Satyam
Editorialist: Devendra Singh

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You are given an array A of length N. Find the number of pairs of indices (i,j) such that

1 \leq i \lt j \leq n
A_i \cdot A_j \gt 0

EXPLANATION:

The product of two numbers A_i and A_j is positive when A_i and A_j are both positive
i.e. A_i \gt0 and A_j\gt0 OR A_i and A_j are both negative i.e. A_i \lt0 and A_j\lt0. Therefore we can pair all negative numbers together and pair all positive numbers together and then add them together to get the answer.

We can use two variables to count the negative and positive numbers. let neg represent the count of negative numbers and pos represent the count of positive numbers in the array. Then the answer to the problem would be ^{neg}C_2 + ^{pos}C_2 which is (neg\cdot (neg-1))/2 + (pos\cdot (pos-1))/2

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,' ');
}
void solve()
{
    int n=readInt(1,10000,'\n');
    ll pos=0,neg=0;
    for(int i=1;i<=n;i++)
    {
        int c;
        if(i!=n)
            c=readInt(-10000,10000,' ');
        else
            c=readInt(-10000,10000,'\n');
        if(c>0)
            pos++;
        else if(c<0)
            neg++;
    }
    ll ans=(pos*(pos-1))/2 + (neg*(neg-1))/2;
    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,30,'\n');
    while(T--)
        solve();
    assert(getchar()==-1);
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Tester-1's Solution(Python)

for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	pos, neg = 0, 0
	for x in a:
		pos += x > 0
		neg += x < 0
	print(pos*(pos-1)//2 + neg*(neg-1)//2)

Tester-2's Solution

// #pragma GCC optimize("O3")
// #pragma GCC target("popcnt")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>   
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;     
using namespace std;
#define ll long long        
#define pb push_back                 
#define mp make_pair              
#define nline "\n"                             
#define f first                                            
#define s second                                             
#define pll pair<ll,ll> 
#define all(x) x.begin(),x.end()     
#define vl vector<ll>           
#define vvl vector<vector<ll>>    
#define vvvl vector<vector<vector<ll>>>          
#ifndef ONLINE_JUDGE    
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);  
#endif     
void _print(ll x){cerr<<x;}  
void _print(char x){cerr<<x;}   
void _print(string x){cerr<<x;}    
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());   
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";} 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=1e9+7;          
void solve(){     
    ll n; cin>>n;
    vector<ll> a;
    for(ll i=1;i<=n;i++){
        ll x; cin>>x;
        a.pb(x);   
    }
    ll ans=0; n=a.size();
    for(ll i=1;i<n;i++){  
        for(ll j=0;j<i;j++){
            if(a[i]*a[j]>0){
                ans++;
            }
        }
    }
    cout<<ans<<nline;
    return;          
}                                     
int main()                                                                               
{    
    ios_base::sync_with_stdio(false);                         
    cin.tie(NULL);                              
    #ifndef ONLINE_JUDGE                 
    freopen("input.txt", "r", stdin);                                              
    freopen("output.txt", "w", stdout);  
    freopen("error.txt", "w", stderr);                          
    #endif         
    ll test_cases=1;               
    cin>>test_cases; 
    while(test_cases--){
        solve();
    }
    cout<<fixed<<setprecision(10);
    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=1e5+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);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
ll n,neg=0,pos=0,a;
cin>>n;
for(int i=0;i<n;i++)
{
    cin>>a;
    if(a>0)
    pos++;
    else if(a<0)
    neg++;
}
cout<<(pos*pos-pos+neg*neg-neg)/2<<'\n';
return ;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int test=1;
    cin>>test;
    while(test--) sol();
}

mwolf · April 13, 2022, 7:49pm

why was I (and still am) getting WA for this C# solution which uses the same logic as explained
thank you in advance

int T = int.Parse(Console.ReadLine());
int posCnt, negCnt, temp1, temp2;

for (int t = 0; t < T; t++)
{
int N = int.Parse(Console.ReadLine());
int[] A = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
posCnt = 0;
negCnt = 0;

for (int i = 0; i < A.Length; i++)
{
    if (A[i] < 0)
        negCnt++;
    else if (A[i] > 0)
        posCnt++;
}

temp1 = negCnt * (negCnt - 1) / 2;
temp2 = posCnt * (posCnt - 1) / 2;
Console.WriteLine(temp1 + temp2);

}

m123456789i · April 14, 2022, 2:23am

There is an integer overflow for temp1 and temp2.
You have initialised temp1 and temp2 as int, they can be more than that in this case.
max value of posCnt = 10^5
and temp1 = (posCnt*(posCnt-1))/2 which can be approx temp1 = 10^5 * 10^5
temp1 = 10^10, which is more than int can hold, the same goes for negCnt and temp2.
Just initialise the value of temp1 and temp2 as long.

yashdew · April 14, 2022, 12:18pm

#include <bits/stdc++.h>
using namespace std;
void solve()
{
long long num;
cin>>num;

//vector<long long> array;

int pos=0,neg=0;
for(int i=0;i<num;i++){
    int temp;
    cin>>temp;
    if(temp < 0)
        neg++;
    
    else if(temp > 0)
        pos++;
    else
        continue;
}

long long count = neg*(neg-1) /2  + pos*(pos-1)/2 ;
cout<<count<<endl;

}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int testCases;
cin >> testCases;

while (testCases--)
{
        solve();
}

return 0;

}
what’s wrong in this solution?

yesshivam · April 14, 2022, 2:36pm

Why I am getting WA in task 3 and 4 ?
Please exaplain

#include <iostream>
using namespace std;
int sum(int n){
	return (n*(n-1)/2);
}
int main() {
	// your code goes here
	 int t ;
 cin>>t;
 while(t--){
 	int n;
 	cin>>n;
 	long int  a[n], neg = 0, p = 0;
 	for (int i = 0; i < n; i++)
 	{
 		cin>>a[i];
 		if(a[i]>0)p++;
 		else if(a[i]<0)neg++;
 	}
 	
 	cout<<sum(p)+sum(neg)<<endl;

 }
	return 0;
}

type or paste code here

rajpatel1729 · April 14, 2022, 2:36pm

What am I doing wrong here, can anyone tell please?

void solve(){
	// USE rep for implementing loop
	int n;
	cin >> n;
	int a;
	int pos = 0,neg=0;
	rep(i,0,n){
		cin >> a;
		if(a>0){
			pos++;
		}else if(a<0){
			neg++;
		}
	}
	

	cout<<(pos*(pos-1))/2 + (neg*(neg-1))/2<<"\n";
}

anubhav1112 · April 14, 2022, 2:36pm

I took the count of negative and positive as integer data type and was getting Wrong Answer. Then I changed the variable types to long in JAVA and it worked all fine. But why is that? Since Maximum array length is 2 * 10^5 , then I don’t think long is needed to store the counts of positive and negative numbers. Although long is needed to finally calculate the answer. Can you help me regarding this? I wasted a lot of time yesterday thinking that something is wrong with my logic.

anon14547936 · April 14, 2022, 2:36pm

#include <iostream>
using namespace std;

int main() {
	int t;
	cin >> t;
	while(t--){
	    int n,sum = 0,pos = 0,neg = 0;
	    cin >> n;
	    int * arr = new int[n];
	    for(int i = 0; i < n; i++){
	        cin >> arr[i];
	        if(arr[i] == 0){
	            continue;
	        }
	        else if(arr[i] < 0)
	        neg++;
	        else
	        pos++;
	    }
	    
	    for(int i = 0; i < n; i++){
	        if(arr[i] == 0){
	            continue;
	        }
	        else if(arr[i] > 0){
	            pos--;
	            sum = sum + pos;
	        }
	        else{
	            neg--;
	            sum = sum + neg;
	        }
	    }
	    
	    cout << sum << endl;
	}
	return 0;
}

can anybody tell me how this code fails last 2 cases??

amiytiwari_adm · April 15, 2022, 5:27pm

Hey @anon14547936
There is the problem of integer overflow in your code as max value of n is 10^5 which will form max pair about 10^10. try using long long in your code instead of int.

amiytiwari_adm · April 15, 2022, 5:30pm

Hey @anubhav1112
While multiply of two int datatype value and assigning it to a long datatype value still has a integer multiplication and cause overflow until you do not change it to long multiplication.

amiytiwari_adm · April 15, 2022, 5:34pm

Hey @rajpatel1729
Datatype of your variable (pos,neg) is int which on multiplication cause integer overflow as max vaalue of n is 10^5 which on multiply reaches 10^10 which is out of integer datatype limit, try using long long datatype.

amiytiwari_adm · April 15, 2022, 5:38pm

Hey @yesshivam
Return type of your sum function is int which is to long long.

amiytiwari_adm · April 15, 2022, 5:41pm

Hey @yashdew
While multiply of two int datatype value and assigning it to a long datatype value still has a integer multiplication and cause integer overflow until you do not change it to long multiplication add ‘1ll*’ in the begin of your multiplication.

rajpatel1729 · April 15, 2022, 6:14pm

Thanks @amiytiwari_adm ,
I didn’t noticed this mistake,but then editorial’s solution should also be corrected,it also has pos and neg in int datatype.

anubhav1112 · April 16, 2022, 3:17am

Thank you Man! I got it now. Better to typecast all the ints to long or take long as data type beforehand just to be safe.