int minSum(vector& a, int k) {
priority_queue<int,vector> pq(a.begin(),a.end());
while(k–)
{
int p = pq.top();
pq.pop();
pq.push(p/2);
}
int sum = 0;
while(!pq.empty())
{
sum += pq.top();
pq.pop();
}
return sum;
}
int main()
{
int n, k,arr;
cin>>n>>k;
vector v1;
for (int i=0;i<n;i++)
{
cin>>arr;
v1.push_back(arr);
}
int result=minSum(v1, k);
cout<<result;
return 0;
}
You have to maintain a priority queue for accessing the largest element in O(1) time. So initially, we have to enter all the integers in the priority queue. Now, we can minimize the sum to the least only by performing the operation (floor(x/2)) on the largest interger. So in each opeation, we first store the largest integer in a variable and pop the top interger. Then divide the variable by 2 and push the updated value back in the priority queue. Perform this operation K times. At last, pop the elements and get their minimized sum. (Overall complexity : O(nlogn)
And one more important thing…the sum should be stored in a long long int type variable otherwise it gives WA.
In my set there was a problem “Count Pairs”, Has any one done that?
Rest were Minimize Sum(done), Constellations(done), Hedger was 01 knapsack problem on submitting it showed memory limit exceeded or TLE.
I think this solution will also got accepted for minimize the sum
code
#include <bits/stdc++.h>
using namespace std; #define ll long long int #define ld long double #define pb push_back #define mp make_pair #define fi first #define se second #define mod 1000000007 #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
int main()
{
fastio;
ll n,s=0,i,k;
cin>>n>>k;
ll a[n];
for(i=0;i<n;i++)
cin>>a[i];
As i said Hedger showed MLE when using efficient approach probably because range of W was in 10^6 if you would like to know then go through problem after reading 01 knapsack.
Can you share your MLE code? What I thought was the problem was variation of unbounded knapsack where the catch is we can take fixed K amount of any item and not infinite number of any item.Correct me if I am wrong.
Yes, we can take any stock depending on the profit it generates for <=K times such that our total cost doesn’t exceeds total amount we have that is W.I am not sure of credibility as i just passed sample cases but it may help you.
Take the code for reference:
def knapSack(W, wt, val, n):
K = [[0 for x in range(W + 1)] for x in range(n + 1)]
# Build table K[][] in bottom up manner
for i in range(n + 1):
for w in range(W + 1):
if i == 0 or w == 0:
K[i][w] = 0
elif wt[i - 1] <= w:
K[i][w] = max(val[i - 1]
+ K[i - 1][w - wt[i - 1]], K[i - 1][w])
else:
K[i][w] = K[i - 1][w]
return K[n][W]
tCases = int(input())
for _ in range(tCases):
n1, k1, W1 = map(int, input().split())
wt1 = list(map(int, input().split()))
profit = list(map(int, input().split()))
newWt = []
newVal = []
val1 = []
for i in range(n1):
tempVal = wt1[i]*profit[i]/100
val1.append(tempVal) #Profit list is made
for i in range(n1):
for j in range(k1):
newWt.append(wt1[i])
newVal.append(val1[i]) #append each value weight and profit K times
n1 *= k1
print(round(knapSack(W1, newWt, newVal, n1)))
can anyone please make me understand faulty keyboard question ?
I am confused with the given test cases .
| denotes cursor position-
my thought : T= empower , S=ew then , for me minimum operations will be : e|w (p+m)-> empow|(m)->empowe|(p+b)-> empower| ,
so total operations will be 5 , am i doing anything wrong ?
