CHEFSHOP - Editorial

editorial
greedy
medium
nov15

#1

PROBLEM LINK:

Practice
Contest

Author: Roman Furko
Tester: Istvan Nagy
Editorialist: Xellos

DIFFICULTY:

MEDIUM

PREREQUISITES:

Dynamic programming, bitmasking, greedy algorithms.

PROBLEM:

There are N items and M discounts - subsets of the items. Each item has a price. You may choose any number of disjoint discounts and pay for all items except the cheapest item in each discount. You may also permute the prices in any way. Find the minimum price to pay.

QUICK EXPLANATION:

Solve the subproblem where you know the chosen discounts. Sort the discounts and prices, use a subset DP to compute the answer.

EXPLANATION:

Note: in this problem, subsets S \subset \lbrace0,1,..,N-1\rbrace should be represented by bitmasks. The intersection of two such subsets s_1 and s_2 can be found easily as s_1\&s_2 (bitwise and), their union as s_1|s_2 (bitwise or); if they’re disjoint, their union is simply s_1+s_2. Those operations work in O(1).

Small bounds mean exponential solutions (or old Topcoder). That means we probably want some subset DP that maximises our savings (the answer is just the sum of all prices minus the amount we saved using discounts), but that’s complicated by the fact that we can permute price tags. How should we assign them?

We have a subproblem to solve here: if we knew which discounts will be used, what’s the optimal assignment of price tags?

Let’s sort those tags first in an array exttt{tags}[] - their starting order doesn’t matter, anyway. If the smallest discount offer is for at least d_1 items, then the largest d_1-1 prices must be paid. The d_1-th largest price can be discounted (i.e. not paid - literally “not counted” / “uncounted” towards the final price), but only if we pack the largest d_1 into that smallest discount offer. Similarly, if the second smallest discount offer is d_2, then the d_1+d_2-th largest price is the next one which can be discounted, and so on. This greedy assignment is really optimal, since for each k, the k-th largest discounted price is the maximum possible, so their sum - our savings - is the maximum possible.

That means we need to sort the discounts by their size - the number of items in them. We’ll process them in the order from smallest to largest and do a DP on an array exttt{maxdisc}[s] - the maximum amount we can save if the union of discounts used so far is a subset s. When processing a discount that can be applied on a subset s_d, then we can ignore it (which doesn’t change exttt{maxdisc}[]) or use it. We can use it if the subset s of items used in discounts so far was disjoint with s_d, which gives exttt{maxdisc}[s+s_d]= exttt{maxdisc}[s]+ exttt{tags}[|s+s_d|] (the array exttt{tags}[] is sorted in non-increasing order here). Overall, we get

exttt{maxdisc}[s+s_d]= ext{max}\left( exttt{maxdisc}[s+s_d], exttt{maxdisc}[s]+ exttt{tags}[|s+s_d|]\right)

for s\&s_d=0.

The straightforward way to update exttt{maxdisc}[], which involves trying all s and checking if they’re disjoint, won’t work here, since that takes at least O(M2^N)=O(4^N) time. For each discount, we need to efficiently enumerate all subsets s disjoint with it and only update exttt{maxdisc}[s+s_d] for them; that will work fast enough, since the number of subsets s disjoint with some s_d is 2^{N-|s_d|} and the number of subsets s_d of size |s_d|=k is N\choose k, so are at most \sum_{k=0}^N {N\choose k} 2^{N-k}=(2+1)^N=3^N (we un-expanded the sum using the binomial theorem) subsets s disjoint to all possible distinct s_d. And if we have several identical discount offers, we can ignore all except one of them without affecting the answer.

As it works in reality, we don’t actually need to buy everything in discounts only (which may be impossible, anyway), any items can still be bought normally. Therefore, the maximum savings at the end are given as the maximum exttt{maxdisc}[s] over all subsets s bought in discounts only; as mentioned already, to get the answer, we should subtract the savings from the sum of all prices.

Generate subsets s disjoint to s_d is actually quite simple - just find the items that aren’t in s_d, keep a list of subsets s generated so far and process those items one by one; for each item, take the subsets generated so far and generate two copies for each - with and without that item. Each subset is only generated once, so K subsets can be generated in time O(N+K).

