You are not logged in. Please login at www.codechef.com to post your questions!

×

FFCOMB - Editorial

6
2

PROBLEM LINK:

Practice
Contest

Author: Sergey Kulik
Tester: Misha Chorniy
Editorialist: Pawel Kacprzak

DIFFICULTY:

EASY

PREREQUISITES:

Dynamic programming, bits

PROBLEM:

There are $N$ meals to buy numbered from $1$ to $N$. The $i$-th meal can be bought separately for price $C_i$. Meals can also be bought in sets. There are $M$ sets and each set consists of some meals. The prices of the $i$-th set is $P_i$. The goal is to buy all $N$ meals for the lowest possible price. In one test file there are multiple test cases to handle.

QUICK EXPLANATION:

The main idea is to use dynamic programming and bitmasks to compute $dp[mask]$ as the smallest possible cost of buying elements set in the $mask$.

EXPLANATION:

In subtasks $1$ and $2$ methods based on computing the exactly value of $dp_1$ defined in the explanation for subtask 3 below might be used. In particular let $dp[mask]$ be the lowest price to buy meals in $mask$. Then one possible idea for lower constrains is to iterate for all possible masks and for each single one, iterate over all possible seats of meals and try to lower the cost of meals covered by the current mask and the set of meals by combining their costs.

Subtask 3

First of all, notice that buying all meals is always possible, because they all can be bought separately. However, the price can be reduced by buying the meals in sets.

Let $dp_1[mask_1]$ be the smallest price for buying meals in $mask_1$ using a single purchase - so using either a single purchase of a separated meal or a single purchase of a set of meals

Let $dp_2[mask_2]$ be the smallest price for buying meals in $mask_2$ using any purchases.

Clearly, $dp_2[mask_2]$ for $mask_2$ containing $N$ ones is the final answer.

At the beginning, we can set values of $dp_1$ and $dp_2$ to some extremely large values in order to simplify the implementation.

The first step towards the solution is to compute $dp_1$ values for all possible $2^N$ masks. Later we are going to use these values to compute values in $dp_2$.

Let $mask_{separete, i}$ be the mask corresponding the meal $i$. Moreover, let $mask_{set, i}$ be the mask corresponding to the $i$-th set of meals. Initially, we set:

$dp_1[mask_{separete,i}] = C_i$ for all $i = 1, 2, \ldots, N$.

Then, we set:

$dp_1[mask_{set, i}] = \min(dp_1[mask_{set, i}], P_i)$ for $i = 1, 2, \ldots, M$.

Since buying a set of $B$ meals might be the cheapest way to buy a set of $A$ meals for $A < B$, then we are going to try to lower these costs as follows:

for (int mask = (1 << n) - 1; mask >= 0; —mask) {
   for (int j = 0; j < n; ++j) {
      if (mask & (1 << j)) {
         dp_1[mask ^ (1 << j)] = min(dp_1[mask ^ (1 << j)], dp_1[mask]);
      }
   }
}

The thing to notice there is that we iterate from the masks containing the most meals to the masks containing less meals in order to try to reduce their prices. Notice that $\texttt{mask ^ (1 << j)}$ is the $mask$ with the $j$-th bit set to $0$.

After than, we are ready to compute the values of $dp_2$. The idea is very simple, for a given $mask$ we are going to iterate over all submasks of $mask$ and ty to add a single meal to them to expand it to $mask$:

dp_2[0] = 0;
for (int mask = 0; mask < 1 << n; ++mask) {
   int submask = (mask - 1) & mask;
   while (submask > 0) {
      dp_2[mask] = min(dp_2[mask], dp_2[submask] + dp_1[mask ^ submask])
      submask = (submask - 1) & mask;
   }
}

The above method has time complexity $O(2^N \cdot N + 3^N)$, where the first part is the complexity of calculating $dp_1$ values and the second part is the complexity of calculating $dp_2$ values. While the complexity of the first part is quite obvious, the complexity of the second part needs an explanation. For each mask, we iterate over all its submasks. We know that there are $\binom{N}{k}$ masks with $k$ ones and each such mask has $2^{N-k}$ submasks. Thus the number of iterations during computation of $dp_2$ can be measure as $\sum\limits_{k=0}^N \binom{N}{k} \cdot 2^{N-k} = 3^N$.

AUTHOR'S AND TESTER'S SOLUTIONS:


Setter's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

asked 29 Oct '16, 23:01

pkacprzak's gravatar image

5★pkacprzak ♦♦
74485097
accept rate: 12%

edited 30 Oct '16, 00:55

$2^{18}*18 + 3^{18}$ = $392139081$ > $2*10^8$, how does it pass within the time limit? Does the present server compute faster than 10^8 operations also?

