MOON - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Kumar Raju
Editorialist: Kumar Raju

DIFFICULTY:

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;
}
2

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

3

Can you suggest a test case for which this O(n) solution is failing ?
MY WA CODE: CodeChef: Practical coding for everyone

4

“YES”

5

Could you elaborate your logic so that I can help you debug?

6

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
7

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
Please help!!!