Author: S Manuj Nanthan
Tester: Anshu Garg
Editorialist: Istvan Nagy

SIMPLE

# PREREQUISITES:

Parity, Telescoping series

# PROBLEM:

An array is called lovely if the sum of absolute differences of each adjacent pair of elements is odd; formally, the array S of size m is lovely if \sum_{i=1}^{m-1} |S_i-S_{i+1}| is odd.

You are given an array A of N integers. You need to reorder the array in any manner such that the array becomes lovely. If there is no reordering operation that makes the array lovely, output -1.

# QUICK EXPLANATION

• |S_i-S_{i+1}| is odd if and only if S_i and S_{i+1} parity are different.
• we need exactly odd number of such adjacent pairs
• we can just have exactly one adjacent even-odd or odd-even pair by considering all the even elements and odd elements first

# EXPLANATION

Because of the parity of a value is the same as its absolute value parity, we can get rid off the absolute sign.

Parity\left( \sum_{i=1}^{N}|S_i-S_{i+1}|\right)=Parity\left(\sum_{i=1}^{N}(S_i-S_{i+1})\right)=\\Parity\left(S_1-S_2+S_2-S_3+...+S_{N-2}-S_{N-1}+S_{N-1}-S_N\right)=\\=Parity\left(S_1-S_N\right).

S_1-S_N is odd when S_1 and S_N has different parity. So we can order the array if and only if when not all the values have the same parity.

# TIME COMPLEXITY:

O(N) per test case

# SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
#define ll int
using namespace std;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--){

int n,m,x,i,j,k;
cin>>n;
vector<int> arr;        //Input array - arr
for(i=0;i<n;++i){
cin>>x;
arr.push_back(x);
}
m=0;
for(i=0;i<n;++i){
if(arr[i]%2)++m;        // Counting whether the element is of odd parity
}
if(m==0 || m==n) {          // Note that if all elements are of same parity , then the differences are always even!
cout<<-1<<"\n";
continue;
}
for(i=0;i<n;++i){
if(arr[i]%2) cout<<arr[i]<<" ";             //Print all the odd elements first
}
for(i=0;i<n;++i){
if(arr[i]%2==0) cout<<arr[i]<<" ";          // Print all the even elements , this ensures there is only 1 adjacent pair where the parity becomes odd
}
cout<<"\n";                                 /* You can also print all even elements first and all the odd ones next,
Other solutions are there but not needed for this simple one! */
}
}

Tester's Solution
#include<bits/stdc++.h>
using namespace std ;

#define ll              long long
#define pb              push_back
#define all(v)          v.begin(),v.end()
#define sz(a)           (ll)a.size()
#define F               first
#define S               second
#define INF             2000000000000000000
#define popcount(x)     __builtin_popcountll(x)
#define pll             pair<ll,ll>
#define pii             pair<int,int>
#define ld              long double

const int M = 1000000007;
const int MM = 998244353;

template<typename T, typename U> static inline void amin(T &x, U y){ if(y<x) x=y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x<y) x=y; }

#ifdef LOCAL
#define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 2351
#endif

long long readInt(long long l,long long r,char end){
long long x = 0;
int cnt = 0;
int first =-1;
bool is_neg = false;
while(true) {
char g = getchar();
if(g == '-') {
assert(first == -1);
is_neg = true;
continue;
}
if('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if(cnt == 0) {
first = g - '0';
}
++cnt;
assert(first != 0 || cnt == 1);
assert(first != 0 || is_neg == false);

assert(!(cnt > 19 || (cnt == 19 && first > 1)));
}
else if(g == end) {
if(is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
assert(false);
}
}
}
string ret = "";
int cnt = 0;
while(true) {
char g = getchar();
assert(g != -1);
if(g == end) {
break;
}
++cnt;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}

