ADJLOVE - Editorial

[cherry0697]

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: S.Manuj Nanthan
Tester: Manan Grover
Editorialist: Aman Dwivedi

DIFFICULTY:

Easy

PREREQUISITES:

Maths

PROBLEM:

An array is called lovely if the sum of product of each adjacent pair of elements is odd.

More formally, the array S of size M is lovely if the value \sum_{i=1}^{M-1} (S_i . S_{i+1}) is odd.

You are given an array A consisting of N positive integers. Find a permutation of array A which is lovely.

If multiple such permutations are possible, output any. If there is no lovely permutation, output -1.

EXPLANATION:

Let’s try to see what happens under various cases, before that remember the three basic properties:

Even+Even = Even \\ Odd+Odd = Even \\ Odd+Even = Odd

and

Even * Even = Even \\ Odd*Odd = Odd \\ Even*Odd = Even

Now let’s look the cases we were talking about:

• Odd numbers are less than or equal to 1.

  Let’s see what happens when there is no odd number present. Hence in any permutation you arrange the array elements. The consecutive product is gonna be even for all the indexes look at the above property that even multiplied with even gives you an even number. And then the sum of all even numbers is going to be even.

  Now when there is only one odd element in the given array. Wherever you place this odd number it’s left side element and right side element is going to be even. And as we know even multiplied with odd gives you even number. Again the sum of all even numbers is going to be even.

  Hence we can conclude that in such cases it is never possible to achieve the odd sum in whatever permutation we arrange the given array.

• All numbers of the given array are odd.

  This is very interesting and simple case as all numbers are odd and hence when the odd number is multiplied with the odd number it produces an odd number. Hence every consecutive product is an odd number. Now the answer depends whether the sum of these consecutive product is even or odd.

  • N is Even

    There will be (N-1) consecutive products that exist for the the array of length N. Hence (N-1) is an odd number. If odd number is added odd times it produces an odd number.

  • N is Odd

    In this case (N-1) is going to be even. Hence when odd number is added even times it produces an even number.

  Hence we can conclude that in such cases whether the sum is going to be odd depends on whether N is even.

• All other cases

  Ok, so for all other cases it is always possible to produce an odd number. Let’s say the number of odd numbers in the given array be X. Now let us try to prove how:

  X is Odd

  Now we know that these numbers are the only chances for us to get the odd sum in the array. Now if we place all these numbers consecutively then there will be (X-1) consecutive odd products. Since (X-1) is even hence we will end up getting the sum as even.

  Let us then do one thing place the (X-1) odd numbers consecutively and the remaining odd number anywhere. Now there will be (X-2) odd consecutive products in the given array which leads us to get the odd sum.

  Hence we can say that it is possible to get the odd sum when X is going to be odd.

  X is Even

  Very simple if you read the Odd case above. Just place the all these X numbers consecutive and then you know what happens and you will be able to get the odd sum.

TIME COMPLEXITY:

O(N) per test case.

SOLUTIONS:

Author

for _ in range(int(input())):
	n=int(input())
	a=list(map(int,input().split()))
	odd=[]
	even=[]
	for i in a:
		if(i%2):
			odd.append(i)
		else:
			even.append(i)
	if(len(odd)<=1 or (len(odd)==n and n%2)):
		print(-1)
	else:
		if(len(odd)%2):
			print(odd.pop(),end=' ')
		print(*even,end=' ')
		print(*odd)

Tester

