 # CHECANDY-Editorial

PRACTICE
Editorialist: Yogesh Yogendra

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:

5
5 3 14 2 4

Impressed

### Explanation:

Chef will take [5,3,2,4]
Chefina will take 
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 = https://youtu.be/s4fsOuWOVOg , go and have a look.

# SOLUTION:

#include<bits/stdc++.h>
#define int    long long int
using namespace std;

int dp;
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;
}

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

1 Like