# MKSMEVN - Editorial

Testers: Shubham Anand Jain, Aryan
Editorialist: Nishank Suresh

Simple

Modulo, Parity

# PROBLEM:

Given an integer array A of n integers, in one operation Chef can set A_i = A_i^{max(0, \lceil\frac{A_i}{2}\rceil-1)}. What is the minimum number of operations needed to make the sum of the array even?

# QUICK EXPLANATION:

The answer is 0 if the sum is already even, 1 if the sum is odd and A contains a 2, and -1 otherwise.

# EXPLANATION:

If the sum of the array is already even, the answer is obviously 0.
Now, what if the sum is odd?
It can be observed that any power of an odd integer is always going to be odd, and any positive power of an even integer is even - however, an even integer to the power 0 is 1, which is odd.
So, if we are to change the parity of our sum from odd to even, our only hope is to turn some even integer into 1 - operating on odd integer is useless because its parity will never change.
If the array has a 2, in one operation we can make it 2^{\lceil\frac{2}{2}\rceil-1} = 2^{1-1} = 2^0 = 1, and this is enough to change the parity of the sum.
What if every even integer in A is \geq 4? Then, none of them can be brought down to 1 - can you see why?

Proof

Let A_i \geq 4.
\lceil\frac{A_i}{2}\rceil-1 \geq 2-1 = 1, so operating on A_i gives us a positive power of A_i - and a positive power of A_i is even and \geq A_i\geq 4, which is what we started out with.
So no matter what we do it’s impossible to fall below 4 and reach 1, and thus changing the parity of the sum is also impossible.

The final solution is thus:

• If the sum of A is even, print 0
• If the sum of A is odd and A contains a 2, print 1.
• Else, print -1.

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# SOLUTIONS:

Setter's Solution (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long int
#define ordered_set tree<int, nuint_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
mt19937 rng(std::chrono::duration_cast<std::chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count());
#define mp make_pair
#define pb push_back
#define F first
#define S second
const int N=100005;
#define M 1000000007
#define BINF 1e5
#define init(arr,val) memset(arr,val,sizeof(arr))
#define MAXN 17500001
#define deb(xx) cout << #xx << " " << xx << "\n";
const int LG = 22;

int get(vector<int>v){
int n = v.size();
int s = 0, f = 0;
for(auto i : v){
s += i;
if(i == 2) f = 1;
}
if(s % 2 == 0) return 0;
if(f) return 1;
return -1;
}

#undef int
int main() {
#define int long long int
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("optput.txt", "w", stdout);
#endif

int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<int>a(n);
for(int i = 0; i < n; i++)
cin >> a[i];

cout << get(a) << endl;
}

return 0;

}

Tester's Solution (C++)
//By TheOneYouWant
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)

int main(){
fastio;

int tests;
cin>>tests;
while(tests--){
int n;
cin>>n;
int a[n];
for(int i = 0; i < n; i++){
cin>>a[i];
}
bool p = 0;
int s = 0;

for(int i = 0; i < n; i++){
if(a[i] == 2) p = 1;
s += a[i];
s %= 2;
}
if(s == 0){
cout<<0<<endl;
}
else if(p == 1){
cout<<1<<endl;
}
else{
cout<<-1<<endl;
}
}

return 0;
}

Editorialist's Solution (Python)
    t = int(input())
for _ in range(t):
n = int(input())
a = list(map(int, input().split()))

if sum(a)%2 == 0: # If sum is even, no operations required
print(0)
elif a.count(2) > 0: # If the array contains a 2, 1 operation
print(1)
else: # Can't be done
print(-1)

2 Likes

hey, can you explain for test case 9 9 9
which can be converted to even on single operation, but code print -1 for this test case…

int main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int cnt_one=0;
int odd=0;
int cnt_two=0;
for(int i=0;i<n;i++)
{
int a;
cin>>a;
if(a==1)
{
cnt_one=cnt_one+1;
}
if(a&1)
{
odd=odd+1;
}
if(a==2)
{
cnt_two=cnt_two+1;
}
}
if((cnt_one==n)&&(odd&1))
{
cout<<-1<<endl;
}
else if((odd&1)&&(cnt_one>0))
{
cout<<1<<endl;
}
else if((odd&1)&&(cnt_two>0))
{
cout<<1<<endl;
}
else if(odd%2==0)
{
cout<<0<<endl;
}
else
{
cout<<-1<<endl;
}
}
}

Why am I getting partially accepted and only 70 points for this solution

Okay see the sum in this case would be (9+9+9) 27. And applying the given formula on any odd integer is of no use since it would always result in the odd number. Same goes for even number. The only number which can change our ans to even sum is 2. (Try applying the formula you will get res as 1).

For input

1
2
1 4


that code prints 1, but the answer is -1.
In general the count of 1s has nothing to do with the solution.