#include <bits/stdc++.h>
using namespace std;
long long readInt(long long l, long long r, char endd) {
    long long x = 0;
    int cnt = 0;
    int fi = -1;
    bool is_neg = false;
    while (true) {
        char g = getchar();
        if (g == '-') {
            assert(fi == -1);
            is_neg = true;
            continue;
        }
        if ('0' <= g && g <= '9') {
            x *= 10;
            x += g - '0';
            if (cnt == 0) {
                fi = g - '0';
            }
            cnt++;
            assert(fi != 0 || cnt == 1);
            assert(fi != 0 || is_neg == false);
 
            assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
        }
        else if (g == endd) {
            assert(cnt > 0);
            if (is_neg) {
                x = -x;
            }
            assert(l <= x && x <= r);
            return x;
        }
        else {
            assert(false);
        }
    }
}
int main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  #ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif
  int t;
  t = readInt(1, 1000, '\n');
  while(t--){
    int n;
    n = readInt(2, 500, '\n');
    int temp;
    vector<int> e, o;
    for(int i = 0; i < n; i++){
      if(i != n - 1){
        temp = readInt(1, 1000000, ' ');
      }else{
        temp = readInt(1, 1000000, '\n');
      }
      if(temp % 2){
        o.push_back(temp);
      }else{
        e.push_back(temp);
      }
    }
    if(o.size() == 0){
      cout<<-1<<"\n";
    }else{
      if(o.size() % 2 == 0){
        for(int i = 0; i < o.size(); i++){
          cout<<o[i]<<" ";
        }
        for(int i = 0; i < e.size(); i++){
          cout<<e[i]<<" ";
        }
        cout<<"\n";
      }else{
        if(e.size() == 0 || o.size() == 1){
          cout<<-1<<"\n";
        }else{
          cout<<o[0]<<" ";
          for(int i = 0; i < e.size(); i++){
            cout<<e[i]<<" ";
          }
          for(int i = 1; i < o.size(); i++){
            cout<<o[i]<<" ";
          }
          cout<<"\n";
        }
      }
    }
  }
  return 0;
}

Editorialist

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

void solve()
{
    int n;
    cin>>n;
    
    vector<int> even,odd;
    
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        
        if(x%2)
            odd.push_back(x);
        else 
            even.push_back(x);
    }
    
    if (odd.size()<=1 || (odd.size() == n && n%2))
    {
        cout<<-1<<endl;
        return;
    }
    
    if(odd.size()%2)
    {
        cout<<odd[0]<<" ";
        odd.erase(odd.begin());
    }
    
    for(auto itr: even)
        cout<<(itr)<<" ";
    
    for(auto itr: odd)
        cout<<(itr)<<" ";
        
    cout<<endl;
        
}

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

return 0;
}

[siddhant_rout]

Can someone check why this code is not passing all test cases?

void solve() {
    ll n;
    cin >> n;
    
    vll arr(n);
    cin >> arr;

    unordered_set<ll> odd, even;
    for(auto x: arr) {
        if(x % 2 == 0) {
            even.insert(x);
        }
        else {
            odd.insert(x);
        }
    }

    ll odd_pairs = floor(odd.size() / 2.0);
    ll even_pairs = floor(even.size() / 2.0);
    if(odd.size() % 2 != 0 && even.size() % 2 != 0) {
        even_pairs++;
    }
    else if(odd.size() % 2 != 0) {
        odd_pairs++;
    }
    else if(even.size() % 2 != 0) {
        even_pairs++;
    }

    if(odd_pairs % 2 == 0) {
        cout << -1 << endl;
        return;
    }

    for(auto x: odd) {
        cout << x << " ";
    }
    for(auto x: even) {
        cout << x << " ";
    }
    cout << endl;
}

[suman_18733097]

Consider this Input

1
7
8 6 4 6 7 3 10 

[rahul_siddhu]

//Why this code is not passing 2 test cases. Please tell
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n;cin>>n;
int arr[n];
int odd=0;
vector v;
for(int i=0; i<n ;i++){
cin>>arr[i];
if(arr[i]%2){
odd++;
v.push_back(arr[i]);
}
}
if(odd<=1 || (odd==n && odd%2)){
cout<<-1<<endl;
return;
}
for(int i=0; i<n; i++){
if(arr[i]%2==0)v.push_back(arr[i]);
}
if(odd%2==0){
for(int i=0; i<n; i++)cout<<v[i]<<" “;
cout<<endl;
}
else{
swap(v[0],v[n-1]);
for(int i=0; i<n; i++)cout<<v[i]<<” ";
cout<<endl;
}
}
int main() {
int t;cin>>t;
while(t–){
solve();
}
return 0;
}
//Why this code is not passing 2 test cases. Please tell

