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

×

LEBALONS - Editorial

12
3

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 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   
           // 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

This question is marked "community wiki".

asked 12 May '14, 15:11

darkshadows's gravatar image

5★darkshadows ♦
3.0k93164187
accept rate: 12%

edited 12 May '14, 17:21

2

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

(13 May '14, 03:13) rishabh19942★

@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) avastpulkit3★

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

link

answered 12 May '14, 17:00

cool_techie's gravatar image

2★cool_techie
28971218
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★

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

link

answered 13 May '14, 00:54

aditya1993's gravatar image

5★aditya1993
462
accept rate: 0%

edited 13 May '14, 02:45

(13 May '14, 03:35) betlista ♦♦3★
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

link

answered 16 May '14, 18:39

akumar3's gravatar image

3★akumar3
1426
accept rate: 0%

edited 16 May '14, 21:46

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

link

answered 13 May '14, 03:19

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

edited 13 May '14, 03:20

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

link

answered 13 May '14, 03:35

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

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

link

answered 12 May '14, 19:15

raul1rnjn535_3's gravatar image

2★raul1rnjn535_3
2241411
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) betlista ♦♦3★

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 ?
link

answered 14 May '14, 13:54

alphaparticle's gravatar image

4★alphaparticle
151411
accept rate: 25%

the cost of selecting the ith color is last two terms collectively

(25 Jan '15, 03:28) rahul_nexus2★

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

link

answered 14 May '14, 15:06

razkverma's gravatar image

2★razkverma
1
accept rate: 0%

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

link

answered 18 May '14, 04:41

abhishek1995's gravatar image

3★abhishek1995
311
accept rate: 0%

@darkshadows http://www.codechef.com/viewsolution/3915467

Could anyone point out the mistake in this ? Seems correct :( Thanks

link

answered 22 May '14, 15:22

thezodiac1994's gravatar image

6★thezodiac1994
1.0k61122
accept rate: 16%

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.

link

answered 05 Jun '14, 22:46

siddv29's gravatar image

2★siddv29
1124
accept rate: 0%

-1

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

link

answered 12 May '14, 18:09

kevind's gravatar image

1★kevind
1482312
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 ♦♦3★

@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

link

answered 17 May '14, 19:51

shoumik's gravatar image

3★shoumik
01
accept rate: 0%

edited 17 May '14, 23:50

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,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