PROBLEM LINK:Author: Vitaliy DIFFICULTY:EASYMEDIUM 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).
Now, we come to the numerator.
But, we count only those subsets where different colors is more than or equal to M.
Complexity: O(color*color) where color=number of distinct colors. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 12 May '14, 15:11

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
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^(n1)(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^(n1)* cost of k'th balloon ... so, for all the 'n' balloons = 2^(n1) * sum of all the costs = 2^(n1) * cost[i]
(14 May '14, 09:31)

Explanation for DP2..if it helps :)
We wish to know cost of all sets till now. Which is equal to:
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
Cost of "i" in all subsets of (s, e, t, i) Which in terms of the variables looks like:
Where, MAGIC is number of occurrences of "i" in all subsets of (s, e, t, i) = Think of the equation for MAGIC...this is the beauty of the solution.... Great Problem to solve! I hope the explanation makes sense :D answered 16 May '14, 18:39

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
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). answered 13 May '14, 03:19

@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 But when you choose price, you have one baloon from the color, so the ways are answered 13 May '14, 03:35

http://www.codechef.com/viewsolution/3890092 Where does my solution fail,ie,which cases i haven't considered? answered 12 May '14, 19:15
First four results are ok, last four are wrong, see my test case generation description.
(13 May '14, 03:27)

Can anyone please explain the calculation of Dp2[i][j] more elaborately. I understood that for
answered 14 May '14, 13:54

how dp2[i][j] calculation has done??? someone please explain ??? answered 14 May '14, 15:06

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

@darkshadows http://www.codechef.com/viewsolution/3915467 Could anyone point out the mistake in this ? Seems correct :( Thanks answered 22 May '14, 15:22

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

i am getting wa.Any help where my solution fails? http://www.codechef.com/viewsolution/3900476 answered 12 May '14, 18:09
1
First four results are ok, last four are wrong, see my test case generation description.
(13 May '14, 03:25)

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^(21) =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

please explain the calculation of dp2[i][j] from starting in simple language
@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 .