Page Contents
Shuffling Parities Codechef Solution
Chef is given an array AA consisting of NN positive integers. Chef shuffles the array AA and creates a new array BB of length NN, where Bi=(Ai+i)mod2Bi=(Ai+i)mod2, for each i(1≤i≤N)i(1≤i≤N).
Find the maximum possible sum of integers of the array BB, if Chef shuffles the array AA optimally.
Also See: September Long Challenge 2021 Solutions
Input Format
- The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
- Each test case contains two lines of input.
- The first line of each test case contains an integer NN.
- The second line of each test case contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.
Output Format
For each test case, print a single line containing one integer – the maximum sum of integers of the array BB.
Constraints
- 1≤T≤1041≤T≤104
- 1≤N≤1051≤N≤105
- 1≤Ai≤1091≤Ai≤109
- Sum of NN over all test cases does not exceed 3⋅1053⋅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 11: One of the optimal ways to shuffle the array AA is [2,1,3][2,1,3]. Then the array B=[(2+1)mod2,(1+2)mod2,(3+3)mod2]=[1,1,0]B=[(2+1)mod2,(1+2)mod2,(3+3)mod2]=[1,1,0]. So the sum of integers of array BB is 22. There is no other possible way to shuffle array AA such that the sum of integers of array BB becomes greater than 22.
Test case 22: One of the optimal ways shuffle the array AA is [2,5,4][2,5,4]. Then the array B=[(2+1)mod2,(5+2)mod2,(4+3)mod2]=[1,1,1]B=[(2+1)mod2,(5+2)mod2,(4+3)mod2]=[1,1,1]. So the sum of integers of array BB is 33 .
Follow us on telegram for quick update an abundance of free knowledge: Click Here
Solution
Program 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++:
#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:
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:
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)
Codechef Long Challenges
September Long Challenge 2021 Solution
- Airline Restrictions
- Travel Pass
- Shuffling Parities
- XOR Equal
- 2-D Point Meeting
- Minimize Digit Sum
- Minimum Digit Sum 2
- Treasure Hunt
- Covaxin vs Covishield
August Long Challenge 2021 Solutions
- Olympics Ranking
- Problem Difficulties
- Chef and Bulb Invention
- Array Filling
- Special Triplets
- Geometry 1
- Charge Scheduling
- Chef and Digits of Large Numbers
- Fat Hut
- Alternating LG Queries
This Gives Runtime Error
Thats Right Solution my BAD
Thanks for this, i figure it out were I was making mistake