We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
interesting problem; fairly straightforward once you think about it for a bit. some hints that may prove helpful if you're stuck:
[spoiler]
1) use [1,a] for the range instead of [a,b]:
f([a+1,b]) = (f([1,b])*b-f([1,a])*a)/(b-a) due to the linearity of expected value/probability
2) find the ev/prob for each i-bit subset of the range (ie numbers between 2^i and 2^(i+1)) separately and then linearly combine them at the end. this way the same algorithm can be used for both parts of the problems - just multiply each prob by i to convert from probability to the expected number of bits or divide to go in the opposite direction
3) the range spanned by the most significant bit (msb) can be written as a linear combination of i-bit ranges (with prefix bits)
I am getting segmentation fault for test cases 11-14. I suspect stack overflow. Any advice?
interesting problem; fairly straightforward once you think about it for a bit. some hints that may prove helpful if you're stuck:
[spoiler]
1) use [1,a] for the range instead of [a,b]:
f([a+1,b]) = (f([1,b])*b-f([1,a])*a)/(b-a) due to the linearity of expected value/probability
2) find the ev/prob for each i-bit subset of the range (ie numbers between 2^i and 2^(i+1)) separately and then linearly combine them at the end. this way the same algorithm can be used for both parts of the problems - just multiply each prob by i to convert from probability to the expected number of bits or divide to go in the opposite direction
3) the range spanned by the most significant bit (msb) can be written as a linear combination of i-bit ranges (with prefix bits)
[/spoiler]
terminated due to time out