BUTYPAIR - Editorial

PROBLEM LINK:

Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1

Author: Souradeep
Tester : Riley Borgard
Editorialist: Aman Dwivedi

DIFFICULTY:

Simple

PREREQUISITES:

Observation

PROBLEM:

Given a sequence A_1, A_2, \ldots, A_N. An ordered pair of indices (i,j) in this sequence is called a beautiful pair if i \neq j and \frac{A_i - A_j}{A_i} \lt \frac{A_i - A_j}{A_j}. (Here division represents real division)

Find the number of beautiful pairs present in the given sequence.

EXPLANATION:

Subtask 1:

As the value of N is quite small which allows us to consider every ordered pair of indices (i, j) of the given sequence.

Therefore we can easily find the number of pairs that are beautiful.

Time Complexity

O(N^2) per test case

Solution
// Subtask 1

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

void solve()
{
	int n;
	cin>>n;

	double a[n];

	for(int i=0;i<n;i++)
		cin>>a[i];

	int ans = 0;

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

			int temp = a[i]-a[j];
			if(temp/a[i]<temp/a[j])
				ans++;
		}
	}

	cout<<ans<<"\n";
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
  // freopen("input.txt","r",stdin);
  // freopen("output.txt","w",stdout);

  int t;
  cin>>t;

  while(t--)
    solve();

return 0;
}

Subtask 2:

Since the value of N is large enough to not allow us to check all the ordered pairs. We can optimize with some basic observations and calculations.

Let’s say we have an ordered pair of indices (i, j) whose values are A_i and A_j. Now according to the values of A_i and A_j, there are three cases possible:

Case 1

A_i \gt A_j

When A_i \gt A_j, then the value of A_i - A_j will be positive. Let’s call this value X. We have,

A_i \gt A_j

Multiplying X on both sides we get:

A_i * X \gt A_j*X
\frac{X}{A_j} \gt \frac{X}{A_i}

Finally substituting the values of X, we get:

\frac{A_i-A_j}{A_i} \lt \frac{A_i-A_j}{A_j}

That means all such pairs where A_i \gt A_j are beautiful pairs.

Case 2

A_i \lt A_j

When A_i \lt A_j, then the value of A_i - A_j will be negative. Let’s call this value X. We have,

A_i \lt A_j

Multiplying X on both sides we get:

A_i * X \gt A_j*X
\frac{X}{A_j} \gt \frac{X}{A_i}

Finally substituting the values of X, we get:

\frac{A_i-A_j}{A_i} \lt \frac{A_i-A_j}{A_j}

That means all such pairs where A_i \lt A_j are also beautiful pairs.

Case 3

A_i = A_j

When A_i = A_j, then the value of A_i - A_j will be zero. Hence

\frac{A_i-A_j}{A_i} = 0
\frac{A_i-A_j}{A_j} = 0

Therefore the condition of \frac{A_i-A_j}{A_i} \lt \frac{A_i-A_j}{A_j} doesn’t hold. Hence we say that such pairs where A_i = A_j , those pairs are not beautiful.

From the above cases, we can say that the pair is not beautiful when A_i = A_j. Therefore we can maintain a frequency array that stores the count of each element in the given array, Finally, when we are at index i we can simply add (N-freq[A_i]) in our answer, where freq[A_i] tells the occurrences of A_i in an array.

TIME COMPLEXITY:

O(N) per test case.

SOLUTIONS:

Author
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
	    Scanner sc=new Scanner(System.in);
	   // BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	    int t=1;
	    t=sc.nextInt();
	    //int t=Integer.parseInt(br.readLine());
	    while(--t>=0){
	        int n=sc.nextInt();
	        int a[]=new int[n];
	        int pre[]=new int[1000001];
	        for(int i=0;i<n;i++){
	            a[i]=sc.nextInt();
	            pre[a[i]]++;
	        }
	        long sum=0;
	        for(int i=0;i<n;i++){
	            sum=sum+(n-pre[a[i]]);
	        }
	     
	        System.out.println(sum);
	    }
	    
	}
}
Tester

