Author: Vamsi Kavala
Tester: Roman Rubanenko
Editorialist: Bruno Oliveira
PROBLEM LINKS
DIFFICULTY
Simple
PRE-REQUISITES
Simple 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 column-wise 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 SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.
