# PROBLEM LINK: Chef and a New Home

Author: Pankaj Sharma
Tester: Abhishek Jugdar
Editorialist: Pankaj Sharma

EASY - MEDIUM.

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

1. We can add m_i to our current sum -> cur+=m_i
2. We can substract m_i to our current sum -> cur+=m_i if k>0
3. 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:

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

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

2 Likes

I guess under the quick explanation DP transition , it should be dp[index-1][][] and not dp[index][][] on the RHS

If not, when will the problem be available for practice?

Hi , we have requested Codechef to move the problems to practice section as soon as possible. Although it may some time to get reflected on the website. Appreciate your patience!

2 Likes

Cool thanks. And I really appreciate the problemset in this contest. Great job!

1 Like

Glad you liked the Problem Set !

Thanks for pointing out. Fixed it!

Can anyone help me figure out mistakes in this code?
https://www.codechef.com/viewsolution/34570267