I cant seem to find why i am getting WA even in subtask1
http://www.codechef.com/viewsolution/7475713
please help.
good test cases might help
I have solved it using merging intervals having same c values and 0-1 knapsack. if anyone interested can have look here
7 Likes
Can you explain why my code got a WA ?
I used sweep line algorithm to get apt interval and then used a knapsack 
#include<bits/stdc++.h>
using namespace std;
/*
1 data first.first
2 type first.second
3 other second.first
4 cost second.second
*/
int knapSack(long long int W, long long int wt[], long long int val[], long long int n)
{
long long int i, w;
long long int 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()
{
ios_base::sync_with_stdio(false);
vector<pair<long long, long long> > v;
vector<pair<pair<long long,long long>,pair<long long,long long> > > u;
map<pair<long long, long long>, long long> m1;
long long t, n, k, m, sum, i, x, l, r, c;
cin >> t;
while (t--)
{
cin >> n >> k >> m;
sum = 0;
for (i = 0;i < n;i++)
{
cin >> x;
sum = sum + x;
if (x < 0)
{
v.push_back(make_pair(-1 * x, i + 1));
}
}
sort(v.rbegin(), v.rend());
for (i = 0;i < m;i++)
{
cin >> l >> r >> c;
m1[make_pair(l, r)] = c;
}
long long int wt[100000], val[100000], z;
pair<pair<long long,long long>,pair<long long,long long> > temp;
//DO THE SWEEP-LINE PARADIGM
for(i=0;i<v.size();i++)
{
(temp.first).first=v[i].second;
(temp.first).second=0; // we put a 0 type for point , -1 for left, 1 for right
(temp.second).first=-1;
(temp.second).second=v[i].first; // cost contains value for points, and cost for intervals
u.push_back(temp);
}
for(map<pair<long long, long long>, long long> ::iterator it=m1.begin();it!=m1.end();it++)
{
(temp.first).first=(it->first).first;
(temp.second).first=(it->first).second;
(temp.first).second=-1;
(temp.second).second=(it->second);
u.push_back(temp); //pushing left part of interval
(temp.second).first=(it->first).first;
(temp.first).first=(it->first).second;
(temp.first).second=1;
(temp.second).second=(it->second);
u.push_back(temp); //pushing right part of interval
}
set<pair<long long,pair<long long,long long> > > s;
pair<long long,pair<long long,long long> > temps;
sort(u.begin(),u.end());
z=0;
for(i=0;i<u.size();i++)
{
if(u[i].first.second==-1) //left of interval
{
temps.first=u[i].second.second;
temps.second.second=u[i].second.first;
temps.second.first=u[i].first.first;
s.insert(temps);
}
else if(u[i].first.second==1) //right of interval
{
temps.first=u[i].second.second;
temps.second.first=u[i].second.first;
temps.second.second=u[i].first.first;
s.erase(temps);
}
else //point
{
temps=*(s.begin());
val[z]=v[u[i].first.first-1].first;
wt[z]=temps.first;
z++;
}
}
long long int ans = knapSack(k, wt, val, z);
cout << sum + ans << "\n";
m1.clear();
u.clear();
v.clear();
s.clear();
}
return 0;
}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.