WIPL - Editorial

WIPL - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-3 Contest

Author & Editorialist: Shivam Singh
Tester: Radoslav Dimitrov

DIFFICULTY:

Easy

PREREQUISITES:

DP, Knapsack

PROBLEM:

Given N boxes of each of some height, you need to combine them to form 2 towers such that the height of each towers is at least K.

QUICK EXPLANATION:

The problem can be solved using knapsack.

  • Sort all the boxes in non-decreasing order.
  • Run a knapsack of the form dp[i][S]: minimum height greater than equal to S that can be made using only the last i boxes.
  • Define suf[i] as the sum of last i boxes.
  • 2 towers can be made using the last i boxes if suf[i] - dp[i][K] \geq K.
  • Find the max i for which the above condition is true, the answer(if it exists) will be n-i.

EXPLANATION:

Subtask 1
Knowledge of knapsack is not required for the first subtask. Create a dp array where dp[i][j][k] : the minimum number of boxes required to build two towers of height exactly i and j respectively, if we can only use the first k boxes. The recurrence relation for each height[i] will be :

dp[0][0][0] = 0;
int ans = INF;
// height is sorted in non-increasing order
for(int idx = 1; idx <= n; idx++){
    for(int i = MAX; i >= 0; i--)
        for(int j = MAX; j >= 0; j--){
            if(i >= height[idx-1])
                dp[i][j][idx] = min(dp[i][j][idx], dp[i - height[idx-1]][j][idx-1] + 1);
            if(j >= height[idx-1])
                dp[i][j][idx] = min(dp[i][j][idx], dp[i][j - height[idx-1]][idx-1] + 1);
        }
}

then after the whole computation check the minimum value of dp[i][j] for all i, j \geq k .
This solution of time complexity \mathcal O(N^{3}) will pass the first subtask.

Now coming to the final subtask.
For the rest of the editorial we will assume the heights are sorted in non-decreasing order.

Subtask 2
Main Observation
If we take t boxes then it is always optimal to take the t tallest boxes. One subset of these t boxes will be used to create the first tower and the remaining will be used for the second tower.

Create a dp array where dp[i][s] : minimum height greater or equal than s that can be reached using only the last i elements. Therefore dp[i][K] is the minimum height greater than equal to K that can be reached using only the last i elements, or using only the largest i elements. If the sum of heights of the last i elements - dp[i][K] is greater than equal to K means, if a certain subset(which dp[i][K] denotes) having a value of at least K is taken out, the remaining boxes still sum to at least K. Thus it will be possible to create 2 towers with the last i elements if this condition is true.

Calculate dp[i][K] for each i and find the largest i for which the above condition will be true, the least number of boxes required will be then n-i.
If no i exists such that suf[i] - dp[i][K] \geq K output -1.

Time complexity for this solution will be \mathcal O(N^{2}).

Tester’s Solution
The tester uses an optimised knapsack with bitsets. In that solution dp[i] denotes: is it possible to create a towers of height i from some of the boxes considered till now ?
Here ‘sum’ denotes the sum of height of the boxes considered till now and get_ones(L, R) returns a bitset with all 1’s from index L to R both included. The previous explanation follows from here. Iterate for each box i and check if it is possible to create a towers of height in the range [k, sum - k](denoted as L, R) provided R \geq L. If it is then answer exists and is equal to n - i.

Time Complexty - \mathcal O(N^{2}).

FURTHUR IMPROVEMENTS

It is interesting to note that every time while computing the dp we require
only the current and previous states. Creation of dp[N][K] can thus be minimised
to just dp[2][K], which decreases the memory used greatly. Implementing this solution is left as a task for the reader :slight_smile:

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h> 
using namespace std;
 
#define hs ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
const ll MAX = 1e9;
const ll N = 4001;
//
//
int dp[N][N];
int height[N], suffix[N];

void solve(){
    int n, k;
    cin>>n>>k;
    for(int i = 0; i < n; i++)
        cin>>height[i];
    sort(height, height + n);
    suffix[n] = 0;
    for(int i = n-1; i >= 0; i--)
        suffix[i] = suffix[i+1] + height[i];
    for(int i = 0; i <= n ; i++)
        for(int j = 0; j <= k; j++)
            dp[i][j] = MAX;

    dp[n][0] = 0;
    for(int i = n-1; i >= 0; i--){
        for(int j = k; j >= 0; j--){
            if(j <= height[i]){
                dp[i][j] = height[i];
                continue;
            }
            if(dp[i+1][j-height[i]] == MAX)
                dp[i][j] = MAX;
            else
                dp[i][j] = min(dp[i+1][j], dp[i+1][j-height[i]] + height[i]);
        }
    }
    for(int i = n-1; i >= 0; i--)
        if(suffix[i] - dp[i][k] >= k){
            cout<<n-i<<"\n";
            return ;
        }
    cout<<-1<<"\n";
}
int main(){ 
        hs;
        ll t;
        t=1;
        cin>>t;
        for (int i=1; i<=t; i++){
                solve();
         }
        return 0; 
}
Tester's Solution
#include <bits/stdc++.h>
#define endl '\n'

