Help me in solving ALT problem

help
,
1

My issue

I sorted even numbers and then odd numbers. Now, I started taking combinations of left half of sorted even/odd and right half of sorted even/odd. Why am I getting wrong answer. Can anyone please help!!

‘o’ represents odd array and ‘e’ represents even array in my code.

My code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define vii vector<vector<int>>

int main() {
	int t;cin>>t;
	while(t--){
	    vector<int> e,o;
	    int n; cin>>n;
	    for(int i=0;i<n;i++){
	        int x; cin>>x;
	        if(x%2!=0){
	            o.push_back(x);
	        }else{
	            e.push_back(x);
	        }
	    }
	    if(n%2!=0){
	        cout<<-1<<' '<<'\n';
	    }else if(o.size()%2!=0){
	        cout<<-1<<' '<<'\n';
	    }else{
	        sort(e.begin(),e.end());
	        sort(o.begin(),o.end());
	        int y = e.size();
	        for(int i=0;i<y/2;i++){
	            cout<<(e[y/2-i-1]+e[y-i-1])/2<<' ';
	            cout<<(e[y-i-1]-e[y/2-i-1])/2<<' ';
	        }
	        y = o.size();
	        for(int i=0;i<y/2;i++){
	            cout<<(o[y/2-i-1]+o[y-i-1])/2<<' ';
	            cout<<(o[y-i-1]-o[y/2-i-1])/2<<' ';
	        }
	        cout<<'\n';
	    }
	    
	}
	return 0;
}

Problem Link: Alter Ego Practice Coding Problem - CodeChef

2

Hey you are simply printing every pair of numbers you are getting… you are not supposed to do that… read the question carefully the numbers picked from array A to form the array B are Ai and Ai+n/2 so you need to create a new array for the answer and store the pairs you get in the similar format as well…

	int j = 0;

	for(int i = 0 ; i < es/2 ; i++){
		ans[j+(n/2)] = (even[es-i-1] - even[i])/2;
		ans[j] = even[es-i-1] - ans[j+(n/2)];
		j++;
	}
	for(int i = 0 ; i < os/2 ; i++){
		ans[j+(n/2)] = (odd[os-i-1] - odd[i])/2;
		ans[j] = odd[os-i-1] - ans[j+(n/2)];
		j++;
	}
	
	f(i,0,n){
		cout << ans[i] << " ";
	}
	cout << endl;

check this code snippet and let me know if you need any help.

3

Bro, I am not simply printing them, I did the operations required in else part. See the else part of the code.
sort(e.begin(),e.end());
sort(o.begin(),o.end());
int y = e.size();
for(int i=0;i<y/2;i++){
cout<<(e[y/2-i-1]+e[y-i-1])/2<<’ ‘;
cout<<(e[y-i-1]-e[y/2-i-1])/2<<’ ‘;
}
y = o.size();
for(int i=0;i<y/2;i++){
cout<<(o[y/2-i-1]+o[y-i-1])/2<<’ ‘;
cout<<(o[y-i-1]-o[y/2-i-1])/2<<’ ‘;
}
cout<<’\n’;

4

i did not mean your pairs formed (logic) are incorrect… they have to printed in a certain order and in order to do so we use another array (ans here) to store them in the correct order, one of the number from the pair at Ai then another one at
Ai + n/2 and then print the entire array

5

Oh I see, Thanks bro, I thought that as we are shuffling at the end, we can print in any order. I got it now!!

Thanks a lot :slight_smile:

1 Like