How many of you solved WCPL question

1

if you solved WCPL QUE USING BIT MASKING PLEASE SHARE YOUR CODE I WANT TO KNOW WHERE MY MISTAKE IS.

2

Maybe you mean WIPL? :slight_smile:

1 Like
4

I did it rec + memo
Let me know if it is useful

#include <bits/stdc++.h>
using namespace std;
int dp[4010][4010];
int box(int *arr, int buf1, int buf2, int n) {
    if (buf1 <= 0 && buf2 <= 0)
        return 0;
    if (n < 0)
        return 6000;

    if (buf1 <= 0 || buf2 <= 0) {
        if (buf1 <= 0) {
            if (dp[0][buf2] > 0)
                return dp[0][buf2];
            int x = 1 + box(arr, buf1, buf2 - arr[n], n - 1);
            dp[0][buf2] = x;
            return x;
        }
        if (buf2 <= 0) {
            if (dp[buf1][0] > 0)
                return dp[buf1][0];
            int x = 1 + box(arr, buf1 - arr[n], buf2, n - 1);
            dp[buf1][0] = x;
            return x;
        }
    }
    if (dp[buf1][buf2] > 0)
        return dp[buf1][buf2];
    int x = min(1 + box(arr, buf1 - arr[n], buf2, n - 1),
                1 + box(arr, buf1, buf2 - arr[n], n - 1));
    dp[buf1][buf2] = x;
    return x;
}
void solve() {
    long long int n, k;
    cin >> n >> k;
    int arr[n];
    for (long long int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr, arr + n);
    for (int i = 0; i <= 4005; i++)
        for (int j = 0; j <= 4005; j++)
            dp[i][j] = -1;
    int x = box(arr, k, k, n - 1);
    if (x > 5000)
        cout << -1 << "\n";
    else
        cout << x << "\n";
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}
2 Likes
5

can you explain it?

6

sorry yes Watching CPL this one

9

using dp is great but i was wondering can we solve this problem only using bit masking i tried some thing but not even one tc passes

#include
#include
#include
#include
#define ll long long int
#include
#define mod 1000000007
using namespace std;
int main()
{
ll tc;
cin>>tc;
while(tc–)
{
int n=2;
ll size,k,sum=0,chec=0,max=-1,count=0,no=0,res=1;
cin>>size>>k;
k=(2*k);
ll arr[size];
for(ll i=0;i<size;i++)
{
cin>>arr[i];
sum+=arr[i];
}
if(sum==k)
{
cout<<size;
}
else if(sum<k)
{
cout<<"-1";
}

    else
    {
    for(ll i=0;i<(1<<size);i++)
    {
        count=0;
        chec=0;
        for(ll j=0;j<size;j++)
        {
            if(i&(1<<j))
            {
                chec+=arr[j];
                count++;
                if(chec>=k&&res==1&&count>1)
                {
                    res=-1;
                    no=count;
                    count=0;
                    chec=0;
                }
                 if(chec>=k&&count<no&&res==-1&&count>1)
            {
                no=count;
                chec=0;
                count=0;
            }
            }
        }
        }
    }
    cout<<no<<endl;
}
return 0;

}

10

See first sort an array. Then run knapsack on it. easy
U need min boxes so if n < 0 then we return 6000;
Because max n given is 5000.
if one box becomes zero then we select 2nd one… u got the point right ?

1 Like