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!