BUTYPAIR - Editorial

editorial
, , ,
22

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
23

Thanks.

24

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.

25

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

26

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.

27

Can anyone tell me why am I getting RE (SIGSEGV) on subtask 2?
Solution: 49303931 | CodeChef

28

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.

29

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.

30

Declare the array globally, or use CPP vector.

31

Use vector instead of array then it will not show SIGSETV error.

32

Thank u very much buddy for your help :slight_smile: . Now it works fine after using vector instead of array.

33

Thanks

34

#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???

35

@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!