SILLYPRS - EDITORIAL

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

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 :stuck_out_tongue: ) . Suggestions are welcomed as always had been. :slight_smile:

1 Like

I calculated no of even digits in A and B.Then got the difference (i.e | no of even digits in A- no Of even digits in B| ) . This gave me the no of pairs that had one even and one odd no. But the solution was not accepted.Can you explain what was I missing?

According to this approach answer should be
(sum of all elements in a and b array)/2- (no of mismatched even)/2.

I used a different approach. I found parity of each input and sorted the arrays based on the parity. Then simply added the values together. Solution : https://www.codechef.com/viewsolution/24986100.

1 Like

Can someone please give me a better explanation of the actual code following the editorial

I used the simple method similar but slight different from given solution :
added all the values of array A and array B to sum
Then counted no. of even values in both and stored the minimum = e1
similarly for odd also e2
even even pair will remain even =e1
odd odd pair will become even =e2
remaining is odd even pair which is odd needs to be subtracted as when you get integer value from x/2 , if x is odd then actual answer is (x-1)/2
remaining is o = n-e1-e2
final answer = (sum-o)/2

Share the link of your Solution :slight_smile:

I first calculated the sum of all elements of A and B then i found the number of odd elements in A and B which can not be paired i.e. abs(no of odd in A- no of odd in B) ,I substracted this multiplied by 0.5 from the sum. i was gettting correct output but codchef did not accept my solution. please help me
https://www.codechef.com/viewsolution/24992069

I did slightly different. Here’s my solution- https://www.codechef.com/viewsolution/24986621

My approach:

  1. Partition both arrays into even and odd (even 1st (or odd 1st))
  2. Take ith element from both array and add it to ans(initially=0) as (a[i]+b[i])/2 (0<=i<n)
    ( ie sum+=(a[i]+b[i])/2 )

The basic idea was to add even(or odd) to even(or odd) first and pair up the rest.
https://www.codechef.com/viewsolution/24998406

I checked your solution, you were using int data type while will undergo overflow for large values as mentioned in constraints. Here is your fixed AC solution. Your approach was correct tho :wink:

https://www.codechef.com/viewsolution/25008359

First of all you just have to do

heightSum/=2 … without any if…else condition
same for heightReduced/=2

secondly the constraints are large for an int datatype, so changed them to long.

Here is your fixed AC Solution

https://www.codechef.com/viewsolution/25008412

But 21/2 would give me 10 and then subtracting 1 from it would give 9(where the correct ans was 10).That’s why I checked if the sum was an odd no, i would divide it by 2 and then add 1.Anyways, thanks a lot :slight_smile:

1 Like

here is my solution : https://www.codechef.com/viewsolution/24986606

My approach is, first I concentrated on odd numbers in a single array paired them with odd numbers of other array. after the odd odd pairs are processed, i processed remaining elements. to maintain the processed numbers i took two boolean arrays. i am getting wrong answer, can anyone suggest me where the issue is.
here is the link to my solution
https://www.codechef.com/viewsolution/24998969

i employed the logic in the editorial.
Its working for the given test case however i’m getting wrong answer. pls help.
https://www.codechef.com/viewsolution/25098941