#include <bits/stdc++.h>

#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

void solve() {
    int n;
    cin >> n;
    map<ll, int> ma;
    rep(i, 0, n) {
        ll a;
        cin >> a;
        ma[a]++;
    }
    ll ans = 1LL * n * (n - 1);
    for(auto &pa : ma) {
        ans -= 1LL * pa.second * (pa.second - 1);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int te;
    cin >> te;
    while(te--) solve();
}
Editorialist
// Subtask 2

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

#define int long long

void solve()
{
	int n;
	cin>>n;

	int a[n];

	for(int i=0;i<n;i++)
		cin>>a[i];

	int ans = 0;
	map <int,int> m1;

	for(int i=0;i<n;i++)
		m1[a[i]]++;

	for(int i=0;i<n;i++)
		ans+=(n-m1[a[i]]);

	cout<<ans<<"\n";
}

int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
  // freopen("input.txt","r",stdin);
  // freopen("output.txt","w",stdout);

  int t;
  cin>>t;

  while(t--)
    solve();

return 0;
}

2 Likes

my solution using MAP STL
->if we take a example array 2 1 3 4 5 6 here the answer will be equal to 30 because all elements are unique and each can form a pair with other elements in the array which would be (10(5 for indexs 1,2 1,3 1,4 1,5 1,6 and other 5 for the mirror images of these indices)+8+6+4+2) if we have duplicate elements then using map we can solve the problem first we store max operations possible then for duplicate element till the count of the ith element becomes 1 we keep on reducing 2 (pair and its mirror)

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
void solve(){
    lli n;
    cin>>n;
    lli a[n+1];
    map<lli,lli> m;
    for(lli i=0;i<n;i++){
        cin>>a[i];
        m[a[i]]++;
    }
    lli operations = 0;
    for(lli i=0;i<n;i++){
        operations += (n-(i+1))*2;
    }
    for(auto &itr : m){
        auto cnt = itr.second;
        if(cnt == 1){
            continue;
        }else{
            while(itr.second!=1){
                auto cnt = itr.second;
                itr.second-=1;
                operations -= ((cnt-1)*2);
            }            
        } 
    }
    cout<<operations<<endl;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

Are you posting the solution for the other’s help, then please format the code and put that into link form or under the Spoilers. Currently it is not read-able and won’t benefit others.

IT is getting partially accepted , please anyone help

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

#define endl ‘\n’
const int mod=1000000007;

int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// your code goes here
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
long long int ans=0;
map<int,int> mp;
for(int i=0;i<n;i++)
{
mp[a[i]]++;
}

    ans=n*(n-1); // calculate total no. of possible pair from all using 2*(nC2)
  //map for counting freqquency
    for(auto it:mp)
    {
        if(it.second>1)
        {
            
            long long int temp= it.second*(it.second-1); // pair from count>1 2*(countC2)
            ans=ans-temp;   // subtracting inalid pairs
           
        }
    }
    cout<<ans<<endl;
}

return 0;

}

2 Likes

Use long long int for vector,map and n test cases are huge

#include <iostream>

#include
using namespace std;

int main() {
// your code goes here
int t;cin>>t;

while(t--){
    map <int,int> hash;
    int n;cin>>n;
    
    for (int i=0;i<n;i++){
        int a;cin>>a;
        hash[a]++;
    }
    
    long long int out=0;
    
    for (auto it=hash.begin();it!=hash.end();it++){
        out+=it->second*(n-it->second);
    }
    cout<<out<<endl;
}
return 0;

}
Newbie here, I find my code almost same as the editorial one but still getting partially accepted please help

1 Like

I don’t know why I am getting WA verdict on Task 1 while my answers are correct for Task 2!! Solution : Solution: 49358596 | CodeChef

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

#define ll long long int

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t–){
int n;
cin>>n;
int arr[n];
int c[1000001]={0};
for(int i=0;i<n;i++){
cin>>arr[i];
c[arr[i]]++;
}
ll total = n*n;
int a=0;
for(int i=0;i<1000001;i++){
if(a>n){
break;
}
total-=(c[i]*c[i]);
a=a+c[i];
}
cout<<total<<endl;
}
return 0;
}