[anon77374810]

ans is 237.

[abhinav_hac1]

Can someone please help me and tell me about error in my code. Even after reading editorial i am not able to point it out .

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

int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int e=0,o=0;
vector arr(n);
vector odd;
vector even;


    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    
    for(int i=0;i<n;i++)
    {
        if(arr[i]%2==0)
        {
          e++;
          even.push_back(arr[i]);
        }
        else{
            o++;
            odd.push_back(arr[i]);
        }
    }
    
    if(o%2==0)
    {
        for(int it:odd)
        {
            cout<<it<<" ";
        }
         for(int i=0;i<even.size();i++)
            {
                cout<<even[i]<<" ";
            }
        cout<<"\n";
    }
    else if(o<=1)
    {
        cout<<-1<<"\n";
    }
    else{  //number of odd number is odd
        if(e>=1)
        {
            for(int i=0;i<odd.size()-1;i++)
            {
                cout<<odd[i]<<" ";
            }
            for(int i=0;i<even.size();i++)
            {
                cout<<even[i]<<" ";
            }
            cout<<odd[odd.size()-1]<<"\n";
        }
        else{
            cout<<-1<<"\n";
        }
    }
}
return 0;

}

[piyushchef]

Since we will get n-1 products and we have to sum these. Now if in these n-1 products, odds have occurred odd times then only the sum will be odd, so I will check for(int i = 1; i <= n - 1; i +=2) and if there are (i+1) odd numbers in the array then answer will be yes and I will print all odd first then all even.

What’s wrong with this approach? Please answer.

[anon67629683]

@cherry0697

else:
		if(len(odd)%2):
			print(odd.pop(),end=' ')
		print(*even,end=' ')
		print(*odd)

Can someone please explain me the working of this code (Author’s solution last 5 lines).

[anon73689555]

I am not understanding for which cases my code is failing. Can someone help me out?
My code: CodeChef: Practical coding for everyone

[anon73689555]

@cherry0697

		if(len(odd)%2):
			print(odd.pop(),end=' ')

Can someone please explain out this part? I tried for a long time but I am not getting any logic.

[chefsecond]

//
//  Adjacency Love.cpp
//  codechef 2
//
//  Created by Kunal Dutta on 22/03/22.
//

#define loop(n) for(int i=0; i<n; i++)
#define fast ios_base::sync_with_stdio(false); cin.tie(0);
using ll = long long;

#include <iostream>
using namespace std;
int main()
{
    fast
    ll t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin >> n;
        ll a[n];
        ll odd=0, even=0;
        loop(n)
        {
            cin >> a[i];
            (a[i]%2==0) ? even++ : odd++;
        }
        if(odd<=1)
        {
            cout << "-1\n";
        }
        else if(odd%2==0)
        {
            loop(n)
            {
                if(a[i]%2!=0)
                {
                    cout << a[i] << " ";
                }
            }
            loop(n)
            {
                if(a[i]%2==0)
                {
                    cout << a[i] << " ";
                }
            }
            cout << '\n';
        }
        else if(even==0)
        {
            cout << "-1\n";
        }
        else
        {
            ll nodd=0;
            loop(n)
            {
                if(a[i]%2!=0)
                {
                    ++nodd;
                    if(nodd==odd)
                    {
                        a[0]=a[i];
                        break;
                    }
                    cout << a[i] << " ";
                }
            }
            loop(n)
                {
                    if(a[i]%2==0)
                    {
                        cout << a[i] << " ";
                    }
                }
            cout << a[0] << '\n';
        }
    }
    return 0;
}

Can Somebody tell which kinda testcase is my code failing to pass, I see no mistakes, I even tried to match the if else statements according to the editorial, still geting WA.
PLEASE HELP

