Author: Vamsi Kavala PROBLEM LINKSDIFFICULTYSimple PREREQUISITESSimple Math, Dynamic Programming Problem:You are shopping to buy N items and you can shop in K different shops. For every items bought consecutively on the same shop you get a discount on the item you buy more recently. Given the prices of the N items in all K shops as well as the discounts in all K shops, you want to find the least amount of money you need to spend to buy all N items. Quick Explanation:We can use dynamic programming to obtain the answer in O(N*K) time, where N is the total number of items we want to buy and K is the total number of shops we can choose from. We use the following DP state: Answer(i,j) → Total amount of money spent on buying i items, given that we buy the last item in shop j. As we will see, this state will be very useful in solving our problem. Detailed Explanation:The most important step in this problem, as in any DP problem, is to understand how to formulate a good state which will allow us to get the optimal answer. To begin, it might be worthwhile to state that the approach of using all discount coupons from a single shop will most likely not produce the optimal answer in the end. However, at every purchase we do, we are faced with K shops to choose from, and as we have N items to buy, we can define a DP state that will contain valuable information to guide us to the optimal answer. Let us define Answer(i,j) as referred on the quick explanation. According to the above formulation, our answer will be simply Min(Answer(N,j)) for j = 1 to K. It is obvious that Answer(1,j) = price of the item bought on shop j without any discount. This will form the base case of our recurrence relationship. Now, to derive what such relationship can be, we can think on how would our spendings change when we decided to buy second item. We can do one of two things now: aa) We buy the second item at the same store and apply the corresponding discount to its price; bb) We choose to buy the second item at other store, case where the price is taken without any discount; What will tell us which approach to use is actually the one that has the minimum price. So, an algorithm we can use is: Initialize answer array with the prices of the 1st item of each one of the K shops on the 1st column. Then at each step do: Answer(i,j) = Minimum(aa , bb) + price(i,j) Please note that aa and bb are explained above. In the end, answer will be Minimum of Answer(N,j) for all j = 1 to K. The matrix Answer is filled columnwise at each step. Since step bb takes time K, and since for every step we run over all K shops for the N items, final complexity would be O(N*k^2). But, we can do better than this! In fact, if for every item i, we store the minimum value of Answer(i,j), we can actually eliminate the O(K) additional processing and we can solve the problem in O(N*k) time, since we store minimum for all shops as we do the calculations. This was the intended solution. Refer to setter's and tester's solution for implementation details. SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here. Useful Links
This question is marked "community wiki".
asked 30 Jun '13, 14:19

@admin... one request... see that paper setter's or tester's solution should be written in languages, known to most of the users, like c, c++, java, python.Not only for this particular question, in future also.Other we can't understand his coding techniques.. thank you. answered 30 Jun '13, 17:43
the solution has been written in Pascal, which is quite popular.
(30 Jun '13, 18:18)
i think pascal is not used by many programmers, from normal colleges, NOW A DAYS, so we can't understand.And this is our request not a complaint...
(30 Jun '13, 18:36)
@aravind159, Setter and/or tester are free to implement the code on the language of their choice... Gennady himself always coded in Pascal until a very short time ago where he switched to C++... the idea of the editorial was to abstract solution from any particular language :)
(01 Jul '13, 15:42)

long long int is also not fetching me AC in subtask 1.. what can be the reason? answered 01 Jul '13, 15:26
@nanditagiri92 : Give a link to your submitted code , only then I can help , otherwise I just have speculate.
(01 Jul '13, 15:31)
(01 Jul '13, 15:48)
2
dont use ULONG_MAX (~4*10^9)for limit, as value is long long (1e18). I also faced d same problem. :)
(03 Jul '13, 00:23)
so what shud i use then??
(03 Jul '13, 14:45)
u shud use 1e18. ;) Or just take min=(LL)1e9*1e9
(03 Jul '13, 16:13)
1
thanks a lot.. it worked ;)
(03 Jul '13, 21:53)
showing 5 of 6
show all

please can anybody tell me which case my code doesn't pass. http://www.codechef.com/viewsolution/2308889 answered 02 Jul '13, 11:53

Well i am getting acc. ans for subtask #2,but wrong ans for subtask #1,#3. any corner cases to take care of. I have taken care of The condition if productPricediscount<0 => productPriceAfterDiscount=0. I have also used long long answered 09 Jul '13, 15:33

I was a little confused with this problem, it makes me slightly take some time, this appears to be the problem of finding the shortest path but eh answered 21 May '15, 09:00

For people finding some difficulty in understanding , try solving this question https://www.geeksforgeeks.org/dynamicprogrammingset34assemblylinescheduling/. The above question adheres to the same logic. answered 28 Mar '18, 22:16

How does the above solution pass with the time limit of 1 sec? The worst case time complexity is O(NK) which is O(10^510^5) ? Also the space complexity would be O(10^10). It is not possible to store so many elements in memory.
For time complexity: from constraints: 1 ≤ T * N * M ≤ 1000000
For space complexity: you can dynamically allocate memory, using malloc.
@Author : A good problem with a clear, detailed explanation. Thank you.