# PROBLEM LINK: Chef and a New Home

* Author:* Pankaj Sharma

*Abhishek Jugdar*

**Tester:***Pankaj Sharma*

**Editorialist:**# DIFFICULTY:

EASY - MEDIUM.

# PREREQUISITES:

DP

# PROBLEM:

Find no of solutions of given equation . Each element of solution must belongs to [1,0,-1].

Also count of -1 element in solution doesnot exceeds k.

# QUICK EXPLANATION:

Problem can be solved by making a 3 dimensional DP as dp[n][sum][k].

DP transition are as follows

## Check

```
if k>0
dp[index][cur_sum][k]=dp[index - 1][cur_sum+arr[index]][k - 1]+dp[index - 1][cur_sum-arr[index - 1]][k]+dp[index - 1][cur_sum][k]
else
dp[index][cur_sum][k]=dp[index - 1][cur_sum+arr[index]][k - 1]+dp[index - 1][cur_sum][k]
dp[index[[curr_sum][k] -> no. of ways to achieve curr_sum using only 1,...i array elements and only $k$ $-1$ symbols have been used.
```

# EXPLANATION:

We have given following equation :

a_1*m_1+a_2*m_2+a_3*m_3+.............+a_N*m_N = S

We need to find no of values of [a_1,a_2,a_3,......a_N] such that above equation will be satisfied.

Now a good observation is each a_i belongs to [1,0,-1]

It means each m_i must belongs to [m_i,0,-m_i]

Letβs denotes current sum as cur

It also means each m_i has 3 choices either

- We can add m_i to our current sum -> cur+=m_i
- We can substract m_i to our current sum -> cur+=m_i if k>0
- We dont take m_i to our current sum -> cur+=0

We can apply recursion to solve this problem .

Each m_i has 3 choices .

But recursive code has O(3^n) complexity which will give timeout.

So we have to use DP here since the problem satisfies both optimal substructure and overlapping subproblems property.

So we just need to memoizised/store the result of overlapping subproblems.

Lets try to figure out dimension/state of our DP

What is max value of given equation?

## Tap to view

ans = \sum_{i = 1}^{N} m_i

Which can be upto 300.

What is minimum value of given equation ?

## Tap to view

ans = \sum_{i = 1}^{N} -m_i

Which can be upto -300.

Similarly

Max value of k=N because we needed only N β**-1**β values to make all elements negative

Lets say sum=\sum_{i = 1}^{N} m_i

If S > sum then there exist 0 solutions because S cannot be greater than sum of array elements

Now if we make DP[n][sum][k]

But here sum state can be equal to some negative value

Consider -1 + -1 + -1 + 3 =0 It means we need intermediate sum as -2 which can also lead to a valid solution.

so we take sum state of DP as 2*sum

It means we have shifted all values by sum.

0 becomes sum

1 becomes sum+1

-1 becomes sum-1

Now lets consider some base cases

Base case

## Tap to view

```
if n==0:
if sum==required_sum
return 1 // we have found a solution
else
return 0 // we coundn't find a solution
```

## Memoized Code

```
int find_solution(int cur_sum, int index, int k, vector<int> &arr, int required, vector<vector<vector<int>>> &dp)
{
if (index == 0)
{
if (cur_sum == required)
return 1;
else
return 0;
}
// if dp array not equal to -1 means we have already calculated the result so just return it
if (dp[index][cur_sum][k] != -1) return dp[index][cur_sum][k];
// modA(a,b)=(((a%MOD)+(b%MOD))%MOD) to avoid overflow
int temp = modA(find_solution(cur_sum + arr[index - 1], index - 1, k, arr, required, dp) , find_solution(cur_sum, index - 1, k, arr, required, dp));
if (k > 0)
temp = modA(temp, find_solution(cur_sum - arr[index - 1], index - 1, k - 1, arr, required, dp));
// store each value in dp array
return dp[index][cur_sum][k] = temp;;
}
```

# Time Complexity:

The time complexity is O(N*Sum*K) per test case.

where N=number of elements

Sum=Sum of array elements

K=No of values with -1

# SOLUTIONS:

## Editorialist's Solution

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define int ll
#define MOD 1000000007
#define modA(a,b) (((a%MOD)+(b%MOD))%MOD)
int find_solution(int cur_sum, int index, int k, vector<int> &arr, int required, vector<vector<vector<int>>> &dp)
{
// base cases
if (index == 0)
{
if (cur_sum == required)
return 1;
else
return 0;
}
if (dp[index][cur_sum][k] != -1) return dp[index][cur_sum][k];
// modA(a,b)=(((a%MOD)+(b%MOD))%MOD) to avoid overflow
int temp = modA(find_solution(cur_sum + arr[index - 1], index - 1, k, arr, required, dp) , find_solution(cur_sum, index - 1, k, arr, required, dp));
if (k > 0)
temp = modA(temp, find_solution(cur_sum - arr[index - 1], index - 1, k - 1, arr, required, dp));
return dp[index][cur_sum][k] = temp;;
}
signed main()
{
int t;
cin >> t;
while (t--) {
ll n;
cin >> n;
int sum = 0;
vector<int> arr(n);
for (int i = 0; i < n; i++)
{
cin >> arr[i];
sum += arr[i];
}
int S, k;
cin >> S >> k;
int ans = 0;
// S cannot be greater than sum of array
if (S > sum)
{
cout << 0 << "\n";
continue;
}
k = min(n , k);
vector<vector<vector<int>>> DP(n + 1, vector<vector<int>>(2 * sum + 1, vector<int>(k + 1, -1)));
ans = find_solution(sum, n, k, arr, S + sum, DP);
cout << ans << "\n";
}
}
```

# BONUS:

- Solve the same problems using Tabulated dp.
- What if 1 \leq a_i \leq 10^9
- Can you reduce space complexity of DP solution for same problem
- What if K \geq N always hold true.

Please give me suggestions if anything is unclear so that I can improve. Thanks