PROSUM Practice(Easy)- getting wrong answer

general
1

Please help me. I don’t know what’s wrong with this!

int main()
{

int x;
long long int k;
scanf("%d",&x);
unsigned long long int n;
unsigned long long int count=0;
unsigned long long int total_combinations=0;
unsigned long long int one_combinations=0;
unsigned long long int two_combinations =0;
unsigned long long int one_count=0;
unsigned long long int two_count=0;
unsigned long long int other=0;

         while(x>0)
         {
 	         scanf("%lld",&n);
	         long long int a[n];
	         count=0;
	         one_count=0;
	         two_count=0;
	         other=0;


	for(k=0;k<n;k++)
	{
		scanf("%lld",&a[k]);
		if(a[k]==1)
		{
			one_count++;
		}
		else if(a[k]==2)
		{
			two_count++;
		}
		else
		{
			other++;
		}
	}

	total_combinations = (n * (n -1)) / 2;
	one_combinations = (one_count * (one_count - 1));
	one_combinations=one_combinations/2;
	two_combinations = (two_count * (two_count - 1)) ;
	two_combinations=two_combinations/2;
	k = one_count * (n - one_count);

	count = (total_combinations - one_combinations - two_combinations - k);

	 cout<<count<<endl;
        x--;
}

return 0;

}

2

the problem is you have forgotten the fact that a[i] can also be ‘0’.so you should also count the number of zeroes.and the major flaw in your algo is that you have only taken into the pair of indices in which ‘1’ combines with other '1’s.but the fact is that if a ‘1’ or ‘0’ occurs it can combine with all the other elements present in the array because if a[i]=1 or 0 then a[i]a[j] for any j will be a[i] or 0 which is in fact less than a[i]+a[j].hence the proper algorithm should be.
1)count the number of 0 and 1.let that count be a.
2)count the number of 2.let it be b.
now comput number of combinations of 0 and 1=(a(n-1))-((a*(a-1)/2);
now compute the number of 2 combinations=(b*(b-1))/2;
now ans =total combinations - (0 and 1 combinations)- ( 2 combinations);

1 Like
3

http://www.codechef.com/viewsolution/4174117.this is the link to the correct solution.

4

Thanks a lot. It worked.They mentioned that the number are non negative.so i did not consider 0.my bad!