SONGSHOP - Editorial

PROBLEM LINK:

Practice
Contest

Author: Erfan alimohammadi
Tester & Editorialist: Hussain Kara Fallah

DIFFICULTY:

Easy-medium

PREREQUISITES:

DP

PROBLEM:

There are N songs (numbered 1 through N) and M albums (numbered 1 through M) available. For each valid i, the i-th song has greatness v_i, price p_i and belongs to the album a_i. For each valid i, the i-th album has price b_i. If we buy an album, then all songs from this album count as bought. It is also possible to buy any songs individually.

Your task is simple ― given the budget P, calculate the maximum total (sum of) greatness of songs we can buy.

1 \leq N,M,P \leq 1000

EXPLANATION

Let’s solve it in the following way, let’s create a list of all songs such that all songs which are from the same album are consecutive. Let’s build then our dp table.

dp(i,B) denotes the maximum total greatness we can achieve considering only the first i songs and spending exactly B.

dp(0,0)=0 \,\,\,\,\, This is our initial case.

Now when we are processing some song let’s say the i_{th} one we have 2 options either to buy it or not. So :

dp(i,B) \, = \, max(\, dp(i - 1,B) \, , dp(i-1,B-p_i)+v_i)

The first term indicates not buying the song, whereas the second indicates buying it. Of course, we shouldn’t try buying the song if B<p_i

As you can see we solved the problem considering buying only songs individually. How can we add the possibility of buying a complete album?

Not so hard, after processing the last song from a certain album. We should add try buying the complete album and updating our dp table. Please make sure again that all songs which are from the same album are consecutive.

Let’s assume that the current song x_{th} one is the last song of some album. For each possible B

dp(x,B)=max(dp(x,B)\, , \,dp(y,B-album\,price)+totV_album)

Looks confusing and not understandable

By y we denote the first song preceding the x_{th} and belonging to different album. We can only build a solution containing some album fully bought only if the sub-solution (the sub-problem) we are building on top of it has no song bought from that album (since each song can be bought only once).

It’s clear that totV_{album} denotes the greatness sum of the album songs.

Complexity: O(N*P)

AUTHOR’S AND TESTER’S SOLUTIONS:

AUTHOR’s solution

TESTER’s solution

10 Likes

I had tried a similar approach. Where is it going wrong?
My solution: https://www.codechef.com/viewsolution/23697076
Any suggestion or help is appreciated!!

1 Like

I am confused here. Why this is not infinite recursion?

1 Like

@sombis this is not a recursion at first place. The author has described an iterative approach.

@admin @sibasish_14 In this problem can we select songs in any order?
Like: Song 1 from Album2, then Song 1 from Album1, or we need to follow the order?
i.e. after selecting songs from Album1, then only we can move to Album 2…

If you are choosing an entire album, all songs of the same album must be selected at once. If not, you don’t need to maintain any particular order.

what is wrong in my code - https://www.codechef.com/viewsolution/28899991
testcases are passed