MCHEF - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sunny Aggarwal
Tester: Mugurel Ionut Andreica
Editorialist: Lalit Kundu

DIFFICULTY:

Easy-Medium

PREREQUISITES:

dynamic programming, data structures

PROBLEM:

Given an array of N elements consisting of both negative and positive elements and M operations. Each operation is of type L, R and K which implies that you can remove any one element within range L to R(both include) by paying K cost (each operation can be used multiple times).

You have a fixed budget C. You have to maximize the total sum of the array such that the expenditure in maximizing sum of elements does not exceed your budget C.

Here, N, M \le 10^5 and C \le 200.

QUICK EXPLANATION:

First for each element find the minimum cost required to remove it. And then using DP similar to 0-1 Knapsack Problem calculate the maximum possible sum.

For finding minimum cost to remove each element:

  • For subtask 1, you can brute force i.e. for each operation traverse over all indices it effects and update the value in an array.

  • For solving subtask 2, you have to either use STL sets or you can use segment trees.

EXPLANATION:

================
The most basic observation here is that each operation allows to remove single element only. So, let’s say you want to remove A_i, you can remove it in many ways. Let’s define by set S_i the set of operations which can remove A_i. So S_i = \{\textrm{oper}_j : L_j \le i \le R_j\}. Now you can intuitively/greedily say that for removing A_i you would always choose the operation from set S_i whose cost is minimum.

Now, let’s say for all i, we have found the minimum cost to remove A_i. How we actually do this I will explain later. So our problem now is basically:

You have an array A of size N… For each element A_i there is cost of removal R_i. Remove some elements from A_i to maximize the sum of remaining elements and also total cost of removal shouldn’t exceed C. This is quite similar to 0-1 Knapsack Problem which can be solved via Dynamic Programming(DP).

So, first step in writing/formalizing any DP problem is to decide some states which defines a sub problem of the problem we are trying to solve. You can do some hit and trial before you reach the correct states. Next step is to break the current problem into smaller sub problems which can help in defining the recursive relation between the DP states. Last step is to decide the base case.

So, here we define \textrm{solve}\hspace{1mm}(i,\hspace{1mm}j) as the answer if our budget is j and our array is formed by the first i elements ie. A_1, A_2, ..., A_i. So our answer will be \textrm{solve}\hspace{1mm}(N,\hspace{1mm}C).

Now let’s try to form recursive relations. You want to reduce your current problem i.e. \textrm{solve}\hspace{1mm}(i,\hspace{1mm}j) into smaller sub problems. How can we do that? To reduce current problem in smaller parts, we have to perform some action, which here is to decide whether to remove A_i or not.

Let’s consider case 1, where we will remove A_i. This is only possible if j \ge R_i. Now, \textrm{solve}\hspace{1mm}(i,\hspace{1mm}j) = \textrm{solve}\hspace{1mm}(i-1,\hspace{1mm}j - R_i). Note that we have lost R_i cost on removing A_i and our array is now reduced to first i - 1 elements. Also, in the sum of remaining elements A_i couldn’t contribute anything. (A thought: Will we ever remove A_i if it’s positive, considering removing elements incurs cost?).

Now, case 2, let’s not remove A_i. Now, \textrm{solve}\hspace{1mm}(i,\hspace{1mm}j) = A_i + \textrm{solve}\hspace{1mm}(i-1,\hspace{1mm}C). Now, A_i is not removed and contributes to the sum of remaining elements. Also, our budget remains same and our array size is now reduced by 1.

So, our recurrence is ready which is basically:
\textrm{solve}\hspace{1mm}(i,\hspace{1mm}j) = \textrm{max}(\hspace{1mm}\textrm{solve}\hspace{1mm}(i-1,\hspace{1mm}j - R_i), \hspace{1mm} A_i + \textrm{solve}\hspace{1mm}(i-1,\hspace{1mm}j)).

Let’s see what are the base cases. The only base case is that if i==0 i.e. there is no array left, the only maximum sum possible is 0.

DP Implementation:

This is the last step of completing your DP problem. The best and the easiest way of writing DP is recursively with memoisation. There is no major difference in run time of recurisve and iterative DP.

