Codechef September long challenge 2021 | Shuffling Parities Solution

 

Codechef September long challenge 2021 | Shuffling Parities Solution

• Post published:0 Comm\ents

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.

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 to 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 .

C++ Solution

#include <bits/stdc++.h>

using namespace std;

int main()

{

int t;

cin >> t;

while (t--)

{

int n;

cin >> n;

vector<int> v;

for (int i = 0; i < n; i++)

{

int temp;

cin >> temp;

v.push_back(temp);

}

int odd = 0, even = 0;

for (int i = 0; i < n; i++)

{

if ((i + 1 + v[i]) % 2 == 0)

{

if (v[i] % 2 == 0)

even++;

else

odd++;

}

}

int ans = 0;

ans = abs(even - odd);

ans = n - ans;

cout << ans << endl;

}

return 0;

}

Python Solution

for i in range(int(input())):

n = int(input())

odd =0

even=0

a = list(map(int, input().split( )))

for x in a:

if x%2==1:

odd+=1

else:

even+=1

pos = min(even, (n+1)//2 ) + min(odd, n//2)

print(pos)

 

Java Solution

/* package codechef; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Codechef

{

public static void arrange (long a[], long n) {

int o = 0;

int e = 1;

while(true) {

while(e < n && a[e] % 2 == 1) e += 2;

while(o < n && a[o] % 2 == 0) o += 2;

if(e < n && o < n) {

long temp = a[e];

a[e] = a[o];

a[o] = temp;

}

else break;

}

}

public static void main (String[] args) throws java.lang.Exception

{

Scanner scan = new Scanner(System.in);

int t = scan.nextInt();

while(t-- != 0) {

long n = scan.nextLong();

long[] a = new long[(int)n];

for(int i = 0; i < n; i++) {

a[i] = scan.nextLong();

}

arrange(a, n);

int sum = 0;

for(int i = 0; i < n; i++) {

sum += (a[i] + (i+1)) % 2;

}

System.out.println(sum);

}

}

}