spoj IITKWPCO

simple

#1

question link: here

My code:

      #include <bits/stdc++.h>
      #include <iostream>
      #define rep(i,n) for(int i=0;i<n;++i)
      using namespace std;
     int a[2000010],ar[105];
     int main()
   {
     int t,n,x,ans;
     cin>>t;
     while(t--)
   {
	    memset(a,0,sizeof a);ans=0;
	    cin>>n;
	    rep(i,n) 
	    {
		  cin>>x;
		  a[x]++;
		  ar*=x;
	    }
	    sort(ar,ar+n);//without this line solution is wrong.why??
	    rep(i,n) if(a[ar**2]>0&&a[ar*]>0) {++ans;a[ar**2]--;a[ar*]--;}
	    cout<<ans<<"

";
}

        return 0;

   }

I think there is no need to sort the array ar[].But it is needed why??
 Please help anyone ???

#2

In this problem, we need to maximize the number of pairs of integers such that ar* and 2ar both are present in the array.

Suppose array ar[] contains {4,8,16,2}. If it is unsorted, then your code is making a pair of 4 and 8 ie {4,8} and there are no more pairs now that follow the given condition. Hence your output is 1 (which is non optimal and can be improved by sorting).


If the arrray is sorted, it becomes {2,4,8,16} and your code makes 2 pairs ie {2,4} and {8,16}. Your output is 2 (maximal) and you get AC.


#3

Thanks a lot!!!