int _runtimeTerror_()
{
int N;
// cin >> N;
vector<int> A(N);
int odd = 0, even = 0;
for(int i=0;i<N;++i) {
if(i < N - 1) {
}
else {
}
odd += A[i] & 1;
even += (A[i] % 2 == 0);
}
if(!odd || !even) {
cout << "-1\n";
return 0;
}
sort(all(A),[&](int i,int j) {
return i % 2 < j % 2;
});
for(int i:A) {
cout << i << " ";
}
cout << "\n";
return 0;
}

int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef runSieve
sieve();
#endif
#ifdef NCR
initialize();
#endif
// cin >> TESTS;
while(TESTS--)
_runtimeTerror_();
// assert(getchar() == -1);
return 0;
}

Editorialist's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

int main(int argc, char** argv)
{
int T, N;
cin >> T;
forn(tc, T)
{
cin >> N;
vector<int> A(N);
for (auto& ai : A)
{
cin >> ai;
}
sort(all(A), [](const int a, const int b) {return (a & 1) < (b & 1); });
if ((A[0] & 1) == (A.back() & 1))
{
cout << "-1\n";
continue;
}
for (const auto& ai : A)
{
cout << ai << " ";
}
cout << endl;
}
return 0;
}


If you have other approaches or solutions, let’s discuss in comments.

3 Likes

Guys, can anybody tell me whats wrong with this code - Solution: 51333654 | CodeChef

What’s wrong in my approch or code?
https://www.codechef.com/viewsolution/51337492

Can anybody tell me what is wrong with my code?
Approach : I made two vectors, one in which contains all the even numbers and other contains odd. I take alternate even and odd numbers depending on the size of the even/odd filled vector. Since the value of even and odd is always odd, and their summation is odd if the total numbers are odd.

#include <bits/stdc++.h>

#define for0(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define forc(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i)
#define forr0(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define forr1(i, n) for (int i = (int)(n); i >= 1; --i)

using namespace std;

#define pb push_back
#define pob pop_back
#define fi first
#define se second

typedef vector vi;
typedef vector vvi;
typedef pair<int, int> ii;
typedef vector vii;
typedef long long ll;
typedef vector vll;
typedef vector vvll;
typedef double ld;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.precision(10);
cout << fixed;
int t;
cin>>t;
while(t–) {
int n;
cin>>n;
int arr[n];
for0(i,n) cin>>arr[i];
vi v1;
vi v2;
for0(i,n) {
if(arr[i]%2==0) v1.pb(arr[i]);
else v2.pb(arr[i]);
}
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
int a=v1.size();
int b=v2.size();
if(abs(a-b)<=1) {
if(a>b) {
for(int i=0; i<a; i++) {
cout<<v1[i]<<" “;
cout<<v2[i]<<” “;
}
}
else {
for(int i=0; i<b; i++) {
cout<<v2[i]<<” “;
cout<<v1[i]<<” “;
}
}
}
else {
cout<<”-1";
}
cout<<endl;

}
return 0;


}

First, enclose your code in  ticks
Like this

this is a sample code


1>there is no need of sorting
2>you are Wrong here ----> f(abs(a-b)<=1)

What if 1 1 ??? the answer will be -1 but yr code will print 1 1

3>You have written a lot of unnecessary code

4>Tip 1 >Please write -1/false cases at the top

4>Tip 2> Think in terms of ODD-EVEN= ODD .All possible combinations of a+b and a-b like this .

Final conclusion >>print all odd and even together

If I have written the same logic ,go through my code ,I have written it in the simplest form .

typedef long long ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

ll t;
cin>>t;
while(t--)
{

ll n;cin>>n;
vector<ll>arr;
vector<ll>ans;
vector<ll>odd;
vector<ll>even;
ll x;
for(int i=0;i<n;i++)
{
cin>>x;
arr.push_back(x);
if(x%2==0)
{
even.push_back(x);
}
else
{
odd.push_back(x);
}
}
if(even.size()==0 || odd.size()==0)
{
cout<<-1;
}
else
{
for(auto it:even)
{
ans.push_back(it);
}
for(auto it:odd)
{
ans.push_back(it);
}

for(auto it:ans)
{
cout<<it<<" ";
}
}
cout<<"\n";

}

}

