What was the method to solve it without TLE??
I knew we had to pair odd and even numbers but For pairing I used O(n^2) approach.
1 Like
#define loop(i,s,e) for(i=s;i<e;i++)
#define in(x) cin>>x
#define out(x) cout<<x
#include
#include <math.h>
#include <limits.h>
#include
using namespace std;
int main() {
// your code goes here
//freopen(“input.txt”, “rt”, stdin);
ios_base::sync_with_stdio(true); cin.tie(0); cout.tie(0);
long long int t,n,x,y,k,i,sum;
in(t);
long long int q;
long long int sum1=0,sum2=0,cnt1=0,cnt2=0;
long long int max2;
while(t–)
{sum1=0;
sum2=0;
cnt1=0;
cnt2=0;
cin>>n;
long long int a[n],b[n];
loop(i,0,n)
{
cin>>a[i];
if(a[i]%2==1)
{cnt1+=1;
}
sum1=sum1+a[i];
}
loop(i,0,n)
{
cin>>b[i];
if(b[i]%2==1)
{cnt2+=1;
}
sum2=sum2+b[i];
}
max2=abs(cnt1-cnt2);
sum=((sum1+sum2-max2)/2);
cout<<sum<<"\n";
}
return 0;
}
1 Like
Store even and odd number in separate array for both A and B and sort them in descending order . Let say EA and OA for Array A and EB and OB for array B. Now add EA and EB elements till min size of both array . Do Same thing for Odd array . Then pair the remaining elements from both arrays
2 Likes
Got it Thanks . 
Yes,thats right we first need to pair odd and odd.
Then pair even and even and atlast pair left ones.
So, what i did was to store odd of 1st array a[]->in odda[], 2nd array b[]->in oddb[].
same to store even of 1st array a[]-> in evena[], 2nd array b[]->in evenb[].
Than to do pairing in O(n) time.
You can maintain four pointers set at 1st element.
Then iterate it over odd of both till size of one of the odd arrays of any becomes zero.
Same for even ones.
Now just iterate the left elements which are not paired.
It could be either in ( odda and evenb ) || (evena and oddb)
As we have already the pointers pointing the non-paired elements.
We could just iterate it over.
Here is my solution, you will get the idea clear of what i am saying.
https://www.codechef.com/viewsolution/24990041