September Long Challenge 2021

Shuffling Parities Solution September Challenge 2021

by

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)

September Long Challenge 2021 Solution

3 thoughts on “Shuffling Parities Solution September Challenge 2021”

Leave a Comment

1 × 4 =