migy8d3u1epe39's blog

Uber coding round problem
By migy8d3u1epe39, history, 3 years ago, In English

The problem was in a long story format but let me simplify it for you :-)

Problem: Some genie has power P. He wants to grant n wishes of the form {xi, yi}. Now to grant i-th wish he needs to have at least power xi and after granting this wish his power becomes P-yi. In this process, his power shouldn't dip below zero. What is the maximum no. of possible wishes he can grant using his power?

Constraints: 1<=n<=100, 1<=P<=30000, 1<=x<=30000, -300<=y<=300

I couldn't solve this problem in test time, I've seen so many problems of this type but I always fail. I would be grateful if someone explains this. Thanks have a good day!

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

https://codeforces.net/contest/1203/problem/F2, the exact question, you can refer to the editorial, if its of any help.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    cool, I will look at the problem editorial seems interesting to me.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

Deleted.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

this is just the classical 0-1 knapsack problem but with different statement.

you can learn about it here: wikipedia and geeksforgeeks

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I guess in knapsack problem the weight is constant but in this case it changes with each pick up, here yi could increase or decrease the power.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      then why don't you take all the positions that have negative y_i and then do knapsack

      → Reply