PROBLEM LINK:
Setter: Mladen Puzic
Tester: Michael Nematollahi
Editorialist: Taranpreet Singh
DIFFICULTY:
PREREQUISITES:
Basic Math, Observation.
PROBLEM:
You are given two arrays A and B of length N each. We need to pair every element from A to a distinct element from B. Suppose the N pairs formed are (X_i, Y_i). Maximize \sum_{i = 1}^{N} \left\lfloor \frac{X_i+Y_i}{2} \right\rfloor and print this maximized value.
EXPLANATION
First of all, Let us see how \left\lfloor \frac{a+b}{2} \right\rfloor works for different values of a and b.
If both a and b are even:
In this case, a+b is even and hence \left\lfloor \frac{a+b}{2} \right\rfloor = \frac{a+b}{2}.
If both a and b are odd:
In this case too, a+b is even and hence \left\lfloor \frac{a+b}{2} \right\rfloor = \frac{a+b}{2}.
If exactly one out of a and b is odd and other is even:
In this case, a+b is odd and hence, \left\lfloor \frac{a+b}{2} \right\rfloor = \frac{a+b}{2} - \frac{1}{2}.
Hence, if we want to maximize the sum, it is optimal to pair even value from A with even values from B and odd values from A$ with odd values from B.
If p is the number of pairs where an odd value is paired with an even value, we can see, it subtracts \frac{p}{2} from \sum_{i = 1}^{N} \frac{A_i+B_i}{2}. This is the final answer. We can calculate \sum_{i = 1}^{N} \frac{A_i+B_i}{2} easily. We need to find minimum possible p.
Let A_e be number of even elements in A, A_o be number of odd elements in A, B_e be number of even elements in B and B_o be number of odd elements in B. We can see, the maximum number of pairs where both values are even is min(A_e, B_e) and the maximum number of pairs where both values are odd is min(A_o, B_o). This gives the minimum number of pairs with one even and one odd value as p = N - min(A_e, B_e) - min(A_o, B_o) and hence, we have found p and the final answer.
Bonus: Same problem, replace the floor with ceil function.
TIME COMPLEXITY
Time complexity is O(N) per test case.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
#define MAXN 100010
using namespace std;
int A[MAXN], B[MAXN];
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cerr.tie(0);
int T; cin >> T;
while(T--) {
int N;
cin >> N;
for(int i = 1; i <= N; i++) cin >> A[i];
for(int i = 1; i <= N; i++) cin >> B[i];
long long K = 0; //sum of children's heights without odd parents
int oddMen = 0, oddWomen = 0; //how many men and women there are of odd height
for(int i = 1; i <= N; i++) {
K += A[i]/2;
K += B[i]/2;
if(A[i]%2 == 1) oddMen++;
if(B[i]%2 == 1) oddWomen++;
}
cout << K + min(oddMen, oddWomen) << endl;
}
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
const int MAXN = 1e5 + 10;
int n, c[2][2];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int te; cin >> te;
while (te--){
memset(c, 0, sizeof(c));
cin >> n;
ll sm = 0;
for (int w = 0; w < 2; w++)
for (int i = 0; i < n; i++){
int x; cin >> x;
c[w][x&1]++;
sm += x;
}
sm -= abs(c[0][1] - c[1][1]);
cout << sm/2 << "\n";
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class SILLYPRS{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni();
long ans = 0;
int[] f0 = new int[2], f1 = new int[2];
for(int i = 0; i< n; i++){
int x = ni();
ans+=x;
f0[x%2]++;
}
for(int i = 0; i< n; i++){
int x = ni();
ans+=x;
f1[x%2]++;
}
int total = n-Math.min(f0[0], f1[0])-Math.min(f0[1], f1[1]);
pn((ans-total)/2);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new SILLYPRS().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to Share your approach, if you want to. (even if its same 
) . Suggestions are welcomed as always had been. 
