TWOGRS - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Hasan

Tester: Roman Bilyi

Editorialist: Taranpreet Singh

DIFFICULTY:

Simple

PREREQUISITES:

Basic Maths.

PROBLEM:

Given three integers A, B and C, you have a multiset which contains A copies of 1, B copies of 2 and C copies of 3. Can this multiset be partitioned into two multisets with equal sum?

EXPLANATION

First of all, the sum of values in given multiset is S = A+2*B+3*C. If this is an odd value, there’s no way we can partition this set, as no two equal integers can have odd sum.

Now, We’ll try to make a partition with sum S/2 using elements of original multiset, if the sum of one partition is S/2, the sum of other partition is S - S/2 = S/2 which is what we need. So, the question is, Can we make a multiset using at most A copies of 1, at most B copies of 2 and at most C copies of 3 with sum S/2.

The greedy approach is not optimal here (trying to include maximum occurrences of a value as we can), as suppose S/2 = 10, A = 0, B = 4, C = 4, S/2 = 10 = 2*2+3*3. Here, if we try to include three copies of 3, we need one additional 1 which we do not have. So, we need to think of something else.

Now, we can see that lcm(1, 2, 3) = 6. So, including two copies of 3 is same as including three copies of 2, both of which are same as including six copies of 1. Generalizing this, we can see that including x copies of 3 and y copies of 2 is same as including x-2 copies of 3 and y+3 copies of 2. So we can be slightly greedy here, trying largest 6/3 = 2 values of x such that x*3 \leq S/2 (largest value of x is min(C, (S/2)/3) and now, try to obtain S/2 - x*3 as sum of at most B copies of 2 and at most A copies of 1. Now, similarly we can try largest allowed values of y = min(B, (S/2 - x*3)/2). If S/2 -x*3 - y*2 \leq A We have found a way to write S/2 as the sum of at most A copies of 1, at most B copies of 2 and at most C copies of 3.

In general, trying the last few values for x and y would be enough. Or even writing the brute force is likely to find a solution fast enough, with large values of A B and C assuming A+2*B+3*C is even.

TIME COMPLEXITY

The time complexity for this problem is O(C) per test case where C is some small constant depending upon approach.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int fix(int X, int limit) {
	if (X <= limit) return X;
	if ((X - limit)%2 == 0) return limit;
	return limit - 1;
}
int main() {
	int t; cin >> t;
	while(t--) {
	    int A, B, C;
	    cin >> A >> B >> C;
	    A = fix(A,7), B = fix(B, 4), C = fix(C,4);
	    int sum = A + B + C;
	    bool ok = false;
	    for(int mask = 0; mask < (1 << sum); mask++) {
	        int total = 0;

	        for(int j = 0; j < sum; j++) {
	            int mult = 1;
	            if (mask & (1 << j)) mult = -1;

	            if (j < A) total += mult * 1;
	            else if (j < A+B) total += mult * 2;
	            else total += mult * 3;
	        }

	        if (total == 0) {
	            ok = true;
	            break;
	        }
	    }

	    if (ok) cout << "YES\n";
	    else cout << "NO\n";
	}

	return 0;
}
Tester's Solution
#include <iostream>
#include <assert.h>
using namespace std;

int T;
int A,B,C;

int main(){
	//freopen("0.in.txt","r",stdin);
	//freopen("00o.txt","wb",stdout);
	cin>>T;
	assert(1<= T && T<=1000);
	while(T--){
		cin>>A>>B>>C;
		assert(0 <= A && A<= 1000000);
		assert(0 <= B && B<= 1000000);
		assert(0 <= C && C<= 1000000);
		assert(A+B+C>=1);
		while(A >= 30){
			A -= 2;
		}
		while(B >= 30){
			B -= 2;
		}
		while(C >= 30){
			C -= 2;
		}
		if( (A + 2* B + 3 * C) % 2){
			cout<<"NO"<<endl;
			continue;
		}
		bool ok=false;
		for(int i=0;i<=A;i++){
			for(int j=0;j<=B;j++){
				for(int k=0;k<=C;k++){
					if(i + 2 * j + 3 * k  ==  (A + 2* B + 3 * C) / 2){
						ok=true;
					}
				}
			}
		}
		if(ok){
			cout<<"YES"<<endl;
		} else {
			cout<<"NO"<<endl;
		}
	}
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class TWOGRS{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int a = ni(), b = ni(), c = ni();
	    int sum = a+b+b+c+c+c;
	    if(sum%2 == 1)pn("NO");
	    else{
	        sum /= 2;
	        boolean yes = false;
	        for(int cc = Math.min(sum/3, c), j = 0; cc >= 0 && j < 2; j++, cc--){
	            int ssum = sum-cc*3;
	            for(int bb = Math.min(ssum/2, b), jj = 0; bb >= 0 && jj < 3; jj++, bb--){
	                if(ssum-bb*2 <= a)yes = true;
	            }
	        }
	        pn(yes?"YES":"NO");
	    }
	}
	//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 TWOGRS().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:

8 Likes

what is happening in setter’s solution?

Setter, for large values of A, B and C, used the fix function to bring them to lower values without affecting answer and then used Knapsack DP.

1 Like

I am talking about the most weird part,where it is looping over 1<<sum (2^sum) , isn’t it way big?

Due to fix function, sum never exceeds 15.

ohhh, ok.
thanks for replying.

1 Like

A simpler solution with a little bit more maths to avoid almost all computation:

First note if N=a+2b+3c is odd we can say no straight up

Next, assume N is even. If a,b,c are all positive then we can say yes as we split all but one of each 1,2,3 into two sets greedily with a difference of 0 or 2. Then split the 1 2 3 as 1 2 |3 or 1 3 |2 for these differences.

So all we need to do is check when at least one of a,b,c is 0.

If two are zero this is easy - yes when we have a,b or b,c=0 check if b is even otherwise

If one is zero we need to think a bit more.

c=0: always yes as we then have at least 2 ones. Split the twos then split the ones.
b=0: Split the threes, then if we have 1 one we lose -> No. If we have at least 2 we can split them to balance things.
a=0: Similarly to b=0, One 2 and we lose, more and we win.

That’s all of the cases, so just write an if statement to remove the Nos and otherwise say yes.

My solution

15 Likes

Sorry if this is a dumb question but where did the fixed constants {7,4 ,4} in the function fix() come from?

3 Likes

@coulson72 can you explain it more clearly…as your code seems much simple …
i just wanted to know how did you found that if a+2b+3c is even then there will always be a chance of yes provided all of them are non zero

1 Like

Will you please elaborate more simply.
Please.!

The tester’s solution is the clearest.

What is the logic behind while(a>=30) a-=2; (same for b and c) in testers solution

6 Likes

Can anyone please suggest a test-case where this solution is wrong. It is checking if the values of a,b,c are odd or even.

 `int main(){
    	int t,a,b,c;
    	int d,e,f;
    	cin>>t;
    	while(t--){
    		cin>>a>>b>>c;
    		d=a%2;
    		e=b%2;
    		f=c%2;
    		if((a+(b*2)+(c*3))%2!=0)
    			cout<<"NO"<<"\n";
    		else if( (d && e && f) || (!d && !e && !f ) )
    			cout<<"YES"<<"\n";
    		else if( !d && !f && e && a>0)
    			cout<<"YES"<<"\n";
    		else if( d && !e && f && b>0)
    			cout<<"YES"<<"\n";
    		else cout<<"NO"<<"\n";
    	}
    	return 0;
    }`

can someone explain in tester solution why he did while(a>=30)a=a-2; ??

4 Likes

This is the easiest I can explain guys -

1] If the sum(1*a+2*b+3*c==even) of all numbers is even, we check for something , else (Answer–>No).
(If sum is even, then only a set can be divided into 2-equal sets, agreed?)

2]If sum is even, and all a,b,c are positive. Answer is always Yes(you can try it yourself).

