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 
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
Nope. Your solution is logically correct. You are adding to the answer, the number of pairs that are possible with A[i] for each i \isin [1, N].
1 Like
Thanks.
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.
Can we consider our solution better if it takes less execution time ( The one shown when the solution gets accepted ). Mineās took 0.24
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.
Declare the array globally, or use CPP vector.
Use vector instead of array then it will not show SIGSETV error.
Thank u very much buddy for your help 
. Now it works fine after using vector instead of array.
Thanks
#include <bits/stdc++.h>
#define int long long
using namespace std;
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(tā){
int n;
cin>>n;
int a[n];
int total=n*(n-1);
int same=0;
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
for(int i=0,j=1;i<n,j<n;i++,j++){
if(a[i]==a[j]){
same++;
}
}
int result=total-2*same;
cout<<result<<"\n";
}
return 0;}
can someone tell me where my code is wrong???
@cherry0697 @monogon
Can you please help me in figuring out this code?!
https://www.codechef.com/viewsolution/49456434
It gives AC in TC 1 & WA in TC 2!