Monday, January 11, 2021

Watching CPL | Codechef January Long Challenge 2021 | Dynamic Programming

Codechef: Question

Quick Explanation

Given an array A of size n containing boxes with height A1,A2,A3...AN. You are also given an integer K. Your task is to find the smallest number of boxes required to make two towers of height atleast K. You can use a box only once.

Hint 1

Dynamic Programming.

Hint 2

Subset Sum

Solution Approach

To understand this solution, you need to have a basic understanding of Dynamic Programming. But I'll try my best to simplify it for you.๐Ÿ˜€

So,Let's start. ๐Ÿ˜€

Ok,so let's try to simplify the question. Let's say we have an array with some values and an integer K, Now our task is to simply find if two subsets are present in that array with each atleast a sum of K. Also, we need to ensure that the length of subsets we find should have minimum length. Easy so far? Great.๐Ÿ˜Ž Let's take an example.

Given an array ,A=[3,2,1,4,6,12,9] and K=13.

Now the greedy approach that may come to mind is to sort the array so that we can get the boxes with larger height and hence we could minimise our answer. Correct. ๐Ÿ˜„

So, let's Sort the array.

A=[1,2,3,4,6,9,12]  , K=13

Ok ,now to make two subsets of sum=K=13, some of you may try the greedy approach again i.e to iterate from the A[n-1] to A[0] and consecutively find two subarrays of size K i.e S1=[12,9] and S2=[6,4,3] . The sum of length of subset is 2+3=5. But this is not an optimal approach.๐Ÿ˜• Why? Because one of the optimal answer for the above testcase is: S1=[1,12] and S2=[4,9], length=2+2=4 , which is less than the greedy approach. 


So, what is the optimal approach?

Dynamic Programming. Yes. The topic which scares most of us ๐Ÿ˜”,But it really shouldn't.


So what will we do?

Explanation

First of all we sort the array increasingly or non-increasingly,your choice. Then we iterate decreasingly i.e start from the largest value. While we iterate ,we keep the sum of array in a variable say, 'currsum' and we also store the value of current element into a list.

Then we iterate until we find the 'currsum' to be atleast 2*K. Why 2*K? Because the idea here is to store the array of sum atleast 2*K and check whether we can partition that array into two arrays of sum atleast K. Still having problem? Let's take an example.

Let's take the above example again.


Given an array ,A=[3,2,1,4,6,12,9] and K=13.

Let's Sort the array in descending order.

A=[12,9,6,4,3,2,1]  , K=13

Now Let's start iterating until we get sum>=2*k i.e 13*2=26. We will also store this element in a list.

Iteration 1:

list=[12]

sum=12

sum is less than 2*K=26.

Iteration2:

list=[12,9]

sum=21

sum is less than 2*k=26

Iteration 3:

list=[12,9,6]

sum=27

sum is greater than 2*k=26

Now we try to divide the array in two parts each of sum=k=13

As you can notice,we can't do that in above list. So we iterate again.

Iteration 4:

list=[12,9,6,4]

sum=31

sum is greater than 2*k=26

Now we again try to divide the array in two parts each of sum=k=13

As you can notice,we can do that in above list i.e list1=[12,4] ,list2=[12,6]

Hence this is our answer.๐Ÿ’ช If we try to iterate again then the size of that list will increase 

which will eventually lead to increase in our answer. Hence we don't iterate again once we know that array can be partitioned.


Also to check if list contains 2 arrays of sum k, we use dynamic programming. You should first check out Subset Sum Problem for better understanding.


I hope the approach is clear. Let's move on to the coding part.๐Ÿ˜Œ


 



 

The above code can be understood easily. If any problem arises,please let me know in comments:)

The next part can be a bit tricky. 





Our dp function has following parameters: 

list->array containing elements

n->size of array

k->sum required

sum->variable to store the current sum,initially 0

dp->2D matrix for memoization

total-> total sum of array


First let's discuss about our base cases:

1- In out first base case we check whether our current sum is greater than or equal to k,if yes that means we have found a subset of sum k,then in next we check if we subtract that sum from totalsum, will we get another sum>=k ,if yes then voila! you have your answer,return true. Else return false.

2- Our second test case is a basic one . We check if we have reached end of array or not. If we reached the end and then it's sure we haven't yet got our answer .Hence we return false.


