HackerEarth Buying items problem solution

In this HackerEarth Buying items problem solution There are n different types of objects. You want to buy atleast one instance of each type of object. There are m people , each of them sells one set of objects at a certain price (price is for the set).

Each of these m people sells either nothing or all the objects in the set he has. Information of these m sellers is represented by matrix M of size m * n . if M(i,j) = 1, it means that ith seller has one jth type of object in his set, otherwise M(i,j) = 0. The ith seller will sell set of all his objects at price Ci.

You want to buy at least one object of each type (it is guaranteed that it is always possible to do so). Find the minimal cost needed to pay to achieve it.

HackerEarth Buying items problem solution.

# include <bits/stdc++.h>
using namespace std;
# define fi cin
# define fo cout
# define x first
# define y second
# define ll long long
# define mp make_pair
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int main(void)
{
    int n,m;
    fi>>n>>m;
    if (n <= 23)
    {
        static ll D[1 << 23];
        const int N = 1 << n;
        for (int i = 1;i < N;++i)
            D[i] = 1e18;
        static int M[503];
        static int C[503];
        for (int i = 0;i < m;++i)
        {
            for (int j = 0;j < n;++j)
            {
                int v;
                fi>>v;
                M[i] |= v * (1 << j);
            }
            fi>>C[i];
        }
        for (int mask = 0;mask < N;++mask)
            for (int i = 0;i < m;++i)
                smin(D[M[i] | mask],D[mask] + C[i]);
        if (D[N - 1] != 1e18)
            fo << D[N - 1] << 'n';
        else
            fo << "-1n";
    }
    else
    {
        static bitset < 505 > M[505];
        static int C[505];
        for (int i = 0;i < m;++i)
        {
            for (int j = 0;j < n;++j)
            {
                int v;
                fi>>v;
                if (v) M[i][j] = 1;
            }
            fi>>C[i];
        }
        const int N = 1 << m;
        ll ans = 1e18;
        for (int mask = 0;mask < N;++mask)
        {
            ll cost = 0;
            static bitset < 505 > W;
            W.reset();
            for (int i = 0;i < m;++i)
                if ((mask >> i) & 1)
                    W |= M[i],cost += C[i];
            if (W.count() == n)
                smin(ans,cost);
        }
        if (ans != 1e18)
            fo << ans << 'n';
        else
            fo << "-1n";
    }
    return 0;
}

Second solution

import sys
n,m=map(int,raw_input().split());
item = [[0 for j in range(0,n+1)] for i in range(0,m)];
for i in range(0, m):
    item[i]=map(int,raw_input().split());
mask= [0 for i in range(0,m)];
for i in range(0,m):
    for j in range(0,n):
        mask[i]=mask[i]+(item[i][j]<<j);
ALL = (1<<n)-1;
if m>21:
    dp=[-1 for j in range(0,1<<n)];
    dp[0]=0;
    for i in range(0,m):
        for j in reversed(range(0,1<<n)):
            if dp[j]!=-1:
                nex= (j|mask[i]);
                cost=dp[j]+item[i][n];
                if dp[nex]==-1 or dp[nex]>cost:
                    dp[nex]=cost;
    if dp[(1<<n)-1]==-1:
        exit(1);
    print dp[(1<<n)-1];
else:
    ans=-1;
    for i in range(0,1<<m):
        rng=0;
        total=0;
        for j in range(0,m):
            if (i>>j)&1:
                rng=rng|mask[j];
                total=total+item[j][n];
        if rng==ALL:
            if ans==-1 or ans>total :
                ans=total;
    if ans==-1:
        exit(1);
    print ans;###

coding problems