Assuming your Knapsack implementation is correct, the bug might be in your segment tree implementation.
Creating SegmentTree is hard (agree) but testing is easiest!
Simply use brute force solution (update array manually) and then test the output with that of your tree output…
Or at least you can create random test files of yours and then use any of the accepted solutions to generate the output, followed by comparing it with your solution? That should point out your bug in no time.
Today I can do all this for you, but who will do it tomorrow?
Let me know if you need more help on debugging.
As you might have already noted, the elements removed are no longer needed (because they are the ranges which ends at index i, therefore will not affect any index > i in our array)
But why do we care to remove them?
That is because, we are getting min element of the set without checking if the min is from a valid range…
So if we don’t remove those obsolete ranges, we might get a min element with a cost…which is of a range…which actually does not affect our current array element in observation.
I got TLE with the DP solution for the second subtask. Weird.
What’s really surprising is that I tried greedy knapsack (aka fractional knapsack) and got AC. You sort each value by decreasing (value/cost) here A[i]/R[i] and greadily take everything till the budget is reached. Normally this solution shouldn’t work on all test cases. Does anyone have a clue on why it worked?
I used the same kind of solution Lalit used but I used a multiset instead. Can anyone tell me why it TLEed for subtask 2? Here’s my soln. http://www.codechef.com/viewsolution/7352429
Anybody who has solved it using stack and priority queue ?? Something like merging intervals and creating new intervals if required?Sorry on bed rest so can’t code my logic just want to know if anyone was able to pass solution using similar logic
.
this is my implementation using stl sets can anybody point out the error …as this code is not getting accepted #include < bits/stdc++.h >
using namespace std;
long long knapSack (int W,int wt[],int val[],int n)
{
long long i, w;
long long K[n+1][W+1];
// Build table K[][] in bottom up manner
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i==0 || w==0)
K[i][w] = 0;
else if (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];
}
int main()
{
int t,n,k,m,l,r,x,temp;
int *arr,*v,i,*s,*c,j;
long long sum=0;
int *idx;
vector<int> L[100000],R[100000];
set <int> iset;
cin>>t;
while(t--)
{
cin>> n >> k >> m;
sum=0;
arr= new int[n];
s= new int[n];
v= new int[n];
c=new int[m];
for(i=0;i<n;i++)
{
cin>>arr[i];
v[i]=-1*arr[i];
sum+=arr[i];
s[i]=1000000;
}
// L=new vector<int>[n];
// R=new vector<int>[n];
for(i=0;i<m;i++)
{
cin>>l>>r>>temp;
L[l-1].push_back(i);
R[r-1].push_back(i);
c[i]=temp;
}
for(i=0;i<n;i++)
{
for(j=0;j<L[i].size();j++)
{
iset.insert(c[L[i][j]]);
}
s[i]=*(iset.begin());
for(j=0;j<R[i].size();j++)
{
iset.erase(c[R[i][j]]);
}
}
for(i=0;i<n;i++)
{
cout<<s[i]<<endl;
}
Brother can you see why my rating got reduced even after i did 4 of the 10 problems that were accepted and got the AC verdict at the time of submission.
