×

# COUPON - Editorial

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

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.

Dynamic Programming

This question is marked "community wiki".

3★kuruma
17.7k72143209
accept rate: 8%

2561314

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.

(30 Jun '13, 17:18)

For time complexity: from constraints: 1 ≤ T * N * M ≤ 1000000

For space complexity: you can dynamically allocate memory, using malloc.

(30 Jun '13, 17:27) 6★

@Author : A good problem with a clear, detailed explanation. Thank you.

(09 Aug '13, 20:10)

 2 @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 46●4 accept rate: 0% 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) kuruma3★
 0 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. answered 30 Jun '13, 18:58 495●4●4●10 accept rate: 0% 1 I had AC on subtasks 2 and 3 and WA on subtask 1 because I used int insead of long long ;) (30 Jun '13, 19:58) visanr6★ Just switch to long long int. (30 Jun '13, 22:29) iceman_w2★ Yes, I also face the same problem and its due to long long int. (30 Jun '13, 23:39) sobhagya3★
 0 long long int is also not fetching me AC in subtask 1.. what can be the reason? answered 01 Jul '13, 15:26 0 accept rate: 0% @nanditagiri92 : Give a link to your submitted code , only then I can help , otherwise I just have speculate. (01 Jul '13, 15:31) http://ideone.com/6iCRuT (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) phoenix_3★ 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) phoenix_3★ 1 thanks a lot.. it worked ;) (03 Jul '13, 21:53) showing 5 of 6 show all
 0 please can anybody tell me which case my code doesn't pass. http://www.codechef.com/viewsolution/2308889 answered 02 Jul '13, 11:53 3★paramvi 16●5 accept rate: 0%
 0 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 answered 09 Jul '13, 15:33 3★gunner65 1 accept rate: 0%
 0 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 0★ctscool1 1 accept rate: 0%
 0 For people finding some difficulty in understanding , try solving this question https://www.geeksforgeeks.org/dynamic-programming-set-34-assembly-line-scheduling/. The above question adheres to the same logic. answered 28 Mar '18, 22:16 21●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,211
×1,191
×281
×14

question asked: 30 Jun '13, 14:19

question was seen: 7,232 times

last updated: 28 Mar '18, 22:16