We’ve got all that’s necessary now. If we precompute the sizes of all subsets in O(N 2^N), then the number of operations in the DP is O(3^N); even listing all disjoint pairs of subsets takes just O(3^N) as well, so the total time complexity is O(3^N); since we only need to remember them at each step, the memory spent is O(2^N).

AUTHOR’S AND TESTER’S SOLUTIONS:

The author’s solution can be found here.
The tester’s solution can be found here.
The editorialist’s solution can be found here.

RELATED PROBLEMS:


#2

I used a trie to generate subsets disjoint to some given subset.


#3

https://www.codechef.com/viewsolution/8760827 , my solution seems to have a worst case of 2 ^ n * m but it still passed , can someone tell the exact complexity of this since i dont think it will ever go 2 ^ n * m?


#4

I’m confused with this accepted solution (from the problem page, the one who ranked first). This solution seems to ignore the subset and just consider their size. So, could someone explain why this can be correct? Did I miss something?


#5

I think test cases were week. Found another similar solution
They are wrong for trivial case like:

1

4

1 2 3 4

2

2 1 2

2 1 2

Giving output 6, but correct answer is 7


#6

I used randomness(random shuffle) to get maximum disjoint pairs of same size, since the connectivity is smaller compared to nodes, it works smoothly :smiley:

https://www.codechef.com/viewsolution/8784879


#7

Hats off to these two solutions:
first and
second.
They just ignored the details of the “offers” provided in the question and sang their own song, which also eventually got ACed ( :smiley: ).

Also found few more solutions ACed, which fail even basic test cases, like this.

Test Case:

1

8

1 2 3 4 5 6 7 8

3

3 1 2 3

3 4 5 6

2 7 8

Correct Output : 24

Above Code’s Output : 26

I guess the admin should think about the author’s pay again.( :stuck_out_tongue: )


#8

Does the statement actually say that the selected discounts have to be disjoint?

I was really confused by this problem and tried to ask a clarifying question twice, but never got an answer.


#9

“The salesman walked away for a minute, giving Chef an opportunity to swap some price tags. He would like to swap some tags to minimize his purchase cost.”

Could someone explain this statement w.r.t problem? If it means you can swap any price on any item with other item, then isn’t it be solvable without any offers details (subset), just knowing subsets size should work like done in few submissions.


#10

Hi, I wrote this solution with is (2^N)*M, this was not supposed to pass right ?
Also if someone could explain iterating only the necessary subsets instead of all the 2^N, it would be really helpful. :slight_smile:

Solution


#11

Didn’t get the generating subsets disjoint to a particular subset part at all.Can someone help?


#12

@aditya730 suppose our initial set is {1,2,3,4,5,6,7,8,9,10} and sd is {1,2,3,4,5}.
So initially list of sets generated disjoint to sd is empty. We select elements which are not in sd i.e. 6,7,8,9,10.

Now we start with list of sets disjoint to sd which is currently empty i.e. {} (as no set is generated, but we can say an empty set is generated initially)

First select element 6. So, So, we generate two copies of all the sets generated first with element 6 and second without element 6. So, now list of sets generated disjoint to sd are {6},{}.

Now select element 7, So, we generate two copies of all the sets generated first with element 7 and second without element 7. So, now list of sets generated disjoint to sd are {6,7},{6},{7},{}.

Now select element 8, So, we generate two copies of all the sets generated first with element 8 and second without element 8. So, now list of sets generated disjoint to sd are {6,7,8},{6,7},{6,8},{6},{7,8},{7},{8},{}.

and so on…
Hope it’s clear now.


#13

May be that the tests are weak.


#14

It says there’s one item of each type. A bit of common sense is needed…


#15

I’m not talking about the number of items. My understanding was that every item could either be discounted (you don’t have to pay for it), if it was the cheapest item in some discount offer, or not discounted (and you pay for it) otherwise.

“The local grocery store has some special discount offers. If you want to buy some set of ingredients you will pay for all ingredients except the cheapest one”. It doesn’t even say that you have to pick some discounts. It says that all discount offers contribute to the discount.


#16

You can make as many swaps as possible -> permute the prices.

There’s only one item of each type, so you can’t use 2 non-disjoint discounts. That’s why we need subsets. But the test data are weak, apparently.


#17

I’m aware that the statement sucks, but this contradicts the sample, so it just can’t be the case.