MCHEF - Editorial

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 hope I answered your question.

I cannot access tester or setter solution.

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

i used segment trees to find min cost but last 2 test cases of sub-task 2 gave TLE.

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
.

Very nice editorial… Keep it up… :slight_smile:

The update part can be done with the help of an array to keep track of the updated indexes…NO need of segment trees nor any STL DS…just one array!!!

Link: http://www.codechef.com/viewsolution/7426441

I am also trying to create an array of list like this(as implemented below)

L=new vector[n];
R=new vector[n];

but codechef gives sigarbt error …please help

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;
}

//reduces to knapsack problem
cout<<sum+knapSack(k,s,v,n)<<endl;
delete []arr;
delete []s;
delete []v;
delete []c;
for(i=0;i<n;i++)
{
L[i].clear();
R[i].clear();
}
// delete []R;
// delete []L;
iset.clear();
}

}

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.

write

if(!iset.empty())

just before the line

s[i]=*(iset.begin());

No access to Setter’s solution!

You should have received an email saying why. It’s most likely that it’s been detected that you have copied someone else or they have copied you.

tester and setter solution are not visible…plz check

Thank You :slight_smile:

Nice Problem :slight_smile: :slight_smile: got many TLE using SEGMENT TREE. then modified my code with fast input . and dp with space saving

Can anyone explain the approach using segment tree or provide any link for help.

1 Like