3)If sum is even and a=0 and c=0, just check the value of 'b'.

4)If sum is even, a=1 and c=odd number and b=0, answer is No.

5)If sum is even, b=1 and c=even number and a=0, answer is No.

6)For all others, answer is yes.

14 Likes

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int a,b,c,to,ans=0;
cin>>a>>b>>c;
to=a+2b+3c;
if(to&1)
ans=0;
else if((a+b+c)==1)
ans=0;
else if(a==0&&c==0&&(b&1))
ans=0;
else
{
if(a!=0)
{ to=to/2;
to=to-3min(c,to/3);
to=to-2
min(b,to/2);
if(to<=a)
ans=1;
else
ans=0;
}
else
{
to=to/2;
to=to-3*min(c,to/3);
if(to/2<=b)
ans=1;
else
ans=0;
}
}
if(ans==0)
cout<<“NO”<<endl;
else
cout<<“YES”<<endl;

}

}
Why i am not getting ac??? Pls suggest me.

Why is this approach wrong?

#include <bits/stdc++.h>
using namespace std;

//sums an array of size 3
int sum_arr(int arr[]){
return arr[0] + (2arr[1]) + (3arr[2]);
}

int main(){
int T,A,B,C;
cin>>T;
while(T–){
cin>>A>>B>>C;
int arr_1[3]{0};
int arr_2[3]{0};
arr_1[0]=max(A/2,A-A/2);
arr_1[1]=max(B/2,B-B/2);
arr_1[2]=max(C/2,C-C/2);
arr_2[0]=min(A/2,A-A/2);
arr_2[1]=min(B/2,B-B/2);
arr_2[2]=min(C/2,C-C/2);
int sum_1=sum_arr(arr_1);
int sum_2=sum_arr(arr_2);
int diff=sum_1 - sum_2;
if(diff%2==1) cout<<“NO\n”;
else{
if(diff==0)cout<<“YES\n”;
else if(diff==2) {
if(arr_1[0]>=1)cout<<“YES\n”;
else cout<<“NO\n”;
}
else if(diff==4){
if(arr_1[0]>=2 || arr_1[1]>=1)cout<<“YES\n”;
else cout<<“NO\n”;
}
else if(diff==6) cout<<“YES\n”;
else cout<<“NO\n”;
}
A=B=C=0;
}
return 0;

}

Sum is even ? Lol. I wish you best of luck with basic +/- in maths :slight_smile:
(1+2x5+3x4====odd)

my bad i thought u were saying sum of a b c

1 Like

here is my approach ,i check whether i can make the nearerst even or not
https://www.codechef.com/viewsolution/26747330