Thursday, 16 July 2015

MasterChef KNAPSAC + SEGTREE..

MasterChef 


Chef loves to prepare delicious dishes. He has prepared N dishes numbered from 1 to N for this year's MasterChef contest. He has presented all the N dishes to a panel of judges. Judging panel consists of Mjudges numbered from 1 to M. Rating for each dish was decided by voting from all the judges. Rating for the dishes has been given by a 1-indexed array A where Ai denotes rating of the ith dish.
Some dishes prepared by chef are extraordinary delicious, but unfortunately, some are not. Chef has been given a chance to improve the total rating of his dishes. By total rating of dishes, we mean the sum of the ratings of his dishes. Each of the M judges has administrative power to remove some (zero or more) dishes from a specified range. The ith judge takes Ci rupees for removing each dish of Chef's choice from the dishes numbered from Li to Ri (both inclusive). Once a dish is removed by any of the M judges it will not be considered for calculating total rating of the dishes. Chef has spent a large portion of his money preparing mouth watering dishes and has only K rupees left for now. Now chef is worried about maximizing total rating of his dishes by dropping some of the N dishes.
Please Help chef by finding the maximum total rating he can achieve such that the total expenditure does not exceed his budget of K rupees.

Input

  • First line of input contains a single integer T denoting the number of test cases.
  • First line of each test case contains three space separated integers N, K and M denoting the number of dishes prepared by chef, chef's budget, and number of judges in judging panel respectively.
  • Next line of each test case contains N space separated integers where ith integer denotes the rating received by the ith dish.
  • Next M lines of each test case contain three space separated integers each: L, R and C, where the integers in the ith line denotes the value of Li, Ri and Ci respectively.

Output

For each test case, print a single integer in a line corresponding to the answer.

Constraints

  • 1 ≤ T ≤ 105
  • 1 ≤ N,M ≤ 105
  • 1 ≤ K ≤ 500
  • 1 ≤ Li ≤ Ri ≤ N
  • 1 ≤ Ci ≤ 200
  • -109 ≤ Ai ≤ 109
  • Sum of N and M over all test cases does not exceed 5*105

Subtasks :

  • Subtask 1 : Sum of all N's across the test cases in a file does not exceed 5000. Sum of all M's is also at most 5000. (33 points).
  • Subtask 2 : Sum of all N's across the test cases in a file does not exceed 5*105. Sum of all M's is also at most 5*105. ( 67 points ).

Example

input
1
5 10 5
10 -2 -5 7 -10
1 1 5
2 4 10
4 4 12
3 4 10
1 5 15

output
5

Explanation

  • Chef can drop dish numbered 3rd with rating -5 by paying 10 rupees to the 4th judge, and get the maximum possible total rating of 5.


***************************************************QUESTION IN SHORT********************************************

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≤105 and C≤200.

***************************************************************SEGMENT TREE APPROACH******************
 AS THERE ARE MANY   UPDATE QUERIES AND  EACH QUERY  GIVES A RANGE AND ITS VALUE .. SO WE CAN USE SEGMENT TREE WITH LAZY PROPOGATION  TO DECIDE WHICH VALUE IS BEST FOR  A RANGE .. 
AND FINALLY WE FIND SUITABLE COST FOR EACH -VE  NUMBER BY QUERY IN WHICH STARTING AND ENDING INDEX IS SAME (ie START==END   OR LEAF ELEMENTS OF THE SEGMENT TREE) ,,
AND THEN WE CAN USE KNAPSACK TO FIND  NUMBERS WHICH IS BEST SUITABLE TO REPLACE  BY 0 ..