//Here it fails
1
5
1 2 1 2 1

1> Bro simply print all even and all odd together .

My c++ Sumbission >>Solution: 51344677 | CodeChef
Or see it here

typedef long long ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

ll t;
cin>>t;
while(t--)
{

ll n;cin>>n;
vector<ll>arr;
vector<ll>ans;
vector<ll>odd;
vector<ll>even;
ll x;
for(int i=0;i<n;i++)
{
cin>>x;
arr.push_back(x);
if(x%2==0)
{
even.push_back(x);
}
else
{
odd.push_back(x);
}
}
if(even.size()==0 || odd.size()==0)
{
cout<<-1;
}
else
{
for(auto it:even)
{
ans.push_back(it);
}
for(auto it:odd)
{
ans.push_back(it);
}

for(auto it:ans)
{
cout<<it<<" ";
}
}
cout<<"\n";

}

}

// here it fails answer will not be -1
1
4
2 2 2 1

Bhai simply print all even and odd numbers together
Use property of ODD - EVEN = ODD .

Do observation on a copy
Like ODD-ODD = ?
EVEN -EVEN = ?

ODD+ODD =?
EVEN + EVEN =?

finally Answer idea would be that ODD -EVEN = ODD so simply print all even and odd together

Like —
ODD ODD ODD EVEN EVEN EVEN
OR
EVEN EVEN EVEN ODD ODD ODD

My C++ solution

typedef long long ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

ll t;
cin>>t;
while(t--)
{

ll n;cin>>n;
vector<ll>arr;
vector<ll>ans;
vector<ll>odd;
vector<ll>even;
ll x;
for(int i=0;i<n;i++)
{
cin>>x;
arr.push_back(x);
if(x%2==0)
{
even.push_back(x);
}
else
{
odd.push_back(x);
}
}
if(even.size()==0 || odd.size()==0)
{
cout<<-1;
}
else
{
for(auto it:even)
{
ans.push_back(it);
}
for(auto it:odd)
{
ans.push_back(it);
}

for(auto it:ans)
{
cout<<it<<" ";
}
}
cout<<"\n";

}

}


This is my approch but I’m still having a WA. SOS

1. Separte the numbers as per odd or even.
2. And as we know odd-even always yields odd and hence we follow the pattern
3. So The decision point is if abs(Odd.size() - Even.size()) must be either 0 or 1
4. Corner case is if we have n = 1 then also the answer must be -1.
// Don't Just copy the code, Understand it first.
// -- theskyspace(Insta profile also) ;)

#include <bits/stdc++.h>
using namespace std;
#define deb(x) cout << #x << " = " << x << endl;
#define deb2(x,y) cout << #x << " = " << x << " , " << #y << " = " << y << endl;
typedef long long ll;
typedef pair<int , int> pairs;
ll M = 10e8 + 7;

void solve(){
// Let's start
int n;
cin >> n;
vector<int64_t> E;
vector<int64_t> O;

if(n == 1){
cout << -1 << endl;
return;
}

for (int i = 0; i < n; i++)
{
int64_t a;
cin >> a;
if(a&1){
O.push_back(a);
}else{
E.push_back(a);
}
}

int temp = O.size() - E.size();

if((abs(temp) == 0) || (n%2 == 1 && abs(temp) == 1)){
for (int i = 0; i < max(O.size(),E.size()); i++)
{
// deb2(i,max(O.size(),E.size()))
if(O.size() >= E.size()){
if(i != O.size()){
cout << O[i] << " ";
}
if(i != E.size()){
cout << E[i] << " ";
}
}else{
if(i != E.size()){
cout << E[i] << " ";
}
if(i != O.size()){
cout << O[i] << " ";
}
}
}
cout << endl;
}else{
cout << -1 << endl;
}

}

