×

# LEBALONS - Editorial

Author: Vitaliy
Tester: Sergey Kulik
Editorialist: Lalit Kundu

EASY-MEDIUM

# PREREQUISITES:

Combinatorics, Dynamic Programming, Probability

# PROBLEM:

Given N ballons, i'th balloon has color Ci and cost Pi dollars. We choose any subset (chosen randomly, possibly empty) of the balloons such that the number of different colors in that subset is at least M. What is the expected cost of such a subset?

# EXPLANATION:

Since subsets are randomly chosen, expected cost is (total cost of subsets with at least M colors)/(total number of subsets with atleast M colors).
Let's keep colors[i]=number of balloons with color=i and cost[i]=sum of cost of all balloons with color=i.
Let color=number of distinct colors.
Let solve the denominator first.
We keep DP1[i][j], which denotes number of subsets which consists of colors 1 to i, and have j distinct colors.
So,

DP1[i][j]= // we are not using the i'th color
DP1[i-1][j] +

// we use the i'th color
// now, we can choose any combination of colors[i] balloons.
// but not the one in which no balloon is present.
// therefore, we have (2**colors[i])-1 different ways.
DP1[i-1][j-1]*((2**colors[i])-1)


Now, we come to the numerator.
For numerator, we keep DP2[i][j], which denotes the total cost of all subsets which consist of colors 1 to i, and have j distinct colors.
So,

DP2[i][j]= // we are not using the i'th color
DP2[i-1][j] +

// we use the i'th color
// firstly, we again have (2**colors[i])-1 options
DP2[i-1][j-1]*((2**colors[i])-1) +

//total sum for selecting i'th color * number of ways of selecting j-1 colors from i-1 colors(DP1[i-1][j-1])
// total sum for selecting i'th color is cost[i]*(2**(colors[i]-1)). How?
DP1[i-1][j-1]*cost[i]*(2**(colors[i]-1))


But, we count only those subsets where different colors is more than or equal to M.

num=den=0
for i=M to color:
num += DP2[color][i]
den += DP1[color][i]
print num/den


Complexity: O(color*color) where color=number of distinct colors.

# AUTHOR'S AND TESTER'S SOLUTIONS:

This question is marked "community wiki".

3.0k93164187
accept rate: 12%

2

please explain the calculation of dp2[i][j] from starting in simple language

(13 May '14, 03:13)

@darkshadows I think you have made a typo in the editorials. One of " Author's solution " or " Setter's solution " should be " Tester's solution " , in my opinion .

(13 May '14, 03:36)

 7 I don't get it. What is meant by (2**colors[i])-1 different ways in the DP1[i][j] part ?? answered 12 May '14, 17:00 289●7●12●18 accept rate: 22% "2**x" means pow(2,x)..i.e. if u didnt know!!! (12 May '14, 17:37) kunal3614★ 1 You have two choices for each item: choose it or not choose it. If you have two items, you'd have 22 possibilities of choosing them. For N items, you have 22...2 N times, so you have pow(2,N). As you can't choose the empty set, you subtract this 1 from the amount of choices you'd have, giving you pow(2,N) - 1, or (2**N)-1 if you're doing it in Python (12 May '14, 18:07) caioaao3★
 3 total sum for selecting i'th color is cost[i]*(2^(colors[i]-1)). How?? couldn't get that.. answered 13 May '14, 00:54 46●2 accept rate: 0% see my answer (13 May '14, 03:35) 4 suppose u have n balloons of color i... and u want to check how many times balloon k occurs in all the 2^n possibilities .... the number of possibilities will be 2^(n-1)(take balloon k and from the remaining choose as many as u want)... so the amount of cost that will be added for this balloon = 2^(n-1)* cost of k'th balloon ... so, for all the 'n' balloons = 2^(n-1) * sum of all the costs = 2^(n-1) * cost[i] (14 May '14, 09:31) saikripd2★

Explanation for DP2..if it helps :)

• We have a set (s, e, t), and all its subset till now.
• We are going to add a new element: "i"
• Result: (s, e, t, i) and all its subsets

We wish to know cost of all sets till now. Which is equal to:

• cost of all sets before (without "i")

               +

• cost of all newer sets (with "i")

The second term is something we wish to understand...

## Calculation of second term above:

Sum of cost of all subset of (s, e, t, i); but in each subset we do not add the cost of "i" (hence it is essentially repeating the sum DP2[i-1][j-1] , (2^colors[i] - 1) times)

         +


Cost of "i" in all subsets of (s, e, t, i)

Which in terms of the variables looks like:

DP2[i-1][j-1] * (2^colors[i] - 1)

         +


cost[i] * MAGIC

Where, MAGIC is number of occurrences of "i" in all subsets of (s, e, t, i) = DP1[i-1][j-1] * (2^(colors[i]-1))

Think of the equation for MAGIC...this is the beauty of the solution....

Great Problem to solve! I hope the explanation makes sense :D