[arunmozhi12]

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
public class Main
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int tt=0;tt<t;tt++){
int n=sc.nextInt();int a[]=new int[n];
int no_of_even=0;int no_of_odd=0;
ArrayList evenelementlist=new ArrayList<>();
ArrayList oddelementlist=new ArrayList<>();
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
if(a[i]%2==0){
evenelementlist.add(a[i]);
no_of_even++;
}
else{
oddelementlist.add(a[i]);
no_of_odd++;
}
}
if(no_of_odd<=1 && no_of_even>=1){
System.out.println(-1);
}
else if(no_of_odd%2==0){
for(int i=0;i<oddelementlist.size();i++){
System.out.print(oddelementlist.get(i)+" “);
}
for(int i=0;i<evenelementlist.size();i++){
System.err.print(evenelementlist.get(i)+” “);
}
System.out.println();
continue;
}
else if(no_of_odd%2==1){
if(no_of_even==0){
System.out.println(-1);
}
else{
for(int i=0;i<oddelementlist.size()-1;i++){
System.out.print(oddelementlist.get(i)+” “);
}
for(int i=0;i<evenelementlist.size();i++){
System.out.print(evenelementlist.get(i)+” ");
}
System.out.print(oddelementlist.get(oddelementlist.size()-1));
System.out.println();
}
}

	}
}

}

what is wrong with this code it’s working perfectly on my IDE but not working on codechef???

[joffan]

@anon67629683

@cherry0697

else:
		if(len(odd)%2):
			print(odd.pop(),end=' ')
		print(*even,end=' ')
		print(*odd)

Can someone please explain me the working of this code (Author’s solution last 5 lines).

Sure.
The “if len(odd)%2:” test checks whether the number of odd entries in the list is odd, since “if X” will succeed unless X is False, zero, null or empty. An even-length block of odd numbers (with only even neighbours) produces an odd sum, so we banish any “spare” odd number to the start of the permutation, insulate it with even numbers, then print the now-even-length block of remaining odd numbers.

[anon19359521]

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

int main()
{

    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        int ar[n];
        int oddcnt = 0;
        for (int i = 0; i < n; i++)
        {
            cin >> ar[i];
            if (ar[i] % 2 != 0)
            {
                oddcnt++;
            }
        }

        int lo = 0, hi = n - 1;
        for (int i = 0; i < n; i++)
        {
            if (ar[hi] % 2 != 0)
            {
                swap(ar[lo], ar[hi]);
                lo++;
            }
            else
            {
                hi--;
            }
        }
        long long ans = 0;
        for (int i = 0; i < n - 1; i++)
        {
            int temp = ar[i] * ar[i + 1];
            ans += temp;
        }

        if (oddcnt % 2 == 0)
        {
            if (ans % 2 != 0)
            {
                for (int i = 0; i < n; i++)
                {
                    cout << ar[i] << " ";
                }
                cout << endl;
            }
            else
            {
                cout << -1 << endl;
            }
        }
        else
        {
            if (ans % 2 != 0)
            {
                for (int i = 0; i < n; i++)
                {
                    cout << ar[i] << " ";
                }
                cout << endl;
            }
            else
            {
                cout << -1 << endl;
            }
        }
    }
}[quote="cherry0697, post:1, topic:100065, full:true"]
# PROBLEM LINK:

