PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Setter: Akshit Monga
Tester: Tejas Pandey
Editorialist: Kanhaiya Mohan
DIFFICULTY:
Easy
PREREQUISITES:
PROBLEM:
Chef calls a sequence of integers A_1, A_2, …, A_N \texttt{tasty} if it satisfies the condition
- parity(A_i \& A_{i+1}) \neq parity(A_i | A_{i+1}) for all 1 \leq i <N.
Given a sequence A of length N. You may perform following operation on the sequence any number of times (possible 0):
- Choose 2 indices i and j (1 \leq i,j \leq N ; i \neq j) and change A_i to A_i ⊕ A_j.
Chef is asking you to make the sequence tasty using the minimum number of operations, or report that it is impossible.
QUICK EXPLANATION:
- A sequence is
tastyif the elements have alternating parity. - In one operation, we can change the parity of any element i by choosing a j such that A_j is odd.
- The answer is -1 if the sequence has no odd elements.
- To find minimum operations, we can assume the sequence to start from an odd/even element and check the number of mismatches in each case.
- To find a sequence of operations, choose one odd element and correct all other elements using this element. Keep in mind, you might also need to correct the chosen odd element.
EXPLANATION:
What is a tasty sequence?
We are given that a sequence is tasty, if the parity of bitwise and of consecutive elements is not equal to the parity of their bitwise or.
Possible Cases
Let us consider all possible parities of consecutive elements.
The condition holds true when consecutive elements have unequal parity. In other words, a sequence is tasty, if the elements of the sequence have alternating parity.
The sequence would be either of these two forms:
- odd, even , odd, even, ...
- even, odd, even, odd, ...
Explaining an Operation
In one operation, we choose two indices i, j (i \neq j) and change A_i to A_i ⊕ A_j.
Possible Cases
Let us consider all possible parities of A_i and A_j.
In one operation, we can change the parity of any element i by choosing a j such that A_j is odd.
When is the answer -1?
We know that, to change the parity of an element, we need another odd element. This means that if a sequence has only even elements, we can never convert it to a tasty sequence and thus the answer is -1 in that case.
Minimum number of Operations
If there is at least one odd element in the sequence, we can always convert it to a tasty sequence.
It takes exactly one move to change the parity of an element. We can assume the sequence to start from an odd/even element and check the number of mismatches in each case. The case with lesser mismatches is optimal and would require minimum number of operations.
Possible sequence of Operations
By now, we know whether we should start the sequence with an odd element, or an even element.
One possible sequence of operations would be:
- Correct the first two elements using the last odd element of the sequence.
- Correct the rest of the sequence using the first odd element of the updated sequence.
Note that this would not fail even if the last odd element of the initial sequence is amongst the first two positions.
You can have any other sequence as well. Just keep in mind that the element you choose for changing the rest of the sequence might also be a mismatch.
You can see the editorialist’s solution for implementation details.
Alternate Implementation
Claim: We can always have an index with odd element such that it is not a mismatch.
Proof: Let us assume that there is no odd element such that it is not a mismatch OR all odd elements are a mismatch.
The two possible tasty sequences are:
- Starting from odd element: Since the odd elements are mismatch, all odd positions must have even numbers. Thus, it is optimal to choose the sequence starting with even element since atleast half elements in the sequence are even and matched. This means that the odd elements, which are placed at even positions are not a mismatch.
- Starting from even element: Since the odd elements are mismatch, all even positions must have even numbers. Thus, it is optimal to choose the sequence starting with odd element since atleast half elements in the sequence are even and matched. This means that the odd elements, which are placed at odd positions are not a mismatch.
Hence, proved by contradiction that we can always have an index with odd element such that it is not a mismatch.
We can use this element to change all other elements of the sequence. You can see setter’s solution for implementation details.
TIME COMPLEXITY:
The time complexity is O(N) per test case.
SOLUTION:
Setter's Solution (Python)
'''Author- Akshit Monga'''
from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
n=int(input())
a=[int(x) for x in input().split()]
if [ele%2 for ele in a].count(1)==0:
print(-1)
continue
x=delta=0
for i in range(n):
if a[i]%2!=i%2:
x+=1
if x>n-x:
delta+=1
ind=-1
for i in range(n):
if a[i]%2 and (i+delta)%2:
ind=i
break
assert ind!=-1
ops=[]
for i in range(n):
if a[i]%2!=(i+delta)%2:
ops.append((i+1,ind+1))
print(len(ops))
assert len(ops)==min(x,n-x)
for i in ops:
a[i[0]-1]^=a[i[1]-1]
print(*i)
for i in range(n-1):
assert a[i]%2!=a[i+1]%2
Setter's Solution (C++)
//Author- Akshit Monga
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T; cin>>T;
while(T--){
int n; cin>>n;
int arr[n];
bool all_even=1;
for(int i=0;i<n;i++){
cin>>arr[i];
if(arr[i]%2) all_even=0;
}
if(all_even){
cout<<-1<<'\n';
continue;
}
int x=0,delta=0;
for(int i=0;i<n;i++){
if((arr[i]%2)!=(i%2)) x++;
}
if(x>n-x)delta=1;
int ind=-1;
for(int i=0;i<n;i++){
if((arr[i]%2) and ((i+delta)%2)){
ind=i;
break;
}
}
assert(ind!=-1);
vector<array<int,2>> ops;
for(int i=0;i<n;i++){
if((arr[i]%2)!=((i+delta)%2)){
ops.push_back({i+1,ind+1});
}
}
cout<<(int) ops.size()<<'\n';
assert((int) ops.size()==min(x,n-x));
for(auto inds:ops){
cout<<inds[0]<<" "<<inds[1]<<'\n';
}
}
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
int a[n];
int cnt[2][2];
memset(cnt, 0, sizeof(cnt));
for(int i = 0; i < n; i++) cin >> a[i], cnt[i&1][a[i]&1]++;
if(cnt[0][1] + cnt[1][1] == 0) cout << "-1\n";
else {
if(cnt[0][1] == 0 || cnt[0][1] + cnt[1][0] < cnt[1][1] + cnt[0][0]) {
cout << cnt[0][1] + cnt[1][0] << "\n";
int first = 0;
for(int i = 1; i < n; i+=2)
if(a[i]&1)
first = i;
for(int i = 1; i < n; i+=2)
if(!(a[i]&1))
cout << i + 1 << " " << first + 1 << "\n";
for(int i = 0; i < n; i+=2)
if(a[i]&1)
cout << i + 1 << " " << first + 1 << "\n";
} else {
cout << cnt[1][1] + cnt[0][0] << "\n";
int first = 0;
for(int i = 0; i < n; i+=2)
if(a[i]&1)
first = i;
for(int i = 0; i < n; i+=2)
if(!(a[i]&1))
cout << i + 1 << " " << first + 1 << "\n";
for(int i = 1; i < n; i+=2)
if(a[i]&1)
cout << i + 1 << " " << first + 1 << "\n";
}
}
}
return 0;
}
Editorialist's Solution
#include <iostream>
#include <vector>
using namespace std;
void generateMoves(vector<int>& a){
int n = a.size();
int startOddMoves = 0;
int startEvenMoves = 0;
int lastOddPos = -1;
for(int i = 1; i<=n; i++){
if(i%2){
if(a[i-1]%2) startEvenMoves++;
else startOddMoves++;
}
else{
if(a[i-1]%2) startOddMoves++;
else startEvenMoves++;
}
if(a[i-1]%2) lastOddPos = i;
}
if(startOddMoves<startEvenMoves){
cout<<startOddMoves<<endl;
for(int i = 1; i<=n; i++){
if(i%2){
if(a[i-1]%2==0)
cout<<i<<' '<<lastOddPos<<endl;
}
else{
if(a[i-1]%2)
cout<<i<<' '<<lastOddPos<<endl;
}
if(i==1) lastOddPos = 1;
}
}
else{
cout<<startEvenMoves<<endl;
for(int i = 1; i<=n; i++){
if(i%2==0){
if(a[i-1]%2==0) cout<<i<<' '<<lastOddPos<<endl;
}
else{
if(a[i-1]%2) cout<<i<<' '<<lastOddPos<<endl;
}
if(i==2) lastOddPos = 2;
}
}
}
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int odds = 0;
vector<int> a(n);
for(int i = 0; i<n; i++){
cin>>a[i];
if(a[i]%2) odds++;
}
if(odds==0){
cout<<-1<<endl;
}
else{
generateMoves(a);
}
}
return 0;
}