COCR103 - Editorial

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

  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 :slight_smile:

3 Likes

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

Can you please give the link to the practice section?
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 ! :innocent:

Thanks for pointing out. Fixed it!

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