CODE ---

  2. #include<iostream>
  3. using namespace std;
  4. #include<bits/stdc++.h>
  5. typedef long long int lli;
  6. lli arr[1000010];
  7. int lazy[1000000];
  8. int seg[1000000];
  9. lli val[100010];int wt[100010];
  10. int ul,uh,value;
  11. int qs,qe;
  12. lli dyn[100010][510];
  13.  
  14.  
  15. #define maxi 1000000007
  16. void update(int index ,int start,int end)
  17. {
  18. // cout<<"start "<<start<<" end "<<end<<endl;
  19.  
  20. if(lazy[index]!=maxi)
  21. {
  22. seg[index]=min(seg[index],lazy[index]);
  24. if(start!=end)
  25. {
  26. lazy[2*index]=min(lazy[index],lazy[2*index]);
  27. lazy[2*index+1]=min(lazy[index],lazy[2*index+1]);
  29. }
  30. lazy[index]=maxi;
  31. }
  32. if(start>end || start>uh || end<ul) return ;
  33. if(start>=ul && end<=uh)
  34. {
  35. seg[index]=min(seg[index],value);
  36. if(start!=end)
  37. {
  38. // cout<<"lazy set"<<endl;
  39. lazy[2*index]=min(value,lazy[2*index]);
  40. lazy[2*index+1]=min(value,lazy[2*index+1]);
  41. }
  42. return ;
  43. }
  44. update(2*index,start,(start+end)/2);
  45. update(2*index+1,(start+end)/2+1,end);
  46. // seg[index]=min(seg[2*index],seg[2*index+1]);
  47. }
  49. // KNAPSACK
  50. lli maximize(int W, int wt[], lli val[], int n)
  51. {
  52. int i, w;
  53. for (i = 0; i <= n; i++)
  54. {
  55. for (w = 0; w <= W; w++)
  56. {
  57. if (i==0 || w==0)
  58. dyn[i][w] = 0;
  59. else if (wt[i-1] <= w)
  60. dyn[i][w] = max(val[i-1] + dyn[i-1][w-wt[i-1]], dyn[i-1][w]);
  61. else
  62. dyn[i][w] = dyn[i-1][w];
  63. }
  64. }
  66. return dyn[n][W];
  67. }
  68. // QUERY TO FIND COST OF REPLACEMENT OF EACH -VE NUMBERS
  69. int qry(int index,int start,int end)
  70. {
  71. if(start>end || start>qe || end<qs) return maxi;
  72. if(lazy[index]!=maxi)
  73. {
  74. // cout<<" query lazy unset "<<endl;
  75. seg[index]=min(seg[index],lazy[index]);
  77. if(start!=end)
  78. {
  79. lazy[2*index]=min(lazy[index],lazy[2*index]);
  80. lazy[2*index+1]=min(lazy[index],lazy[2*index+1]);
  82. }
  83. lazy[index]=maxi;
  84. }
  86. if(start>=qs && end<=qe)
  87. {
  88. return seg[index];
  89. }
  91. int ai= qry(2*index,start,(start+end)/2);
  92. int b=qry(2*index+1,(start+end)/2+1,end);
  93. return min(ai,b);
  94. }

  1. int main()
  2. {
  4. int t;
  5. cin>>t;
  7. while(t--)
  8. {
  9. int n,p,m;
  10. lli final=0;
  11. // cin>>n>>p>>m;
  12. n=read_int();
  13. p=read_int();
  14. m=read_int();
  15. for(int i=0;i<5*n;i++)
  16. {
  17. seg[i]=maxi;
  18. lazy[i]=maxi;
  19. }
  20. for(int i=0;i<n;i++)
  21. {
  22. // cin>>arr[i];
  23. arr[i]=read_int();
  24. final+=arr[i];
  25. }
  26. for(int i=0;i<m;i++)
  27. {
  28. // // cin>>ul>>uh>>value;
  29. ul=read_int();
  30. uh=read_int();
  31. value=read_int();
  32. ul-=1;
  33. uh-=1;
  34. update(1,0,n-1);
  35. }
  38. int no=0;
  39. for(int i=0;i<n;i++)
  40. {
  41. if(arr[i]<0)
  42. {
  43. qs=i;
  44. qe=i;
  45. wt[no]=qry(1,0,n-1);
  46. val[no]=-arr[i];// MAKING ALL -VA NO +VE AND APPLY KNAPSA //CK ON IT TO FIND BEST SUM TO REPLACE IN GIV //EN AMOUNT OF MONEY
  47. no++;
  48. }
  49. }
  50. lli rec= maximize(p,wt,val,no);
  51. final+=rec;// SINCE FINAL CONTAINS SUM OF ALL NUMBERS SO REC IS // ADDED TO IT WHICH CONTAIN +VE SUM OF NUMBERS WHICH R //REPLACED (FOUND IN KNAPSAC)
  52. printf("%lld\n",final);
  53. }
  54. }


********************************************SET APPROACH********************************************

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 Ai, you can remove it in many ways. Let's define by set Si the set of operations which can remove Ai. So Si={operj:Lj≤i≤Rj}. Now you can intuitively/greedily say that for removing Ai you would always choose the operation from set Si whose cost is minimum.
Now, let's say for all i, we have found the minimum cost to remove Ai. 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 Ai there is cost of removal Ri. Remove some elements from Aito maximize the sum of remaining elements and also total cost of removal shouldn't exceed C. This is quite similar to0-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 solve(i,j) as the answer if our budget is j and our array is formed by the first i elements ie. A1,A2,...,Ai. So our answer will be solve(N,C).
Now let's try to form recursive relations. You want to reduce your current problem i.e. solve(i,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 Ai or not.
Let's consider case 1, where we will remove Ai. This is only possible if j≥Ri. Now, solve(i,j) = solve(i−1,j−Ri). Note that we have lost Ri cost on removing Ai and our array is now reduced to first i−1elements. Also, in the sum of remaining elements Ai couldn't contribute anything. (A thought: Will we ever remove Ai if it's positive, considering removing elements incurs cost?).
Now, case 2, let's not remove Ai. Now, solve(i,j) = Ai + solve(i−1,C). Now, Ai 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:
solve(i,j) = max(solve(i−1,j−Ri),Ai+solve(i−1,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 flag array which is same type of your DP array and intialised to false. Once you have calculated a certain subproblem, you mark it true in the 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 N * C and transition cost is constant time. So, total complexity is 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 Ai.
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 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 iand 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 Lj and Rj the cost of this particular operation ie. Kj. Now, when we traverse arrays Land R from left to right, say we are index i, for indices ≥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 ≥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<int> 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[left].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(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 MIN array is O(N log M). You can also find MIN array using segment trees where the complexity will be O((M + N) log N), if we use lazy propagation and make updates.

COMPLEXITY:

Final complexity after including complexity of DP is O(N log M + N C)

.

Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)