LEBALONS - Editorial

darkshadows · May 12, 2014, 3:11pm

PROBLEM LINK:

Practice
Contest

Author: Vitaliy
Tester: Sergey Kulik
Editorialist: Lalit Kundu

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Combinatorics, Dynamic Programming, Probability

PROBLEM:

Given N ballons, i’th balloon has color C_i and cost P_i 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   
           // so we add   
           DP2[i-1][j-1]*((2**colors[i])-1) +   

           //also, we add    
           //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:

Author’s solution
Setter’s solution

cool_techie · May 12, 2014, 5:00pm

I don’t get it. What is meant by (2**colors[i])-1 different ways in the DP1[i][j] part ??

kunal361 · May 12, 2014, 5:37pm

“2**x” means pow(2,x)…i.e. if u didnt know!!!

caioaao · May 12, 2014, 6:07pm

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

kevind · May 12, 2014, 6:09pm

i am getting wa.Any help where my solution fails?
http://www.codechef.com/viewsolution/3900476

raul1rnjn535_3 · May 12, 2014, 7:15pm

http://www.codechef.com/viewsolution/3890092
Where does my solution fail,ie,which cases i haven’t considered?

aditya1993 · May 13, 2014, 12:54am

total sum for selecting i’th color is cost[i]*(2^(colors[i]-1)). How?? couldn’t get that…

rishabh1994 · May 13, 2014, 3:13am

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

betlista · May 13, 2014, 3:19am

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 C_i are in first row, P_i 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).

betlista · May 13, 2014, 3:25am

First four results are ok, last four are wrong, see my test case generation description.

betlista · May 13, 2014, 3:27am

First four results are ok, last four are wrong, see my test case generation description.

betlista · May 13, 2014, 3:35am

@aditya1993: too long for comment…

Simple input is

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).

betlista · May 13, 2014, 3:35am

see my answer

avastpulkit · May 13, 2014, 3:36am

@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 .

saikripd · May 14, 2014, 9:31am

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]

alphaparticle · May 14, 2014, 1:54pm

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 ?

razkverma · May 14, 2014, 3:06pm

how dp2[i][j] calculation has done??? someone please explain ???

akumar3 · May 16, 2014, 6:39pm

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

shoumik · May 17, 2014, 7:51pm

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

abhishek1995 · May 18, 2014, 4:41am

My solution is giving wa. Could someone please look at it and tell where the solution fails.
http://www.codechef.com/viewsolution/3906372