PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Souradeep Paul
Testers: Shubham Anand Jain, Aryan
Editorialist: Nishank Suresh
DIFFICULTY:
Simple
PREREQUISITES:
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)