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
}
@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;
}
Thanks buddy for help. But still i can’t find mistake in my previous solution. Pls tell me error in that code. It was accepted in subcase 1 i.e n<1000 , but showing wrong error in other subcase.
Remember that N can be as large as 2\times10^5. So, N \times N can be as big as 4\times 10^{10}.
Now the result of any arithmetic operation is automatically typecasted to the highest data types of operands.
So, in your code(quoted above), the RHS of the assignment operator = will be typecasted to int.
This means, for larger values of N, N\times N will overflow for int (basically becomes negative most of the time). When you assign the same to the total variable, total will have an unexpected value instead of N\times N.
To correct this, declare N as long long int and even the array c[] as long long int, try executing.
Easy observation.
The AM-GM inequality says that \dfrac{x+y}{2} \ge \sqrt{xy}. The equality holds if and only if x=y.
Re-arrange the given condition as A_i^2+A_j^2\gt2A_iA_j (All A_i's are positive so we can multiply them in the inequality without reversing it’s direction). This is the same as the AM-GM inequality applied on A_i^2 and A_j^2 except that it is strictly greater. So we just need to count pairs (i, j) such that A_i \ne A_j.
Thanks buddy for your help.
On declaring array c[ ] as long long it is showing SIGSEGV error i.e. segmentation error and if we declare only N as long long , then it is showing wrong answer.
. Now it works fine after using vector instead of array.