Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerEarth Buying items problem solution

YASH PAL, 31 July 2024
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

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 solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes