Shuffling Parities Codechef Solution
Chef is given an array A consisting of N positive integers. Chef shuffles the array A and creates a new array B of length N, where Bi=(Ai+i)mod2, for each i(1≤i≤N). Find the maximum possible sum of integers of the array B, if Chef shuffles the array A optimally.
Input Format
- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- Each test case contains two lines of input.
- The first line of each test case contains an integer N.
- The second line of each test case contains N space-separated integers A1,A2,…,AN.
Output Format
For each test case, print a single line containing one integer – the maximum sum of integers of the array B.
Constraints
- 1≤T≤104
- 1≤N≤105
- 1≤Ai≤109
- Sum of N over all test cases does not exceed 3⋅105.
Subtasks
Subtask #1 (100 points): Original constraints
Sample Input 1
3
3
1 2 3
3
2 4 5
2
2 4
Sample Output 1
2
3
1
Explanation
Test case 1: One of the optimal ways to shuffle the array A is [2,1,3]. Then the array B=[(2+1)mod2,(1+2)mod2,(3+3)mod2]=[1,1,0]. So the sum of integers of array B is 2. There is no other possible way to shuffle array A such that the sum of integers of array B becomes greater than 2.
Test case 2: One of the optimal ways shuffle the array A is [2,5,4]. Then the array B=[(2+1)mod2,(5+2)mod2,(4+3)mod2]=[1,1,1]. So the sum of integers of array B is 3 .
SOLUTION
Program C: Shuffling Parities Codechef Solution in C
#include <stdio.h>
int main(void) {
int tc;
scanf("%d",&tc);
for(int z=0;z<tc;z++){
int n;
scanf("%d",&n);
int arr[n],sum=0,x,y,ev=0,odd=0;
if(n%2==0){
x=n/2;
y=n/2;
}
else{
x=(n/2)+1;
y=n/2;
}
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
if(arr[i]%2==0){
ev++;
}
else{
odd++;
}
}
if(ev>x){
sum+=x;
}
else{
sum+=ev;
}
if(odd>y){
sum+=y;
}
else{
sum+=odd;
}
printf("%d\n",sum);
}
return 0;
}
Program C++: Shuffling Parities Codechef Solution in C++
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
int t;
cin>>t;
while(t--)
{
int n,c1=0,c2=0,c3=0,c4=0;
cin>>n;
int a[n+5],b[n+5];
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(i%2==0) //even of index
c1++;
if(i%2!=0) //odd of index
c2++;
if(a[i]%2==0) //even of array
c3++;
if(a[i]%2!=0) //odd of array
c4++;
}
cout<<min(c1,c4)+min(c2,c3)<<endl;
}
}
Program Java: Shuffling Parities Codechef Solution in Java
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
try{
Scanner scr= new Scanner(System.in);
int t= scr.nextInt();
while(t-->0){
int n= scr.nextInt();
double temp= n;
int oddindex=(int) Math.ceil(temp/2);
int evenindex=n-oddindex;
int ar[]= new int[n];
int arreven=0;
int arrodd=0;
for(int i=0;i<n;i++){
ar[i]= scr.nextInt();
if(ar[i]%2==0){
arreven+=1;
}
else{
arrodd+=1;
}
}
int count=Math.min(oddindex,arreven)+Math.min(evenindex,arrodd);
System.out.println(count);
}
}catch(Exception e){
return;
}
}
}
Program Python: Shuffling Parities Codechef Solution in Python
for _ in range (int(input())):
n=int(input())
l=list(map(int,input().split()))
flag=tmp=0
for i in l:
if(i%2==1):
flag+=1
else:
tmp+=1
tt=min(flag,n//2 )+ min(tmp,(n+1)//2)
print(tt)
This Gives Runtime Error
Thats Right Solution my BAD
Thanks for this, i figure it out were I was making mistake