 # MOON - Editorial

Author: Kumar Raju
Editorialist: Kumar Raju

CAKEWALK

# PREREQUISITES:

Implementation, Math

# PROBLEM:

Given N items of value X and M items of value Y, divide the items into two sets S_1 and S_2 such that \sum s_1 = \sum s_2 .

# QUICK EXPLANATION:

You can find the answer by running two nested loops.

# EXPLANATION:

Let the two sets be denoted by S_1 and S_2.
Let (i,j) be the tuple denoting the number of elements valued X and Y respectively is S_1.
Therefore, the number of elements in S_2 will be (N - i, N - j).
Sum of S_1 = i \times x + j \times y
sum of S_2 = (N - i) \times x + (M - j) \times y
Thus, we need to find if there exists 2 non-negative integers i and j such that the following equation is satisfied:
(N - i) \times x + (M - j) \times y = i \times x + j \times y
We can check this by replacing i and j with all possible values using simple for loops.
Check the simple code below for more understanding.

The intended complexity for this problem is \mathcal{O}(N^2)

# EDITORIALIST’S SOLUTION:

Language used : C++

#include <bits/stdc++.h>
int main()
{
long long t, n, m, x, y, i, j, flag;
cin>>t;
while(t--)
{
flag = 0;
cin>>n>>m>>x>>y;
for(i = 0; i <= n; ++i)
for(j = 0; j <= m; ++j)
if( (n - i)*x + (m - j)*y == (i)*x + (j)*y )
flag = 1;
if(flag)
cout<<"YES\n";
else
cout<<"NO\n";
}
return 0;
}

Can explain me what will be the output for
1 0 0 0
0 1 0 0
For both it should be yes because Sweetness
Level for both is 0

Can you suggest a test case for which this O(n) solution is failing ?
MY WA CODE: https://www.codechef.com/viewsolution/30753489

“YES”

let the number of truffles with first elf be N_1 & number of candies be M_1 .
Hence total sweetness with 1st elf will be equal to N_1X+M_1Y
Now the combined total sweetness of both the elves will be NX+MY .Now inorder to have equal amounts of sweetness each elf is bound to have a total sweetness of (NX+MY)/2 .
so from above 2 relations we can say that
N_1X+M_1Y = (NX+MY)/2
2N_1X+2M_1Y=NX+MY
M1=(NX+MY-2N_1X)/2Y
Now what I have done is to iterate through all values of possible values of N_1 (from 0 to N) and for each N_1 I am checking if we get a non negative integral value of M_1 which is less than or equal to M if we get this kind of value of M_1 we print "YES" and return else print "NO" after checking all values of N_1.I have tackled all the corner cases of like X=0 ,Y=0…etc separately .

1 Like

Why doesn’t this approach work:
First check if the the total value=nx+my is divisible by 2
Second find gcd of x and y
Frame a linear diophantine eqn of the form:
ax+by=value/2
(The eqn will remain same for the second summation)
Third: check if (value/2) is divisible by gcd(x,y) for the above soln to have solns.
I don’t know why it doesn’t work