EQUALCOIN - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Soumyadeep Pal
Tester: Manan Grover
Editorialist: Taranpreet Singh

DIFFICULTY

Cakewalk

PREREQUISITES

None

PROBLEM

Chef has X coins worth 1 rupee each and Y coins worth 2 rupees each. He wants to distribute all of these X+Y coins to his two sons so that the total value of coins received by each of them is the same. Find out whether Chef will be able to do so.

QUICK EXPLANATION

Chef can only divide the coins equally only when the total worth of coins is even and either there’s at least one coin worth 1 or the number of coins worth 2 is even.

EXPLANATION

First of all, since the chef aims to divide the total value of coins into two equal parts, the total worth of all coins should be even. The total worth is X*1 + Y*2 = X+2*Y.

Hence, if X+2*Y is odd (which happens when X is odd), then it is not possible to divide coins.

Let’s assume that X is even. So X+2*Y is even as well. Let’s assume X+2*Y = 2*P for some P.

Two cases may arise

  • P is odd: We need at least two coins worth 1 since each son must receive at least one coin worth 1 to obtain an odd value sum. Example: for X = 0 and Y = 3, P = 3, but there’s no way to obtain odd sum with only coins worth 2.
  • P is even: It is possible to divide always.

Hence, we can generalize. We need

  • Total value (X+2*Y) to be even. AND
  • Either X \gt 0 or Y must be even.

Tip: For problems like this, it is worth trying all tests with say 0 \leq X, Y \lt 5 if facing any issues

Exercize

Prove that the following conditions are also a valid solution for this problem.

The answer is YES if either of the following is satisfied.

  • (X+2*Y) is multiple of 4
  • (X+2*Y) is multiple of 2 and X \gt 0

Exercize 2

Prove the correctness of my solution. Tip: I wrote conditions for NO case.

TIME COMPLEXITY

The time complexity is O(1) per test case.

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
using namespace std;

int main() {
  int t; cin >> t;
  while (t--) {
    int a, b;
    cin >> a >> b;
    int sum = a + 2 * b;
    if (sum % 4 == 0) {
      cout << "YES\n";
    } else if (sum % 2 == 0 && a > 0) {
      cout << "YES\n";
    } else {
      cout << "NO\n";
    }
  }
}
Tester's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define asc(i,a,n) for(I i=a;i<n;i++)
#define dsc(i,a,n) for(I i=n-1;i>=a;i--)
#define forw(it,x) for(A it=(x).begin();it!=(x).end();it++)
#define bacw(it,x) for(A it=(x).rbegin();it!=(x).rend();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lb(x) lower_bound(x)
#define ub(x) upper_bound(x)
#define fbo(x) find_by_order(x)
#define ook(x) order_of_key(x)
#define all(x) (x).begin(),(x).end()
#define sz(x) (I)((x).size())
#define clr(x) (x).clear()
#define U unsigned
#define I long long int
#define S string
#define C char
#define D long double
#define A auto
#define B bool
#define CM(x) complex<x>
#define V(x) vector<x>
#define P(x,y) pair<x,y>
#define OS(x) set<x>
#define US(x) unordered_set<x>
#define OMS(x) multiset<x>
#define UMS(x) unordered_multiset<x>
#define OM(x,y) map<x,y>
#define UM(x,y) unordered_map<x,y>
#define OMM(x,y) multimap<x,y>
#define UMM(x,y) unordered_multimap<x,y>
#define BS(x) bitset<x>
#define L(x) list<x>
#define Q(x) queue<x>
#define PBS(x) tree<x,null_type,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define PBM(x,y) tree<x,y,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define pi (D)acos(-1)
#define md 1000000007
#define rnd randGen(rng)
int main(){
  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  uniform_int_distribution<I> randGen;
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  #ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif
  I t;
  cin>>t;
  while(t--){
    I x,y;
    cin>>x>>y;
    if(x%2==0 && (y%2==0 || x>0)){
      cout<<"YES\n";
    }else{
      cout<<"NO\n";
    }
  }
  return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class EQUALCOIN{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int X = ni(), Y = ni();
        if(X%2 != 0 || (X == 0  && Y%2 == 1))pn("NO");
        else pn("YES");
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    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 EQUALCOIN().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. Suggestions are welcomed as always. :slight_smile:

Please include Python solutions too.