Prashant94157's blog

By Prashant94157, history, 22 months ago, In English

In front of you ,there is a treasure containing many gems, soon you realize that they contain bad luck and are not precious as well. You have the power to destroy gems but can destroy 1 gem per sec. You can destroy gems in any order and wanted to destroy maximum bad luck. You have given a 2D matrix, where for i'th gem , it takes arr[i][0] seconds to give arr[i][1] units of bud luck and you can decide in which order you want to receive the bad luck. There is no time lapse in the process. Although while receiving bad luck, you can destroy bad luck. Once gem started giving bad luck , cannot be stopped until it is destroyed of its own after giving bad luck. You have to print maximum bad luck you can destroy.

Constraints

1 <= n <= 10^3 1 <= arr[i][0] <= 10^3 1 <= arr[i][0] <= 10^6

Testcase 1:
Input:
4
0 10
1 4
1 3
1 20
Output: 30
Explanation:
You can get maximum 30 when you choose to destroy 0th and 3rd while receiving bad luck from 1st and 2nd gems. 2 gems require 2 seconds to destroy while 1st and 2nd take 2seconds to give bad luck.
Testcase 2:
Input:
7
3 5
6 5
0 8
8 8
7 4
10 3
8 6
Output:
34
Tags dp
  • Vote: I like it
  • +5
  • Vote: I do not like it

| Write comment?
»
22 months ago, # |
  Vote: I like it -14 Vote: I do not like it

It's just a knapsack problem. Please think before asking.

Marinush

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    But it is not a knapsack, if you closely observe. Even if it is, tell me the weight of the knapsack and also tell me the type of knapsack it it pls.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    think before commenting

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    @Marinush yes this is a knapsack but take a look at the constraints, the dp table would be O(10^9) and the tc is also O(10^9)

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How is it 10^9 bro, its just 10^6. Simple n*k dp

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess it is a 2d dp question where while memoizing we'll take no. Of stones taken, sum.....where we will reduce sum value by stating a condition which shows that is sum > N make it equal to N only.....coz we'll care about the value of sum till then only

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please elaborate your approach

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      actually i have come up with a better one: Initialize dp[n][sum];

      now iterate: //we are taking the stone solve(arr, ind+1, sum + arr[ind][1] + 1); //here +1 is for destroying the other gem simultaneously

      // if we are not taking the stone

      solve(arr, ind+1, sum);

      //base condition if(sum >= N) return 0;

      if(x >= N) //as we have reached the end of array without satisfying the criteria

      and after evaluating the score: through dp return total_time — score

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>

int mx;

int dp[1001][1001];

int f(vector<vector<int>> &arr,int idx,int rem)
{
    if(rem <= 0) return 0;
    if(idx >= arr.size()) return INT_MAX-mx;
    // take
    if(dp[idx][rem] != -1) return dp[idx][rem];
    int ans1 = arr[idx][1] + f(arr,idx+1,rem-1-arr[idx][0]);
    int ans2 = f(arr,idx+1,rem);

    return dp[idx][rem] = min(ans1,ans2);
}

void solve()
{
    memset(dp,-1,sizeof(dp));
    int n;
    cin>>n;
    mx = 0;
    int total = 0;
    vector<vector<int>> arr(n,vector<int>(2));
    for(int i=0;i<n;i++)
    {
        cin>>arr[i][0]>>arr[i][1];
        mx = max(mx,arr[i][1]);
        total += arr[i][1];
    }
    cout<<total-f(arr,0,n)<<"\n";
}

signed main()
{
    int t;
    t = 1;
    while (t--)
    {
        solve();
    }
}
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    // for the Input Input: 7 3 5 6 5 0 8 8 8 7 4 10 3 8 6

    I am getting output : 36 If we can select 10 3 we will get 10 seconds, so we can destroy all other gems ( remaining 6, so required 6 sec < 10 sec). So the answer will be total — 3 => 39-3 = 36

    Right??