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