PROBLEM LINK: Chef and a New Home
Author: Pankaj Sharma
Tester: Abhishek Jugdar
Editorialist: Pankaj Sharma
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