#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back

using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (int)1e4 + 42;

int n, k;
int w[MAXN];

void read() {
    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        cin >> w[i];
        chkmin(w[i], k);
    }
}

bitset<MAXN * 2> dp, ones, emp;

bitset<MAXN * 2> get_ones(int l, int r) {
    // beautiful
    return (((ones >> l) << l) << (2 * MAXN - r - 1)) >> (2 * MAXN - r - 1);
}

void print(bitset<MAXN * 2> bs) {
    for(int i = 0; i <= 2 * k; i++) {
        cout << bs[i];
    }
    cout << endl;
}

void solve() {
    dp = emp;
    for(int i = 0; i < MAXN * 2; i++) {
        ones[i] = 1;
    }
    
    // We can prove that we'll always use the largest M numbers
    sort(w, w + n);

    int sum = 0;
    dp[0] = 1;
    for(int i = n - 1; i >= 0; i--) {
        dp = dp | (dp << w[i]);
        sum += w[i];

        int L = k, R = min(sum - k, 2 * MAXN);
        if(L <= R && (get_ones(L, R) & dp).count()) {
            cout << n - i << endl;
            return;
        }
        
    }

    cout << -1 << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while(T--) {
        read();
        solve();
    }

    return 0;
}

VIDEO EDITORIAL:

As always, different approach is welcome in the comments :wink:

18 Likes

Very nice editorial. Much better than video.
I just have one confusion that how to prove that it won’t be Optimal instead of taking t tallest boxes we take any t boxes and make the solution?

5 Likes

Assume any solution is made of 2 sets S1 and S2 where sum of each is greater than or equal to K.
If this solution is not made of the T tallest boxes, then there must exist a box B whose weight is greater than some element B2 of S1 or S2 and B is not in S1 and S2.
In that case, an even greater sum can be obtained in S1 or S2 by swapping B with B2.

Therefore, if we have a solution using some N boxes which are not the N tallest boxes, there will always be a better solution that can be obtained. So it suffices to look at solutions made using only the tallest boxes, as no greater sum can be obtained in either box by swapping with an element which is not in any box.

4 Likes

Has anyone done this problem using greedy/bruteforce? Would love to see their solutions!

3 Likes

Yes I have done it using greedy

1 Like

Here’s my blog for this problem if anyone’s having trouble understanding the editorial.

11 Likes

My solution is also like this editorial but instead of sorting the heights in non-decreasing, I sorted in non-increasing order and then traversed from start, and kept all height combination less than <K in a set, and also kept track of minimum height combination >=K, (min_k), and if at any index prefixSum[i]-min_k >= k I returned the (i+1).
still in 10 days i couldn’t find what i was doing wrong.HELP.
my Solution:-CodeChef: Practical coding for everyone

Bro please tell me what is the prob with my code??? 3 test cases was failing or provide me the test cases.

class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes heresi
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++){
int n=sc.nextInt();
int k=sc.nextInt();
int[] list=new int[n];
for(int j=0;j<n;j++){
list[j]=sc.nextInt();
}

	    for(int j=0;j<n;j++)
	        list[j]=(-1)*list[j];
	    Arrays.sort(list);
	    for(int j=0;j<n;j++)
	        list[j]=(-1)*list[j];
	    /*for(int z:list)      
	        System.out.print(z+" ");*/
	        
	    int c=0,count=0;
	    int h1=0,h2=0;
	    while(true){
	        if(h1>=k && h2>=k){
	            System.out.println(count);
	            break;
	        } 
	        else if((h1<k || h2<k) && c>=n){
	            System.out.println("-1");
	            break;
	        }
	        int dh1,dh2,c1,c2;
	        dh1=h1+list[c];
	        dh2=h2+list[c];
	        c1=k-dh1;
	        c2=k-dh2;
	        if(c1<0 && c2<0){
	            if(c1>c2){
	                h1=h1+list[c];
	                count++;
	            }
	            else{
	                h2=h2+list[c];
	                count++;
	            }
	        }
	        else if(c1>=0 && c2>=0){
	            if(c1<c2){
	                h1=h1+list[c];
	                count++;
	            }
	            else{
	                h2=h2+list[c];
	                count++;
	            }
	        }
	        else if(c1>=0 && c2<=0){
	            h1=h1+list[c];
	            count++;
	        }
	        else{
	            h2=h2+list[c];
	            count++;
	        }
	        c++;
	    }
	}
}

}

1 Like

This problem can be solved with a recursive approach
https://www.codechef.com/viewsolution/41189741

3 Likes

Well explained. Thanks a lot!

81 27