3★akumar3
1426
accept rate: 0%

 1 When there is more difficult problem (like this one) I'm using JUnit tests to test my code. For every test you have to know two values - what is output of your program and what is the correct result. It may be confusing - you want to test something you do not know the correct answer yet, but you can solve this problem. Typically you can solve small instances by brute force and this is very good start. Here are my tests with the expected results. Please note, that my input format is different I will describe just first (the simplest) set of tests 1 2 3 1 2 3 M=0 => 3.000000 M=1 => 3.428571 M=2 => 4.500000 M=3 => 6.000000  That simply means, that my Ci are in first row, Pi are in second row (N can be derived from first two lines) and there are expected results for M from 0 to 3 (number of colors). answered 13 May '14, 03:19 16.9k●49●115●225 accept rate: 11%
 1 @aditya1993: too long for comment... Simple input is 3 0 1 1 1 2 1 3  you have 1 color, but 3 different prices for the colors, so you cannot simple ask how many ways are there to choose color 1 which is nCr(3, 1) + nCr(3, 2) + nCr(3, 3). You are interested in weighted (for each price) cost. So you modify what you want to calculate to "find the number of ways to choose color 1, when I first choose price 1, later price 2 and at the end price 3". But when you choose price, you have one baloon from the color, so the ways are nCr(2, 0) + nCr(2, 1) + nCr(2, 2) which is exactly 2^2 (you can see that from Pascal's triangle). answered 13 May '14, 03:35 16.9k●49●115●225 accept rate: 11%
 0 http://www.codechef.com/viewsolution/3890092 Where does my solution fail,ie,which cases i haven't considered? answered 12 May '14, 19:15 224●1●4●11 accept rate: 11% First four results are ok, last four are wrong, see my test case generation description. http://ideone.com/twTBDH (13 May '14, 03:27)
 0 Can anyone please explain the calculation of Dp2[i][j] more elaborately. I understood that for Dp[i][j] = Dp[i-1][j] + // Not selecting the ith color + Dp[i-1][j-1] * cost[i] * pow(2, color[i]-1 ) // Selecting the ith color + Dp[i-1][j-1] * (pow(2,color[i])-1) // Why is this used ?  answered 14 May '14, 13:54 151●4●11 accept rate: 25% the cost of selecting the ith color is last two terms collectively (25 Jan '15, 03:28)
 0 how dp2[i][j] calculation has done??? someone please explain ??? answered 14 May '14, 15:06 1 accept rate: 0%
 0 My solution is giving wa. Could someone please look at it and tell where the solution fails. http://www.codechef.com/viewsolution/3906372 answered 18 May '14, 04:41 31●1 accept rate: 0%
 0 Could anyone point out the mistake in this ? Seems correct :( Thanks answered 22 May '14, 15:22 1.0k●6●11●22 accept rate: 16%
 0 Can anybody point out the error in the code. I cross checked it with the tester's solution on some test cases. http://www.codechef.com/viewsolution/3973475 I am getting a WA. If anyone could explain the reason or the test case, thanks for the same. answered 05 Jun '14, 22:46 2★siddv29 1●1●2●4 accept rate: 0%
 -1 i am getting wa.Any help where my solution fails? http://www.codechef.com/viewsolution/3900476 answered 12 May '14, 18:09 1★kevind 148●2●3●12 accept rate: 0% 1 First four results are ok, last four are wrong, see my test case generation description. http://ideone.com/twTBDH (13 May '14, 03:25) @betlista can you please tell what is wrong with this code. Though it gives correct ans, it is wa on codechef. this is the result on codechef. Thanks! (02 Jun '14, 09:26) sudharkj3★
 -1 Lets say we have numbers 1,3 for color set 1 , number 2 for color set 2. and costs for numbers 1,2,3 are 5,7,4 so colors[1]=2 , cost[1]=9 , color[2]=1 , cost[2]=7. t=highest color a number holds. now we want to calculate DP1[i][j] //for i=1 to t //for j=1 to i DP1[1][1]= DP1[0][1]+DP1[0][0] * ((2^colors[1])-1) =0(as without taking any color we cant make a subset of 1 distinct color ) + 1 ((2^2)-1) =3 . so we found the subsets : 1,3,13 DP1[2][1]=DP1[1][1]+DP1[1][0] * ((2^colors[2])-1) =3 DP1[2][2]=DP1[1][2]+DP1[1][1] * ((2^colors[2])-1) =0+3 * 1 , so we add color 2 into subsets now we have for DP[2][2] : 12,23,123 now we calculate DP2[i][j]; DP2[1][1]=DP2[0][1]+DP2[0][0] * ((2^colors[1])-1)+DP1[0][0] * 2 ^ (colors[1]-1) cost[1] here we use 2 ^(colors[1]-1) cause lets say for a subset of 1,2 we find 1,2,12 and the number of occurrences of each digit is 2 . 2^(2-1) =2 =0+0+ 1 * 2 * 9=18 ( using color 1 we have 1(5),3(4),13(9) total cost =18 DP2[2][1]=DP2[1][1]+DP2[1][0]((2^colors[2])-1)+DP1[1][0]2 ^ (colors[2]-1) cost[2] =18 +0+0=18 now the last step we need DP2[2][2] so we are using color 2 and we have 2 distinct colors so the subsets will be 23,12,123 . total cost 39 DP2[2][2]=DP2[1][2]+DP2[1][1] * ((2^colors[2])-1)+DP1[1][1] * 2 ^ (colors[2]-1) cost[2] as are adding only one new color 2 . and previosly we have cost of subsets 1,2,12[cost 18] and these portion are calculated in DP2[1][1] . if we have more than one colors to add in the subsets then the cost will be added into all subsets so we use DP2[1][1]((2^colors[2])-1) now the cost of newer element DP1[1][1] * 2 ^ (colors[2]-1) *cost[2] = 3 * 1 * 7=21 so total 39 answered 17 May '14, 19:51 3★shoumik 0●1 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:

×15,852
×2,212
×1,722
×20
×20

question asked: 12 May '14, 15:11

question was seen: 7,615 times

last updated: 25 Jan '15, 03:28