(30 Oct '16, 02:17) likecs6★

^^ Same question. I also tried a 3**n approach (which was wrong) but it still gave tle: https://www.codechef.com/viewsolution/11980847

(30 Oct '16, 02:27) vsp46★

@vsp4, your code is recursive may be that is why it gave TLE, but still why does $3^n$ pass?

(30 Oct '16, 02:45) likecs6★
4

$10^8$ Operations per s is just a rough estimate. If you have a cache friendly algorithm with simple operations you can get much higher. On the old servers cache friendliness seemed to be paramount. In some problem I computed the transpose of a 1000x1000 int matrix in the straightforward naive fashion. It took on the order of a second!

(31 Oct '16, 05:20) ceilks7★

How each mask has 2^(N-k) submasks ?

(01 Nov '16, 00:06) vjmanit4★

How the complexity is O(N*2^N) ?
It look to me something of order O(N *2^N + 3^N) .

link

answered 29 Oct '16, 23:34

brainstorm's gravatar image

4★brainstorm
21
accept rate: 0%

You're right, I made an update and added a detailed explanation for this part.

(30 Oct '16, 00:56) pkacprzak ♦♦5★

Weak tests?

link

answered 29 Oct '16, 23:38

bktl99's gravatar image

4★bktl99
21
accept rate: 0%

I think so. Somhow I passed with a barely optimized $O(2^n\cdot M)$ (M being the number of meal combos in the input).

(31 Oct '16, 05:22) ceilks7★

The solution above mentioned is not O(2^N * N) but actually O(3^N). While calculating dp_2, for each mask a traversal is made on each subtask, which actually gives a complexity of O(3^N - 2^N + 1) as per the given code. Even the tester's code makes 387158346 iterations for line 48-53. Please check and provide a O(2^N * N) solution if there is possible.

link

answered 29 Oct '16, 23:59

uhateme's gravatar image

5★uhateme
2054
accept rate: 11%

Thanks, I updated it and added a description why the complexity of the second part is O(3^N)

(30 Oct '16, 00:56) pkacprzak ♦♦5★

How did you simplify the summation to 3 ^ N ?

link

answered 30 Oct '16, 02:49

omarkhaledd's gravatar image

4★omarkhaledd
1
accept rate: 0%

2

Binomial theorem. $\sum_{k=0}^{n} \binom{n}{k} \cdot 2^k \cdot 1^{n-k} = (2+1)^n$

(30 Oct '16, 08:47) nibnalin6★

Nice editorial :-)

I thought of the bitmask dp method, but couldn't figure out anything to reduce the complexity!

link

answered 30 Oct '16, 16:53

utsav12071997's gravatar image

5★utsav12071997
433
accept rate: 0%

edited 30 Oct '16, 16:53

can anyone tell me why it is O(2^n*n) for dp1 instead of O(2^n).

link

answered 02 Nov '16, 00:08

student2's gravatar image

1★student2
1
accept rate: 0%

edited 02 Nov '16, 00:12

@student2 First 2^n or (1st for loop) is used for generating all combination of generating bits in binary form and other one (2nd for loop) is used for manipulating these bits i.e., doing manipulation on individual bits!

I hope you get this.. otherwise feel free to ask

link

answered 02 Nov '16, 08:34

bansal1232's gravatar image

5★bansal1232
2.8k1419
accept rate: 16%

Thank you bansal.Can anyone tell me what are the submasks and how they can be computed

link

answered 02 Nov '16, 20:53

student2's gravatar image

1★student2
1
accept rate: 0%

could anyone explain in dp1 why we are considering to minimize A meals by just reducing 1 meals from B meals. suppose we have meals 3,4,5 for price 10 and meals 3,4,5,6,7 for price 5 then we have to just take second set price for both set.BTW I solved it by assigning like this but I don't understand in editorial.

link

answered 15 Nov '16, 13:14

chilling's gravatar image

2★chilling
212
accept rate: 0%

edited 15 Nov '16, 17:46

How this statement 'The thing to notice there is that we iterate from the masks containing the most meals to the masks containing less meals in order to try to reduce their prices.' holds true? We are iterating in descending order, that does'nt mean that all numbers containing highest number of bits come first. consider 4 and 3. 4 has 1 bit where 3 contains 2 bits

link

answered 30 Nov '16, 01:21

prudvinit's gravatar image

3★prudvinit
10318
accept rate: 0%

Here is my solution, https://www.codechef.com/viewsolution/12155819 well commented.

link

answered 30 Nov '16, 23:07

prudvinit's gravatar image

3★prudvinit
10318
accept rate: 0%

Link to setter's solution is broken.

link

answered 23 Jan '17, 21:27

inarito's gravatar image

4★inarito
776
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×15,680
×2,170
×77
×41

question asked: 29 Oct '16, 23:01

question was seen: 5,788 times

last updated: 23 Jan '17, 21:27