Challenge Problem #2
Dynamic Programming
Here is the solution to the challenge problem from my article on DP. Be sure to read it first.
This article is a short one. The reason is that the full solution for the above problem is given in the Codeforces editorial here.
This article will focus on trying to explain the solution to the problem using the steps discussed in the article.
Observations
We first observe that if we sort the array of costs in increasing order in a sorted array a, then,
If I pay for some item a[j], then I should take a[j-1] for free, since it’s the most expensive item not yet bought
It makes no sense to take more than 2 items without taking any free items
Hence I can divide the array into segments of length 2. Now I have 2 choices
Buy a[1], a[3], a[5]… and get a[0], a[2], a[4]… for free
Buy a[0]. Then buy a[2], a[4], a[6]… and get a[1], a[3], a[5]… for free
In the harder version of the same problem, instead of buy 1 get 1 free, the offer is now buy 1 get k free. So we can generalise the above solution like this
Buy a[k-1], a[2k-1], a[3k-1]… and get the rest for free
Buy a[0]. Then buy a[k], a[2k], a[3k]… and get the rest for free
Buy a[0] and a[1]. Then buy a[k+1], a[2k+1], a[3k+1]… and get the rest for free
In general, buy the first x items from a[0] to a[x]. Then pay for item a[k+x], a[2x+x], a[3k+x]… and get the rest for free.
Remember to try all x and ensure that we never spend more money than we have.
Problem solving steps
We need to be a little creative whenever we use DP. That is why it’s such a hard skill to master. In this case,
Every state is defined by a number
memo[i] represents the number of items we can buy if we pay for the first i items.
memo[0] means we start buying from a[k-1]
memo[i] means we buy from a[0] to a[i-1] inclusive
The transition state is just to buy the item a[i-1] and keep track of the spent money so far in a separate variable
The time complexity of the solution is O(k*n/k) = O(n). The reason? For every iteration we’re buying every kth item in the array. There are k iterations maximum, since it makes no sense to buy more than k items without using the discount.
You can see the solution code and editorial here. Try to code the solution yourself before reading the editorial.
This was a short post. Thanks for reading! I hope you enjoyed, and I’ll see you in the next one
