Bitwisdom
2015 TCO Parallel 2B · 2015-04-08 · by zxqfl
2015 TCO Parallel 2B · 2015-04-08 · by zxqfl · Math
Problem Statement
Problem Statement
In this problem we are dealing with a string of N bits, numbered from 0 to N-1.
Julia likes the string that consists of N zeros.
If you give her any N-bit string, she will convert it into a string of N zeros using the smallest possible number of actions.
An action consists of selecting an integer k (1 <= k <= N) and flipping either the first k bits or the last k bits of the string.
Formally, Julia can flip either all bits with number i such that i < k or all bits with number i such that i >= N - k.
You are going to generate a random string of N bits.
You are given aint[] p with N elements.
For each i, bit number i has a p[i] percent chance of being a 1 and a (100 - p[i]) percent chance of being a 0.
The values of the bits are chosen independently from each other.
After you generate the string, you are going to give it to Julia.
Please find and return the expected number of actions Julia will take.
Julia likes the string that consists of N zeros.
If you give her any N-bit string, she will convert it into a string of N zeros using the smallest possible number of actions.
An action consists of selecting an integer k (1 <= k <= N) and flipping either the first k bits or the last k bits of the string.
Formally, Julia can flip either all bits with number i such that i < k or all bits with number i such that i >= N - k.
You are going to generate a random string of N bits.
You are given a
For each i, bit number i has a p[i] percent chance of being a 1 and a (100 - p[i]) percent chance of being a 0.
The values of the bits are chosen independently from each other.
After you generate the string, you are going to give it to Julia.
Please find and return the expected number of actions Julia will take.
Notes
- When a bit is flipped, its value changes. If the bit is originally 1, it will become 0. If it is originally 0, it will become 1.
- Your answer must have an absoute or relative error not exceeding 10^(-9).
Constraints
- N will be between 1 and 300, inclusive.
- p will contain exactly N elements.
- Each element of p will be between 0 and 100, inclusive.
Examples
0)
{100, 100, 100}
Returns: 1.0
All of the bits are guaranteed to be 1, and Julia can set them all to 0 in a single action.
1)
{50, 50}
Returns: 0.75
There is a 25% chance that all of the bits are 0, in which case Julia will do nothing. All other configurations allow Julia to clear the field in 1 action, so the answer is 0.75 * 1 = 0.75.
2)
{0, 40, 50, 60}
Returns: 1.4
3)
{37, 63, 23, 94, 12}
Returns: 2.6820475464
4)
{84, 52, 93, 11, 25, 89, 20, 55, 1, 2, 77, 14, 3, 51, 25, 22, 74, 67, 47, 47, 27, 62, 42, 83, 92, 41, 53, 48, 0, 48, 45, 45, 93, 35, 96, 87, 22, 13, 51, 85, 12, 75, 53, 12, 80, 75, 77, 43, 86, 74, 34, 35, 10, 11, 55, 48, 46, 54, 80, 95, 19, 80, 29, 28, 44, 27, 23, 6, 25, 81, 87, 60, 29, 77, 45, 80, 33, 82, 100, 100, 90, 64, 22, 33, 16, 68, 45, 31, 57, 69, 50, 36, 85, 85, 32, 35, 57, 21, 54, 82, 19, 9, 42, 25, 10, 28, 53, 37, 91, 65, 83, 65, 97, 32, 28, 55, 6, 10, 72, 83, 4, 12, 9, 76, 49, 91, 82, 7, 70, 97, 50, 3, 58, 42, 57, 3, 46, 10, 46, 36, 78, 58, 29, 7, 49, 56, 90, 68, 35, 33, 91, 66, 2, 31, 0, 87, 98, 64, 95, 86, 18, 32, 23, 0, 10, 73, 92, 11, 76, 81, 44, 46, 14, 16, 77, 40, 18, 79, 15, 44, 19, 65, 80, 78, 41, 44, 36, 69, 29, 59, 39, 47, 37, 29, 19, 100, 71, 100, 90, 10, 42, 33, 1, 14, 67, 64, 7, 96, 26, 71, 25, 99, 32, 15, 66, 27, 57, 31, 77, 38, 47, 46, 81, 89, 68, 29, 17, 50, 78, 84, 17, 47, 92, 14, 19, 45, 11, 32, 18, 31, 75, 40, 18, 91, 96, 86, 85, 68, 84, 13, 88, 96, 19, 75, 6, 38, 20, 20, 24, 17, 62, 80, 55, 70, 12, 17, 95, 52, 43, 34, 7, 92, 55, 54, 5, 46, 94, 1, 81, 93, 21, 55, 96, 51, 39, 47, 68, 79, 69, 99, 50, 12, 70, 32, 50, 99, 56, 68, 97, 59}
Returns: 145.5516
Submissions are judged against all 38 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Bitwisdom with a public method double expectedActions(vector<int> p) · 38 test cases · 2 s / 256 MB per case