pls tell mistake in my code. It is accepted in subcase 1 but showing wrong answer in subcase 2.

Can someone please tell me why my code gives AC in 1st tc & WA in 2nd?

	import java.util.*;
import java.io.*;
import java.math.*;

public class prac {

static class FastReader
 {
     BufferedReader br;
     StringTokenizer st;

     public FastReader()
     {
         br = new BufferedReader(new
                 InputStreamReader(System.in));
     }

     String next()
     {
         while (st == null || !st.hasMoreElements())
         {
             try
             {
                 st = new StringTokenizer(br.readLine());
             }
             catch (IOException  e)
             {
                 e.printStackTrace();
             }
         }
         return st.nextToken();
     }

     int nextInt()
     {
         return Integer.parseInt(next());
     }

     long nextLong()
     {
         return Long.parseLong(next());
     }

     double nextDouble()
     {
         return Double.parseDouble(next());
     }

     String nextLine()
     {
         String str = "";
         try
         {
             str = br.readLine();
         }
         catch (IOException e)
         {
             e.printStackTrace();
         }
         return str;
     }
 }
static class QuickSort {
    int array[];
    int length;

    public void sort(int[] inputArr) {
        
        if (inputArr == null || inputArr.length == 0) {
            return;
        }
        this.array = inputArr;
        length = inputArr.length;
        quickSort(0, length - 1);
    }
 
    public void quickSort(int lowerIndex, int higherIndex) {
         
        int i = lowerIndex;
        int j = higherIndex;
        // calculate pivot number, I am taking pivot as middle index number
        int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
        // Divide into two arrays
        while (i <= j) {
            /**
             * In each iteration, we will identify a number from left side which 
             * is greater then the pivot value, and also we will identify a number 
             * from right side which is less then the pivot value. Once the search 
             * is done, then we exchange both numbers.
             */
            while (array[i] < pivot) {
                i++;
            }
            while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                exchangeNumbers(i, j);
                //move index to next position on both sides
                i++;
                j--;
            }
        }
        // call quickSort() method recursively
        if (lowerIndex < j)
            quickSort(lowerIndex, j);
        if (i < higherIndex)
            quickSort(i, higherIndex);
    }
 
    private void exchangeNumbers(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}
public static void main(String[] args) {
	try {
	FastReader fr=new FastReader();
	int t=fr.nextInt();
	StringBuilder sb=new StringBuilder();
	QuickSort qs=new QuickSort();
	
	while(t-->0)
	{
		int n=fr.nextInt();
		int a[]=new int[n];
		for(int i=0;i<n;i++)
		a[i]=fr.nextInt();
		qs.sort(a);
		BigInteger sum=new BigInteger("0");
		sum=sum.add(BigInteger.valueOf(n));
		
		sum=sum.multiply(BigInteger.valueOf(n-1));

		int count=1;
		for(int i=0;i<n-1;i++)
		{
			if(a[i]==a[i+1])
				count++;
			else
			{
				if(count>1) {
					sum=sum.subtract(BigInteger.valueOf((count*(count-1))));
					count=1;
				}
			}
		}
		if(count>1)
			sum=sum.subtract(BigInteger.valueOf((count*(count-1))));
		
		sb.append(sum+"\n");
	}
	System.out.println(sb);
}
	catch(Exception e)
	{
		return;
	}
	}

}

@cherry0697 @monogon @souradeep_adm Please check my code and help me point out where it gets wrong.
It will be really very helpful of you.

Can my solution get hacked ?
I just calculate number of ordered pairs i, j such that A[i] < A[j]
Also, I am not including the whole code to make it small, as it contains a lot of macros and generic functions.

void solve() {
  int n;
  cin >> n;
  vi A(n);
  cin >> A;
  sort(all(A));
  ll ans = 0;
  f0(i, n) {
    ans += n - (UB(all(A), A[i]) - A.begin());
  }
  print(2 * ans);
}

Use map instead of hash array

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

