CHECANDY-Editorial

editorial
1

PROBLEM LINK:

PRACTICE
Editorialist: Yogesh Yogendra

DIFFICULTY:

HARD

PREREQUISITES:

Dynamic Programming

PROBLEM:

Chef wanted to impress chefina so he took her to a candy shop.
Chef asked Shopkeeper to bring N Boxes of Candies. Each Box contain some number of candies.

Chef wanted to distribute the candies between chef & chefina, but their is one condition:

  1. All candies of each box can be given to either chef or chefina i.e
    For example:
    if their are 5 Boxes and each box contain some number of candies. Box = [5,3,14,2,4] then
    All candies of 1st box can be given to either chef or chefina
    All candies of 2nd box can be given to either chef or chefina and so on…
    If total candies can be equally distributed between Chef and Chefina, then Chefina will be impressed by chef otherwise no.
    You have to find if Chef can impress Chefina or not.

Input:

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N i.e total number of boxes
The Second line of each test case contains N space seperated integers i.e Total number of candies of each boxes.

Output:

Print “Impressed” without quotes if Chef is able to impress Chefina, otherwise print “Not Impressed” without quotes.

Constraints:

1 <= T <= 10
1 <= N <= 100
1 <= Total number of candies of each boxes <= 1000

Sample Testcase:

Input:

5
5 3 14 2 4

Output:

Impressed

Explanation:

Chef will take [5,3,2,4]
Chefina will take [14]
Impressed Because Candies are equally distributed.

EXPLANATION:

This question was basically the Partition Equal Subset Sum Problem.I have expained this question in a video, Link = Subset Sum Problem | Dp | Love Babbar DSA Sheet | Amazon | Adobe 🔥 | GFG | DP Solution - YouTube , go and have a look.

SOLUTION:

#include<bits/stdc++.h>
#define int    long long int
using namespace std;
 
int dp[1001][1001];
    int solve(int n,int a[],int s){
        if(n == -1){
             if(s == 0)
                return 1;
            return 0;
        }
        if(s<0)
            return 0;
        if(s==0)
            return 1;
        if(dp[n][s]!=-1) return dp[n][s];
        
        return dp[n][s] = solve(n-1,a,s-a[n]) || solve(n-1,a,s);
           
    }
    
    int equalPartition(int N, int arr[])
    {
        int s = 0;
        for(int i=0;i<N;i++) s += arr[i];
        
        if(s&1) return 0;
        s=s/2;
        dp[N][s];
        memset(dp,-1,sizeof(dp));
        return solve(N-1,arr,s);
    }


int32_t main() {
    
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int a[n];
        for(int i=0;i<n;i++) cin>>a[i];
        if(equalPartition(n,a)) cout<<"Impressed\n";
        else cout<<"Not Impressed\n";
    }  
    return 0;
}
2

You could have kept 1 \leq N, S \leq 10^5, S is the total number of candies.

1 Like