Now, what is memoisation? It basically is method where you don’t calculate things you’ve already calculated. So you maintain a \textrm{flag} array which is same type of your DP array and intialised to \textrm{false}. Once you have calculated a certain subproblem, you mark it true in the \textrm{flag} array. If you ever reach again a state, which has already been calculated, you return the value currently stored in DP array. Things will get clear from the following implementation:


	flag[N][C]  #initialised to false
	DP[N][C]	#array which stores actual answers
	A[N]		#array A
	R[N]		#cost array
    
	solve(i, j):
    	#base case
        if i<=0:
        	return dp[i][j]=0	#first sets dp[i][j] to 0 and returns it
            
        if flag[i][j] == true:	#this dp has already been calculated
        	return dp[i][j]
            
        #case 2: don't remove A[i]
        ret = A[i] + solve(i - 1, j)
        
        #case 1: remove A[i] if possible
        #tak ret to be the maximum of both cases
        if(j >= R[i])
        	ret = max(ret, solve(i - 1, j - R[i]))
            
        #mark flag[i][j] true since we have calculated this DP
        flag[i][j] = true
        
        return dp[i][j] = ret

Complexity of DP:

Let’s set what is the complexity of such a recursive implementation. Since each possible state is visited once, the complexity of DP is number of states multiplied with transition cost. Transition cost is the complexity required from transfrom from one state to another state.

Here, our total number of states is \textrm{N * C} and transition cost is constant time. So, total complexity is \textrm{O(N * C)}.

Calculating minimum cost for removing each element

Now, about the part which we skipped earlier about calculating minimum cost of removing of A_i.

First you initialize all indices of a MIN array to infinity and then for each operation you traverse through all indices which it covers and update the minimum value at each index. Here complexity is \textrm{O(M*N)}, where M is number of operations and N is size of array A. This is enough to pass Subtask 1.

For solving Subtask 2, interesting observation is that an index i is affected by operations whose left end is before i and right end is after i. Suppose we have a data structure where we can insert/delete elements and find minimum value currently stored in this data structure in sub linear time. Let’s say this structure is S.
So, let’s maintain two vector arrays L and R(means you can store a list of values at each index) and for each operation j insert at index L_j and R_j the cost of this particular operation ie. K_j. Now, when we traverse arrays L and R from left to right, say we are index i, for indices \ge i, values stored in list L[i] are going to effect them, so we add to our structure the values stored at L[i] and the values stored in R[i] are not going to affect indices \ge i, so we remove all values stored at R[i].
What could be this data structure S. If we use STL set, we can insert/delete a object only once, but this is not what we require. There might be two operations with same cost. So instead of storing values, we can store a pair of value and the indices of operations. In this way all operations will be unique and the beginning element of set will always give the minimum value operation.

If you don’t feel enough clarity, see this pseudo code and try to visualize what is happening.

	struct oper{
    	int l, r, k;
    };
    
    oper operarray[M];		//array of operations
    int MIN[N];				//MIN[i] stores minimum cost for removing A[i]
    vector L[N], R[N];
    //arrays as defined in above paragraph
    //except now they store indices of operations instead of their cost
	
    set < pair < int, int > > iset;
    //first element of pair stores value of operation cost
    //second stores the index of operation
    
    for i = 1 to M:
    	left = operarray[i].l
        right = operarray[i].r
        
    	L.push_back(i)
        R[right].push_back(i)
        
    for i = 1 to N:
    
    	//add all operations beginning at i
    	for j = 0 to L[i].size() - 1:
        	operindex = L[i][j]		//index of operation beginning here
            cost  = operarray[operindex].k
            
            //insert in set
    		iset.insert(make_pair(cost, operindex))
            
        MIN[i] = iset.begin()->first;	//first element of the set
        
        //remove all operations ending at i
    	for j = 0 to R[i].size() - 1:
        	operindex = R[i][j]		//index of operation beginning here
            cost  = operarray[operindex].k
            
            //erase from set
    		iset.erase(make_pair(cost, operindex))

Set is a STL data structure that inserts and deletes elements in O(\textrm{log (size of set)}). And since it keeps all elements in sorted order, we can find minimum element in constant time.

So total complexity of finding the \textrm{MIN} array is \textrm{O(N log M)}. You can also find \textrm{MIN} array using segment trees where the complexity will be \textrm{O((M + N) log N)}, if we use lazy propagation and make updates.