[Contest Division 1](https://www.codechef.com/LTIME106A/problems/ADJLOVE)
[Contest Division 2](https://www.codechef.com/LTIME106B/problems/ADJLOVE)
[Contest Division 3](https://www.codechef.com/LTIME106C/problems/ADJLOVE)
[Contest Division 4](https://www.codechef.com/LTIME106D/problems/ADJLOVE)

**Setter:** [S.Manuj Nanthan](https://www.codechef.com/users/munch_01)
**Tester:** [Manan Grover](https://www.codechef.com/users/mexomerf)
**Editorialist:** [Aman Dwivedi](https://www.codechef.com/users/cherry0697)

# DIFFICULTY:

Easy

# PREREQUISITES:

Maths

# PROBLEM:

An array is called *lovely* if the sum of product of each adjacent pair of elements is odd.

More formally, the array $S$ of size $M$ is lovely if the value $\sum_{i=1}^{M-1}$ $(S_i . S_{i+1})$ is **odd**.

You are given an array $A$ consisting of $N$ positive integers. Find a [permutation](https://en.wikipedia.org/wiki/Permutation#Permutations_of_multisets) of array $A$ which is *lovely*. 

If multiple such permutations are possible, output any. If there is no *lovely* permutation, output `-1`.

# EXPLANATION:

Let's try to see what happens under various cases, before that remember the three basic properties:

$$
Even+Even = Even \\
Odd+Odd = Even \\
Odd+Even = Odd
$$

$$
and 
$$
$$
Even * Even = Even \\
Odd*Odd = Odd \\
Even*Odd = Even
$$

Now let's look the cases we were talking about:

- Odd numbers are less than or equal to $1$.

  Let's see what happens when there is no odd number present. Hence in any permutation you arrange the array elements. The consecutive product is gonna be even for all the indexes look at the above property that even multiplied with even gives you an even number. And then the sum of all even numbers is going to be even.

   Now when there is only one odd element in the given array. Wherever you place this odd number it's left side element and right side element is going to be even. And as we know even multiplied with odd gives you even number. Again the sum of all even numbers is going to be even.

   Hence we can conclude that in such cases it is never possible to achieve the odd sum in whatever permutation we arrange the given array.

- All numbers of the given array are odd.

    This is very interesting and simple case as all numbers are odd and hence when the odd number is multiplied with the odd number it produces an odd number. Hence every consecutive product is an odd number. Now the answer depends whether the sum of these consecutive product is even or odd.

     - $N$ is Even
         
        There will be $(N-1)$ consecutive products that exist for the the array of length $N$. Hence $(N-1)$ is an odd number. If odd number is added odd times it produces an odd number.

     - $N$ is Odd 
    
         In this case $(N-1)$ is going to be even. Hence when odd number is added even times it produces an even number.

     Hence we can conclude that in such cases whether the sum is going to be odd depends on whether $N$ is even.

- All other cases

   Ok, so for all other cases it is always possible to produce an odd number. Let's say the number of odd numbers in the given array be $X$. Now let us try to prove how:

   [details = "X is Odd"]
    Now we know that these numbers are the only chances for us to get the odd sum in the array. Now if we place all these numbers consecutively then there will be $(X-1)$ consecutive odd products. Since $(X-1)$ is even hence we will end up getting the sum as even.

    Let us then do one thing place the $(X-1)$ odd numbers consecutively and the remaining odd number anywhere. Now there will be $(X-2)$ odd consecutive products in the given array which leads us to get the odd sum.

    Hence we can say that it is possible to get the odd sum when $X$ is going to be odd.
   [/details]

   [details="X is Even"]
     Very simple if you read the Odd case above. Just place the all these $X$ numbers consecutive and then you know what happens and you will be able to get the odd sum.
   [/details]

# TIME COMPLEXITY:

$O(N)$ per test case.

# SOLUTIONS:

[details = "Author"]

for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
odd=[]
even=[]
for i in a:
if(i%2):
odd.append(i)
else:
even.append(i)
if(len(odd)<=1 or (len(odd)==n and n%2)):
print(-1)
else:
if(len(odd)%2):
print(odd.pop(),end=’ ‘)
print(*even,end=’ ')
print(*odd)

[/details]

[details = "Tester"]

#include <bits/stdc++.h>
using namespace std;
long long readInt(long long l, long long r, char endd) {
long long x = 0;
int cnt = 0;
int fi = -1;
bool is_neg = false;
while (true) {
char g = getchar();
if (g == ‘-’) {
assert(fi == -1);
is_neg = true;
continue;
}
if (‘0’ <= g && g <= ‘9’) {
x *= 10;
x += g - ‘0’;
if (cnt == 0) {
fi = g - ‘0’;
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);

        assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
    }
    else if (g == endd) {
        assert(cnt > 0);
        if (is_neg) {
            x = -x;
        }
        assert(l <= x && x <= r);
        return x;
    }
    else {
        assert(false);
    }
}

}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
int t;
t = readInt(1, 1000, ‘\n’);
while(t–){
int n;
n = readInt(2, 500, ‘\n’);
int temp;
vector e, o;
for(int i = 0; i < n; i++){
if(i != n - 1){
temp = readInt(1, 1000000, ’ ');
}else{
temp = readInt(1, 1000000, ‘\n’);
}
if(temp % 2){
o.push_back(temp);
}else{
e.push_back(temp);
}
}
if(o.size() == 0){
cout<<-1<<"\n";
}else{
if(o.size() % 2 == 0){
for(int i = 0; i < o.size(); i++){
cout<<o[i]<<" “;
}
for(int i = 0; i < e.size(); i++){
cout<<e[i]<<” “;
}
cout<<”\n";
}else{
if(e.size() == 0 || o.size() == 1){
cout<<-1<<"\n";
}else{
cout<<o[0]<<" “;
for(int i = 0; i < e.size(); i++){
cout<<e[i]<<” “;
}
for(int i = 1; i < o.size(); i++){
cout<<o[i]<<” “;
}
cout<<”\n";
}
}
}
}
return 0;
}

[/details]

[details = "Editorialist"]

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

void solve()
{
int n;
cin>>n;

vector<int> even,odd;

for(int i=0;i<n;i++)
{
    int x;
    cin>>x;
    
    if(x%2)
        odd.push_back(x);
    else 
        even.push_back(x);
}

if (odd.size()<=1 || (odd.size() == n && n%2))
{
    cout<<-1<<endl;
    return;
}

if(odd.size()%2)
{
    cout<<odd[0]<<" ";
    odd.erase(odd.begin());
}

for(auto itr: even)
    cout<<(itr)<<" ";

for(auto itr: odd)
    cout<<(itr)<<" ";
    
cout<<endl;

}

int main()
{
int t;
cin>>t;

while(t--)
    solve();

return 0;
}

[/details]
[/quote]

[quote="cherry0697, post:1, topic:100065, full:true"]
# PROBLEM LINK:

[Contest Division 1](https://www.codechef.com/LTIME106A/problems/ADJLOVE)
[Contest Division 2](https://www.codechef.com/LTIME106B/problems/ADJLOVE)
[Contest Division 3](https://www.codechef.com/LTIME106C/problems/ADJLOVE)
[Contest Division 4](https://www.codechef.com/LTIME106D/problems/ADJLOVE)

**Setter:** [S.Manuj Nanthan](https://www.codechef.com/users/munch_01)
**Tester:** [Manan Grover](https://www.codechef.com/users/mexomerf)
**Editorialist:** [Aman Dwivedi](https://www.codechef.com/users/cherry0697)

# DIFFICULTY:

Easy

# PREREQUISITES:

Maths

# PROBLEM:

An array is called *lovely* if the sum of product of each adjacent pair of elements is odd.

More formally, the array $S$ of size $M$ is lovely if the value $\sum_{i=1}^{M-1}$ $(S_i . S_{i+1})$ is **odd**.

You are given an array $A$ consisting of $N$ positive integers. Find a [permutation](https://en.wikipedia.org/wiki/Permutation#Permutations_of_multisets) of array $A$ which is *lovely*. 

If multiple such permutations are possible, output any. If there is no *lovely* permutation, output `-1`.

# EXPLANATION:

Let's try to see what happens under various cases, before that remember the three basic properties:

$$
Even+Even = Even \\
Odd+Odd = Even \\
Odd+Even = Odd
$$

$$
and 
$$
$$
Even * Even = Even \\
Odd*Odd = Odd \\
Even*Odd = Even
$$

Now let's look the cases we were talking about:

- Odd numbers are less than or equal to $1$.

  Let's see what happens when there is no odd number present. Hence in any permutation you arrange the array elements. The consecutive product is gonna be even for all the indexes look at the above property that even multiplied with even gives you an even number. And then the sum of all even numbers is going to be even.

   Now when there is only one odd element in the given array. Wherever you place this odd number it's left side element and right side element is going to be even. And as we know even multiplied with odd gives you even number. Again the sum of all even numbers is going to be even.

   Hence we can conclude that in such cases it is never possible to achieve the odd sum in whatever permutation we arrange the given array.

- All numbers of the given array are odd.

    This is very interesting and simple case as all numbers are odd and hence when the odd number is multiplied with the odd number it produces an odd number. Hence every consecutive product is an odd number. Now the answer depends whether the sum of these consecutive product is even or odd.

     - $N$ is Even
         
        There will be $(N-1)$ consecutive products that exist for the the array of length $N$. Hence $(N-1)$ is an odd number. If odd number is added odd times it produces an odd number.

     - $N$ is Odd 
    
         In this case $(N-1)$ is going to be even. Hence when odd number is added even times it produces an even number.

     Hence we can conclude that in such cases whether the sum is going to be odd depends on whether $N$ is even.

- All other cases

   Ok, so for all other cases it is always possible to produce an odd number. Let's say the number of odd numbers in the given array be $X$. Now let us try to prove how:

   [details = "X is Odd"]
    Now we know that these numbers are the only chances for us to get the odd sum in the array. Now if we place all these numbers consecutively then there will be $(X-1)$ consecutive odd products. Since $(X-1)$ is even hence we will end up getting the sum as even.

    Let us then do one thing place the $(X-1)$ odd numbers consecutively and the remaining odd number anywhere. Now there will be $(X-2)$ odd consecutive products in the given array which leads us to get the odd sum.

    Hence we can say that it is possible to get the odd sum when $X$ is going to be odd.
   [/details]

   [details="X is Even"]
     Very simple if you read the Odd case above. Just place the all these $X$ numbers consecutive and then you know what happens and you will be able to get the odd sum.
   [/details]

# TIME COMPLEXITY:

$O(N)$ per test case.

# SOLUTIONS:

[details = "Author"]

for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
odd=[]
even=[]
for i in a:
if(i%2):
odd.append(i)
else:
even.append(i)
if(len(odd)<=1 or (len(odd)==n and n%2)):
print(-1)
else:
if(len(odd)%2):
print(odd.pop(),end=’ ‘)
print(*even,end=’ ')
print(*odd)

[/details]

[details = "Tester"]

#include <bits/stdc++.h>
using namespace std;
long long readInt(long long l, long long r, char endd) {
long long x = 0;
int cnt = 0;
int fi = -1;
bool is_neg = false;
while (true) {
char g = getchar();
if (g == ‘-’) {
assert(fi == -1);
is_neg = true;
continue;
}
if (‘0’ <= g && g <= ‘9’) {
x *= 10;
x += g - ‘0’;
if (cnt == 0) {
fi = g - ‘0’;
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);

        assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
    }
    else if (g == endd) {
        assert(cnt > 0);
        if (is_neg) {
            x = -x;
        }
        assert(l <= x && x <= r);
        return x;
    }
    else {
        assert(false);
    }
}

}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
int t;
t = readInt(1, 1000, ‘\n’);
while(t–){
int n;
n = readInt(2, 500, ‘\n’);
int temp;
vector e, o;
for(int i = 0; i < n; i++){
if(i != n - 1){
temp = readInt(1, 1000000, ’ ');
}else{
temp = readInt(1, 1000000, ‘\n’);
}
if(temp % 2){
o.push_back(temp);
}else{
e.push_back(temp);
}
}
if(o.size() == 0){
cout<<-1<<"\n";
}else{
if(o.size() % 2 == 0){
for(int i = 0; i < o.size(); i++){
cout<<o[i]<<" “;
}
for(int i = 0; i < e.size(); i++){
cout<<e[i]<<” “;
}
cout<<”\n";
}else{
if(e.size() == 0 || o.size() == 1){
cout<<-1<<"\n";
}else{
cout<<o[0]<<" “;
for(int i = 0; i < e.size(); i++){
cout<<e[i]<<” “;
}
for(int i = 1; i < o.size(); i++){
cout<<o[i]<<” “;
}
cout<<”\n";
}
}
}
}
return 0;
}

[/details]

[details = "Editorialist"]

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

void solve()
{
int n;
cin>>n;

vector<int> even,odd;

for(int i=0;i<n;i++)
{
    int x;
    cin>>x;
    
    if(x%2)
        odd.push_back(x);
    else 
        even.push_back(x);
}

if (odd.size()<=1 || (odd.size() == n && n%2))
{
    cout<<-1<<endl;
    return;
}

if(odd.size()%2)
{
    cout<<odd[0]<<" ";
    odd.erase(odd.begin());
}

for(auto itr: even)
    cout<<(itr)<<" ";

for(auto itr: odd)
    cout<<(itr)<<" ";
    
cout<<endl;

}

int main()
{
int t;
cin>>t;

while(t--)
    solve();

return 0;
}

[/details]
[/quote]

can you pls check what i did wrong in my approach..

[ritesh_gupta97]

Please see this, why this is giving WA, please help me correct it.
#include <bits/stdc++.h>
using namespace std;

#define REP(i, a, b) for (ll i = a; i <= b; i++)
typedef long long ll;

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);

int t = 1;
cin >> t;
while (t--)
{
    int n;
    cin >> n;
    ll a[n];
    ll even=0;
    ll odd=0;
    ll b[n]= {0};
    ll j=0, k;
    REP(i,0,n-1)
        cin>>a[i];
    REP(i,0,n-1)
    {
        if(a[i]%2==0)
            even++;
        else
            odd++;
    }
    k=odd;
    if(odd <=1 || (odd==n && n%2) || (odd%2))
        cout<<"-1"<<endl;
    else
    {
        for(ll i=0; i<n; i++)
        {
            if(a[i]%2!=0)
                b[++j-1]=a[i];
            else
                b[++k-1]=a[i];
        }
        REP(i,0,n-1)
            cout<<b[i]<<" ";
        cout<<endl;
    }
    

}

return 0;

}

[joffan]

Consider the test case:

1
4
5 6 7 9

noting that the sequence as given is already lovely, since
\sum_{i=1}^{N-1} A_i\cdot A_{i+1} = 30 + 42 + 63 = 135
is odd, despite having an odd number of odd numbers. This happens because the arrangement splits the odd numbers into two blocks, using the even numbers in between, to allow an even-length block of odd numbers. Which odd numbers go where exactly is not important, as long as we end up with that even-length block of odds.

[ritesh_gupta97]

please tell how can I correct in this code

[ritesh_gupta97]

@cherry0697

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

void solve()
{
    int n;
    cin>>n;
    
    vector<int> even,odd;
    
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        
        if(x%2)
            odd.push_back(x);
        else 
            even.push_back(x);
    }
    
    if (odd.size()<=1 || (odd.size() == n && n%2))
    {
        cout<<-1<<endl;
        return;
    }
    
    if(odd.size()%2)
    {
        cout<<odd[0]<<" ";
        odd.erase(odd.begin());
    }
    
    for(auto itr: even)
        cout<<(itr)<<" ";
    
    for(auto itr: odd)
        cout<<(itr)<<" ";
        
    cout<<endl;
        
}

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

return 0;
}

Thank you got it

[jatin0308_adm]

Hey @abhinav_hac1 ,
You are forgetting 2 cases what if whole array contains odd elements. so there can be two possible cases may be they make sum odd / even. for eg consider array A having N odd elements (N is odd) thus if we find out all products it will be N-1 odd products(since odd*odd = odd) thus N-1 is even and sum of even number of odd elements makes sum even but it will not affect when N is even. that’s why your if condition (o <=1 ) should be as if(o <=1 || (o==n && n%2==1)) .

also your first if condition if(o%2==0) is wrong for case when ‘o’ is 0 so make sure there will always be positive integer if(o%2==0 && o > 0).
rest all works fine.

[prajjwal07_adm]

Hey @piyushchef
Thanks for asking your doubt.

Here are some test cases in which your logic fails.

1
4
1 1 1 2

Correct output

1 2 1 1