Next let's discuss about our recursive calls,or we can say,our choices.

There are two choices you can perform in the array, either take the current element or don't take it. That's it.

In this we take the element.

boolean a = checkSubset(list, n - 1, k, sum + list.get(n - 1), dp, total);

In this we do not

boolean b = checkSubset(list, n - 1, k, sum,dp, total);


Hence we get our answer๐Ÿ˜ƒ Hope you all like this blog. 

Thank You!



32 comments:

  1. Nice explanation sir๐Ÿ˜Š๐Ÿ˜Š

    ReplyDelete
  2. After reading this, I have developed "Understanding".

    ReplyDelete
  3. Nicely explained ๐Ÿ‘.
    Keep it up bro

    ReplyDelete
  4. Great work. Hands off to your effort and explaination.

    ReplyDelete
  5. Can you please explain the ans = a|b; and the next part in checkSubset function in your code mention in the blog. Please.

    ReplyDelete
    Replies
    1. In a and b variable,we get either true or false i.e either the answer is found or it isn't found.So the logic behind putting "or" is if answer is found either in a or b,we 'or' both the values ,so ultimately if we have got the answer true,'or' will make sure we return the true value.

      The next part is simply memoization i.e we are storing our answer in dp[][] so that we don't have to calculate it again.

      Delete
  6. how can we prove the claim true that our most efficient answer will be from sub-array of suffix sum from end ?

    ReplyDelete
  7. Can anyone tell me why I am getting wrong ans for this testcase:-
    1
    4 5
    2 10 4 9
    code C++ :-
    #include
    using namespace std;

    #define ll long long
    #define pb push_back
    #define endl "\n"
    #define fast std::ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    #define MOD (int) 1e9+7

    bool dp[4050][10001];

    bool checkSubset(vectorv1,int n,int k,int sum1,int total)
    {
    if(sum1>=k)
    {
    if((total-sum1)>=k)
    return true;
    else
    return false;
    }
    if(n==0)
    return false;
    if(dp[n][sum1]!=-1)
    {
    if(dp[n][sum1]==1)
    return true;
    return false;
    }
    bool a=checkSubset(v1,n-1,k,sum1+v1[n-1],total);
    bool b=checkSubset(v1,n-1,k,sum1,total);
    bool ans= a|b;
    if(ans)
    {
    dp[n][sum1]=1;
    }
    else
    dp[n][sum1]=0;
    return a|b;
    }

    signed main()
    {

    fast;
    int t;
    cin>>t;
    while(t--)
    {
    int n,k;
    cin>>n>>k;
    int arr[n];
    for(int i=0;i>arr[i];
    sort(arr,arr+n);
    int sum=0;
    int flag=0;
    vectorv;
    int size=0;
    memset(dp,-1,sizeof(dp));
    for(int i=n-1;i>=0;i--)
    {
    sum+=arr[i];
    v.pb(arr[i]);
    size++;
    if(sum>=2*k)
    {
    // cout<<size<<" ";
    bool res=checkSubset(v,size,k,0,sum);
    // cout<<res<<endl;

    if(res)
    {
    cout<<size<<endl;
    flag=1;
    break;
    }
    }

    }
    if(flag==0)
    cout<<"-1"<<endl;

    }

    }

    ReplyDelete
  8. the explanation is awesome , but idk why i am getting TLE in subtask 2 , can anyone help..
    https://www.codechef.com/submit/WIPL

    ReplyDelete
  9. This comment has been removed by the author.

    ReplyDelete
  10. Great explanation, but i'm getting TLE in a subtask.
    Can you please tell me the mistake in my code?
    link - https://www.codechef.com/viewsolution/41668420

    ReplyDelete
  11. 1xbet korean - What is 1xbet korean
    1xbet korean. เธซเธฒเน€เธ‡ิเธ™เธญเธญเธ™เน„เธฅเธ™์ If your casino has 1xbet korean 1xbet Asian poker games, blackjack, roulette, and slots that provide ๋ฐ”์นด๋ผ ์‚ฌ์ดํŠธ Asian players the opportunity to

    ReplyDelete

Watching CPL | Codechef January Long Challenge 2021 | Dynamic Programming

Codechef:  Question Quick Explanation Given an array A of size n containing boxes with height A1,A2,A3...AN. You are also given an integer K...