PROBLEM LINK:
Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1
Author: S Manuj Nanthan
Tester: Anshu Garg
Editorialist: Istvan Nagy
DIFFICULTY:
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 readString(int l,int r,char end){
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){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int _runtimeTerror_()
{
int N;
// cin >> N;
N = readIntLn(2,500);
vector<int> A(N);
int odd = 0, even = 0;
for(int i=0;i<N;++i) {
if(i < N - 1) {
A[i] = readIntSp(1,1e6);
}
else {
A[i] = readIntLn(1,1e6);
}
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
int TESTS = readIntLn(1,1000);
// 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.