lkjhgfertyul's blog

By lkjhgfertyul, history, 11 days ago, In English

Problem Statement:
There is an array "cost" of length n, cost[i] is the cost of i'th robot and an array "A" of length n, A[i] is the number written on the i'th robot, you are also given an integer K which is the amount you have. You can buy a robot only if cost of that robot is less than or equal to the remaining amount you have(obviously).
Suppose you buy x robots with indices i1, i2, i3 ... ix then you will get one gift card for each i such that A[i] >= x (i belongs to indices of robots you purchased). Calculate the maximum number of gift cards you can get.

1<= n <= 100
1<= K <= 1e9
1<= cost[i] <= 1e4
1<= A[i] <= n

Sample Input
5 300 <-- (n, K)
4 5 4 3 2 <-- (cost)
120 150 80 90 100 <-- (A)

Sample Output

Buy robots with indices 3,4,5 cost 270(<=300) and you will get 2 gift cards for robots 4 and 5

I was thinking of some knapsack type approach but was not able to get a solution. You can comment your solution or post a link to a similar problem with solution, thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Till I am able to think you can do it with binary search

Ist observation : if you buy k robots and gift you get let y (y < k) then it is optimal to just buy y robots so that you get also y gift

Ex -> let you buy i1 i2 i3 i4 i5 , corresponding A[i] value 6 5 1 2 2 it is optimal to buy 6 5 only since these are contributing

Now Our goal to maximize the y(robot you buy and all contributing to the answer)

Binary Search over y (1...n) for fix y you can club the elements that has A[i] >= y then you pick smallest y elements among them and check their sum <= k or not

I think this works fine , If not plz let me know