COMPLEXITY:

Final complexity after including complexity of DP is \textrm{O(N log M + N C)}.

AUTHOR’S, TESTER’S SOLUTIONS:

setter
tester

Problems to Practice:

Problems based on DP

Problems based on STL

7 Likes

Please provide some test cases for which the following code is giving WA.
http://www.codechef.com/viewsolution/7467050

If you cant find anything wrong,do mention it.

I had used the same concept of 0-1 knapsack problem but still getting WA.http://www.codechef.com/viewsolution/7425751
Plz Help!!!

I managed to get AC with maintaining an array/BIT to jump indices .! Starting from the interval with minimum cost , I kept on assigning the index the minimum value ! The complexity of my code was O(N+M+#jumps*logN) and it passes . I guess the number of jumps can be quite high ! And this solution should not pass atleast with that log N factor multiplied! Solution .

Correct me if I am wrong !

The number of jumps are maximum when we put ranges of length 1 whole over N and leave one index i.e. N ! Now we will have to process all the left queries and suppose they all dont match N , then this will cause processing of all (M-(N-1)) queries over whole N . Hence the complexity should be > (M-(N-1))*N . with M =10^5 and N =10^4 this approach should Time out!

Please help!! I am getting TLE for subtask 2 eventhough i used SET as explained in the editorial.
http://www.codechef.com/viewsolution/7474759
Thanx :slight_smile:

We can also use segment tree to do the first subtask . Here is a link to my solution http://www.codechef.com/viewsolution/7422093

First of all, A very good problem to solve, enjoyed solving it (although only subtask-1)

I used Priority Queue to merge the ranges and obtain the MIN array.
Then 0-1 Knapsack Algorithm to find the final answer.
I got TLE for substask-2.

Intuitively I think the complexity of my ‘mergeRange’ function is O(M + (2M lg M)), i.e., O(M lg M) and therefore it should have passed.

Here is my solution:
http://www.codechef.com/viewsolution/7383196

Can someone verify if Priority Queue can be used to merge the ranges and obtain MIN array in O(M lg M) time.

Thanks.

I used interval tree to find minimum cost to remove a dish and 0-1 knapsack to find the cost of removing maximum dish but got WA and since you guys don’t provide test case details on which my program failed. I guess i wont know what i did wrong :frowning:

Attached is snowbear’s solution: http://www.codechef.com/viewsolution/7329411. Can somebody help me understand how this short code solves the problem.

auto jury = readVector<pair<pair<int, int>, int>>(m);
sort(all(jury));
reverse(all(jury));

for (auto &j : jury) {
	j.first.first--;
	j.first.second--;
}

vector<int> minCost(n, IntMaxVal);
vector<int> longestDiscount(201, -1);

FOR (i, 0, n) {
	while (jury.size() && jury.back().first.first == i) {
		maximize(longestDiscount[jury.back().second], jury.back().first.second);
		jury.pop_back();
	}
	FOR (c, 1, longestDiscount.size()) if (longestDiscount[c] >= i) {
		minCost[i] = c;
		break;
	}
}

vector<vector<int>> best_costs(k + 1);
FOR (i, 0, n) if (a[i] < 0 && minCost[i] <= k) best_costs[minCost[i]].push_back(-a[i]);
for (auto &v : best_costs) sort(all(v)), reverse(all(v));
FOR (c, 1, best_costs.size()) if (best_costs[c].size() > k / c) best_costs[c].resize(k / c);

vector<pair<int, int>> knapsack_items;
FOR (c, 1, best_costs.size()) for (auto x : best_costs[c]) knapsack_items.push_back( { c , x } );
vector<LL> knapsack(k + 1);
for (auto &item :  knapsack_items) 
	FORD (c, k, item.first) maximize(knapsack[c], knapsack[c - item.first] + item.second);
return res + knapsack.back();

I used segment trees with lazy propagation for updates and dp as mentioned but i got TLE. my sol can be found here. Please let me know why it failed??

I tried to solve using 0/1 knapsack . But getting WA. Please help . Thnx in advance :slight_smile:

My code http://www.codechef.com/viewsolution/7449600

I cant seem to find why i am getting WA in subtask 1?
Could any1 please help?
Maybe some good testcases if any

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 :frowning:

#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. 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.