Is there a way to solve this problem using sqrt decomposition?
Why the elements in set removed after finding min[i] for subtask 2? Could somebody explain it a bit more clearly
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. CodeChef: Practical coding for everyone
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… 
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!!!
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.
tester and setter solution are not visible…plz check
Nice Problem 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
Correct me if I’m wrong as I’m not used to segment trees.
You have used segment tree without lazy propagation, right? I’m asking because I tried to do the same and managed to pass only 1st subtask and got TLE on 2nd subtask
No i used lazy propogation in a sense.Have a look at my update function. Once i encounter the segment [l,r] i assign tree[node] to minimum of tree[node] and c and return there itself. I wont go further down the tree.Only in traverse function i traverse from root of the tree to its leaves…Overall time complexity for first subtask is O(nlogn)
1 Like
In Calculating minimum cost for removing each element, you say for each operation j insert at index Lj and Rj the cost of this particular operation ie. Kj. Then in the pseudocode there’s a comment except now they store indices of operations instead of their cost. This is a bit confusing.
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.