COUPON - Editorial

Author: Vamsi Kavala
Tester: Roman Rubanenko
Editorialist: Bruno Oliveira

PROBLEM LINKS

Practice
Contest

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.

Useful Links

Dynamic Programming

2 Likes

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.

@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.

1 Like

the solution has been written in Pascal, which is quite popular.

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…

Somehow, this approach gives AC for subtask#2(m<=100) and subtask#3(m>100) but surprisingly, WA for subtask#1(m=2). Can’t figure out why. Infact, looking at the submissions of this problem, many have got WA in subtask#1, though Subtask#2 (and Subtask#3 as well of some users) are AC. Is there some special/boundary case being tested in Subtask#1 ?

P.S.- The condition if productPrice-discount<0 => productPriceAfterDiscount=0 and no left over money IS taken care of.

I had AC on subtasks 2 and 3 and WA on subtask 1 because I used int insead of long long :wink:

1 Like

Just switch to long long int.

Yes, I also face the same problem and its due to long long int.

long long int is also not fetching me AC in subtask 1… what can be the reason?

@nanditagiri92 : Give a link to your submitted code , only then I can help , otherwise I just have speculate.

@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 :slight_smile:

please can anybody tell me which case my code doesn’t pass.
http://www.codechef.com/viewsolution/2308889

dont use ULONG_MAX (~4*10^9)for limit, as value is long long (1e18).
I also faced d same problem. :slight_smile:

2 Likes

so what shud i use then??

u shud use 1e18. :wink:
Or just take min=(LL)1e9*1e9

thanks a lot… it worked :wink:

1 Like

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 productPrice-discount<0 => productPriceAfterDiscount=0.
I have also used long long