int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cout.tie(NULL);
int t;
cin>>t;
while(t–)
{
ll n;
cin>>n;
vector v(n);
for(ll i=0;i<n;i++)
cin>>v[i];
ll ans=n*(n-1);
unordered_map<ll,ll> mp;
for(auto i:v)
mp[i]++;
for(auto i:mp)
{
if(i.second>=2)
{
ans-=(i.second*(i.second-1));
}
}
cout<<ans<<endl;
}
return 0;
}

my solution using fenwick tree [ counting inversion both from front and back ]
I have maintained the fenwick tree class so I have directly used that

 void go( )
   {
        int N ;
        cin>>N ;
        vector<int>A(N);

        for( auto &x : A )
            cin>>x ;

        auto B = A ;
        sort( B.begin() , B.end() );

        for( auto &x : A )
            x = lower_bound( B.begin() , B.end() , x ) - B.begin() ;

        


        FT_PR T(N) , T1(N); // fenwick tree point update and range query 

        int res = 0 ;

        for( int i = N-1 ; i >= 0 ; i-- )
        {
            res += T.sum( A[i]-1 );
            T.add( A[i] , 1 );
        }

        for( int i = 0 ; i < N ; i++ )
        {
            res += T1.sum( A[i]-1 );
            T1.add( A[i] , 1 );
        }

        cout<<2*res<<endl; // since it was ordered pair so we have to multiply by 2 
   }

Mine showed TLE on larger test cases using ordered map, had to use unordered map for that!

In Case 2
How A[i] becomes less than A[j] after multiplying with x…
Can anyone clarify my doubt?..

@sarfraj_123 The value of A[i]-A[j] is X which is negative as if we multiply the both side of an inequality with a negative integer the sign get reversed.

I just solved the given equation further and got the equation… -((ai-aj)^2)/ai*aj < 0; which is always true for every i and j but except for only those conditions where ai = aj wherein our value comes out to be zero which is not less than 0.so the question gets simply sorted to find the number of ways any two elements can be chosen from the array multiplied by 2 (as both i,j and j, i can be considered)- number of ways of picking any two similar elements multiplied by 2(which we will be doing after finding the frequency of all elements. here’s my solution.

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

int main()
{
int t;
cin >> t;
while (t–)
{
ll n;
cin >> n;
vector v(n);
for (ll i = 0; i < n; i++)
cin >> v[i];
ll N = 1e6 ;
ll k = n * (n - 1);
ll freq[N] = {0};
for (int i = 0; i < n; i++)
{
freq[v[i]]++;
}
ll abo = 0;
for (ll i = 0; i < N; i++)
{
ll m = freq[i];
if (m > 1)
k -= m * (m - 1);
}
cout << k << endl;
}
return 0;
}

Okay Thank you :blush:

Could someone please explain what’s wrong in my code?
it gives AC for the 1st subtask but WA for the 2nd one

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static class FastReader {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader()
        {
            br = new BufferedReader(
                new InputStreamReader(System.in));
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt() { return Integer.parseInt(next()); }
 
        long nextLong() { return Long.parseLong(next()); }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
 
	
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		try{
		    FastReader sc = new FastReader();
		    int tc=sc.nextInt();
		    while(tc-->=0){
		        int n=sc.nextInt();
		        int[] arr = new int[n];
		        
		        for(int i=0;i<n;i++)
		        arr[i]=sc.nextInt();
		        
		        Map<Integer, Integer> mp = new HashMap<>();
                // Traverse through array elements and
                // count frequencies
                for (int i = 0; i < n; i++)
                {
                    if (mp.containsKey(arr[i]))
                    mp.put(arr[i], mp.get(arr[i]) + 1);
                    else
                    mp.put(arr[i], 1);
                }
		        
		        long solve=0;
		        for (Map.Entry<Integer, Integer> entry : mp.entrySet()){
		            solve = solve + (entry.getValue() * (n-entry.getValue()));
		        }
		        
		        System.out.println(solve);
		    }
		}
		catch(Exception e){
		    
		}
	}
}

Really good explanation… better than watching video… good job