calculus.saransh's blog

By calculus.saransh, 13 years ago, In English

Here is the link to the problem



The problem required us to find the expected saving chef can make considering the average of all the discounts over all the combinations Chief might select.

A novice approach of trying all combinations will TLE.

Dynamic programming might be of help here. As the chief would like to maximize the discount he may get over a combination he would use lower discounts for lower costs articles.

My Approach -

1. Sort all costs in ascending order.
2. Sort all discounts in ascending order.

We have N articles and K discounts to use.

expected(n,k)= (expected(n+1,k+1)+cost(n)*discount(k))*((K-k)/(N-n))+expected(n+1,k)*(1-(K-k)/(N-n))

Here n and k denote the number of articles considered and the number of discounts used till now. We have to find expected(0,0) and the multiplication of (K-k)/(N-n) is done to one side and (1-(K-k)/(N-n)) to the to the other because when while calculating expected(n,k) (N-n) articles remain to be considered and (K-k) discounts remain. The probability of getting the article is (K-k)/(N-n) and not getting is (1-(K-k)/(N-n)).

Using this approach we find the expected discount that chef can achieve.

I used this code during the contest which had memoization and i got TLE.


I used this code after the contest which avoided recursion and used straight forward DP and got WA.


Can anyone help me here. 

EDIT: Got AC... Used sliding window DP by minimizing the memory table to 2 rows. As only 2 are required.


Here is the Code

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

13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
the editorials are up on the codechef site maybe you can match your solution with that.