21 50 45 50 39 14 34 17 40 28 8 21 27 35 16 31 37 44 24 39 39 16 24 47 41 7 19 32 4 27 8 22 26 3 38 30 30 37 13 35 30 18 6 7 18 19 3 4 12 40 40 17 21 29 29 11 34 13 41 3 37 14 22 29 30 25 8 10 12 18 42 39 34 45 11 49 29 27 19 39 16
Your answer is:
1
Correct answer is:
2

I ran it against my solution. I am not sure whether it will solve your problem. But anyway I have posted it. Another thing, that strikes is: How can “1” box ever be the answer. It has to be greater than 1. Hope you will find the error now. [Note: your code was good for small testcases(N<50)]. @devshiv

2 Likes

Very clean explanation. Thanks

I just changed Comparator
from
bool cmp(int a, int b) { return a >= b; }
to
bool cmp(int a, int b) { return a > b; }

and it got AC.and I don’t have the simplest clue why?

1 Like

Amazing Question, & Amazing Explanation, thanks, Authors!

1 Like

will you please share your code?
I want to see greedy approch…please

Anybody will you please help me out, where this approach is getting dumped

arr.sort(reverse=True)
mark, tracy, i = 0, 0, 0
while i < n:
    if mark < k:
        if mark + arr[i] > k:
            for j in range(i, n):
                # swapping elements so that the sum is closest to k
                if mark + arr[j] < k:
                    arr[i], arr[j-1] = arr[j-1], arr[i]
                    break
                elif mark + arr[j] == k:
                    arr[i], arr[j] = arr[j], arr[i]
                    break
        mark += arr[i]
        tracy += arr[i+1]
        i += 2
        
    elif mark >= k and tracy < k:
        tracy += arr[i]
        i += 1
        
    elif mark >= k and tracy >= k:
        print(i)
        break

I think this discussion should help:
comparator functions .
Have a look at the first 3 answers at least. Hope it helps. @devshiv

1 Like

Hi can anyone help point out the mistake in the following approach:

Reverse sorting the array and iterating over them. then taking two height variables and adding the loop variable to the minimum of the two heights. Keep looping till either both the heights are greater than K or number of elements in loop are exhausted.

Solution link

can anyone help me to find a problem in my solution it is passing some subtasks but fails in some?
#include

using namespace std;

void insertion_sort (long long int array_sort[], long long int size);
long long int find_smallest_element (long long int array_sort[],long long int index,long long int size);
void swap_value (long long int array_sort[],long long int i_1, long long int index_2);

int main()
{
int number_of_testcases;
cin >> number_of_testcases;
for (int abcd=0; abcd <number_of_testcases;abcd++)
{
long long int n,k;
cin >> n >> k;
long long int blocks[n];
for (long long int i=0; i<n; i++)
{
cin >> blocks[i];
}
long long int i=0;
long long int a=0;
long long int b=0;
for ( i; (a<k)||(b<k)&& i<n ; i++)
{
insertion_sort(blocks,n);
if (a<k)
{
if(a==0)
{
a+=blocks[n-1];
blocks[n-1]=0;
insertion_sort(blocks,n);
continue;
//cout << a << " \n";
}
long long int j=0;

            for ( j;a<k&&j<n;++j)
            {

               if (blocks[j]+a>=k||j==n-1)
               {
                   a=a+blocks[j];
                   blocks[j]=0;
                   //cout << a << "\n";
                   break;
               }

          //  cout << " " << j << "\n";
            }
        }
        else
        {
            if (b==0)
            {

            b+=blocks[n-1];
            blocks[n-1]=0;
            continue;
            insertion_sort(blocks,n);
            }
            long long int j=0;
            for ( j;b<k&&j<n;j++)
            {
               if (blocks[j]+b>=k||j==n-1)
               {
                   b=b+blocks[j];
                   blocks[j]=0;
                   break;
               }
            }
            //cout << j << "\n";
             //cout << b << "\n";
        }
    }
    if (a>=k&&b>=k)
    {
        cout << i << "\n";
    }
    else
    {
        cout << "-1\n";
    }
}

}

void insertion_sort(long long int array_sort[],long long int size)
{
for (long int i=0;i<size;i++)
{
long long int index =find_smallest_element(array_sort, i, size);
swap_value (array_sort, i, index);
}
}

long long int find_smallest_element(long long int array_sort[],long long int index, long long int size)
{
long long int index_of_smallest_value =index;
for (long int i = index +1; i<size;i++)
{
if (array_sort[i]<array_sort[index_of_smallest_value])
{
index_of_smallest_value=i;
}
}
return index_of_smallest_value;
}

void swap_value(long long int array_sort[], long long int i_1,long long int index_2)
{
long long int temp =array_sort[i_1];
array_sort[i_1]=array_sort[index_2];
array_sort[index_2]=temp;
}

//The above is the code I have tried to work with.
//I have done insertion_sort and then tried to optimally assign the values.
thanks in advance
https://www.codechef.com/viewsolution/41535464

here my solution somewhat does the same thing as yours.

the problem in this reverse sorting approach is that it won’t land the optimal solution every time.