//Driver's code
int main(){
// Stdin and stdout.
ios::sync_with_stdio(false);
cin.tie(0);

#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif

int t;
cin >> t;
while(t--){
solve();
}

return 0;
}


Sorry Bro!! But your this assumption is false.
Here is the proof

Testcase:
Input:
1
6
2 1 4 3 5 7

Required Output:
2 4 1 3 5 7

-1


There is no need to sort the array and because you have applied sorting the time complexity is of O(NlogN). One can simply print all odd numbers then all even numbers.
If number of even numbers is 0 or number of odd numbers is zero then there is no answer, so simply print -1 in that case.

1 Like

https://www.codechef.com/viewsolution/51320952
can anybody explain what is wrong with my solution…

1.Abs(a-b)<=1 is not a valid condition.
2. In the for loop, when using i<a,the index could get out of range for v2[i] and same goes for following for loop.

A better approach would be this just check when difference becomes odd and then just swap first element of sorted array with the other element which gives odd difference.
This passed all test cases:

#include<bits/stdc++.h>
using namespace std;

#define  endl       '\n'
#define  ll         long long
#define  forn(i,n)  for(ll i = 0; i < n; i++)
#define  vi         vector<int>
#define  vll        vector<long long>
#define  mod        1e9+7
#define  fast       ios_base::sync_with_stdio(0); cin.tie(0);  cout.tie(0);
#define  yup        cout<<"YES"<<endl;
#define  np         cout<<"NO"<<endl;
//for printing particular number of decimal digits.
#define  prdec(x)   cout<<fixed<<setprecision(10)<<x<<endl;
#define  w(t)       ll t; cin>>t; while(t--)

int main(){
fast
w(t){
ll n;cin>>n;
vll v(n+1);
for(int i=1;i<=n;i++){
cin>>v[i];
}
sort(v.begin(),v.end());
ll idx=0;
for(int i=n;i>=1;i--){
ll dif=abs(v[1]-v[i]);
if(dif%2==1){
idx=i;break;
}
}
if(idx!=0){
swap(v[n],v[idx]);
for(int i=1;i<=n;i++){cout<<v[i]<<" ";}
cout<<endl;
}
else{cout<<-1<<endl;}
}
return 0;
}


//Check this >>>answer will not be -1
1
4
1 1 1 2

Thanks for the reply ayush. This was such a stupid doubt on my part.

1 Like

Thanks man!

1 Like

I don’t understand why people are using sorting in the first question. Its just a simple mathematical property we need to know that odd - odd = even , even - even = even and even - odd = odd. If you see this then simply first print all odd numbers then all even numbers or you can also do vice versa. There are only two cases where answer will be -1 and that are when all numbers are either even or all are odd. Why to take n==1 case when constraints clear say that n>=2.

can anyone please tell me whats wrong with this
i m getting SIGABRT
#include<bits/stdc++.h>

using namespace std;

int main(){

ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int t;
cin>>t;
while(t--){
int n;
cin>>n;
int a[n];
vector<int>ans(n);
int o=0,e=1;
for(int i=0;i<n;i++) {cin>>a[i];
if(a[i]%2==0){ans[e]=a[i];e+=2;}
else{ans[o]=a[i];o+=2;}}

int sum=0;
for(int i=0;i<n-1;i++){
sum+=abs(ans[i]-ans[i+1]);
}
if(sum%2==0)cout<<"-1"<<endl;
else {
for(auto it:ans){
cout<<it<<" ";}cout<<endl;
}

}

return 0;

}`

What if the sum of absolute difference of given array is odd ?

Then directly print the array , no need to do anything , this was not mentioned in the question which actually caused a bit of confusion but I assumed it and it worked .

If it was mentioned that we have to make the array lovely if it was initially lovely then the final answer should be different from the initial array and you would have to generate some other possible odd combination .