Soluție HackerRank pentru Random, subdomeniul Probability, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Random
- Domeniu: Probability
- Limbaj: C++14
Challenge: Random
Subdomeniu: Probability (probability)
Scor cont: 100.0 / 100
Submission status: Accepted
Submission score: 1.0
Submission ID: 464737292
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/random/problem
Cerință
Given an array 'D' with n elements: d[0], d[1], ..., d[n-1], you can perform the following two steps on the array.
1. Randomly choose two indexes (l, r) with l < r, swap (d[l], d[r])
2. Randomly choose two indexes (l, r) with l < r, reverse (d[l...r]) (both inclusive)
After you perform the first operation a times and the second operation b times, you randomly choose two indices l & r with l < r and calculate the S = sum(d[l...r]) (both inclusive).
Now, you are to find the expected value of S.
Input Format
The first line of the input contains 3 space separated integers - n, a and b.
The next line contains n space separated integers which are the elements of the array *d*.
n a b
d[0] d[1] ... d[n-1]
Output Format
Print the expected value of S.
E(S)
Constraints
2 <= n <= 1000
1 <= a <= 10<sup>9</sup>
1 <= b <= 10
The answer will be considered correct, if the absolute or relative error doesn't exceed 10<sup>-4</sup>.
Sample Input #00:
3 1 1
1 2 3
Sample Output #00:
4.666667
Explanation #00:
At step 1):
You have three choices:
1. swap(0, 1), 2 1 3
2. swap(0, 2), 3 2 1
3. swap(1, 2), 1 3 2
At step 2):
For every result you have three choices for reversing:
1. [2 1 3] -> [1 2 3] [3 1 2] [2 3 1]
2. [3 2 1] -> [2 3 1] [1 2 3] [3 1 2]
3. [1 3 2] -> [3 1 2] [2 3 1] [1 2 3]
So you have 9 possible arrays with each having a 1/9 probability.
For the last step:
Each of the 9 arrays will have 3 possible sums with equal probability. For [1 2 3], you can get 1+2, 2+3 and 1+2+3.
Since there will be 27 outcome for this input, one can calculate the expected value by finding sum of all 27 S and dividing it by 27.
Cod sursă
#include <algorithm>
#include <cstdio>
#define MAX_N 1000
using namespace std;
float g[MAX_N][MAX_N], h[2][MAX_N];
int k[MAX_N], d[MAX_N];
int remove_space() {
int ch;
while (true) {
ch = getchar_unlocked();
if (ch != ' ' && ch != '\n')
break;
}
return ch;
}
template<typename T> T read_unsigned_integer() {
T result = (T) 0;
int ch = remove_space();
while (ch >= '0' && ch <= '9') {
result = 10 * result + (ch - '0');
ch = getchar_unlocked();
}
return result;
}
template<typename T> T read_signed_integer() {
T result = (T) 0;
bool flip = false;
int ch = remove_space();
if (ch == '-') {
flip = true;
ch = remove_space();
}
while (ch >= '0' && ch <= '9') {
result = 10 * result + (ch - '0');
ch = getchar_unlocked();
}
return flip ? -result : result;
}
pair<float, float> get_pair(pair<float, float> x, pair<float, float> y) {
float q = x.second * y.second;
float p = (x.first + x.second) * (y.first + y.second) - q;
return make_pair(p, q);
}
pair<float, float> get_pow(pair<float, float> x, int e) {
pair<float, float> result(0.0f, 1.0f);
pair<float, float> base = x;
if (e > 0) {
while (true) {
if (e & 1) {
result = get_pair(result, base);
}
e >>= 1;
if (e <= 0)
break;
base = get_pair(base, base);
}
}
return result;
}
void solve() {
int n, a, b;
n = read_unsigned_integer<int>();
a = read_unsigned_integer<int>();
b = read_unsigned_integer<int>();
for (int i = 0; i < n; i++)
d[i] = read_signed_integer<int>();
float s = 2.0f / (n - 1) , t = (float) (n - 3) / (n - 1);
pair<float, float> coef = get_pow(make_pair(s, t), a);
coef.first /= n;
int m = n * (n - 1) / 2;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
int l = min(i, j) + 1;
int r = n - max(i, j);
int x = min(l, r) - (i == j);
k[j] += x;
if (i == j)
x += i * (i - 1) / 2 + (n - 1 - i) * (n - 1 - i - 1) / 2;
g[i][j] = (float) x / m;
}
long long sum = 0;
for (int i = 0; i < n; i++) {
sum += d[i];
h[0][i] = d[i];
}
int p = 0;
for (int k = 0; k < b; k++) {
float *alpha = h[p];
p ^= 1;
float *beta = h[p];
for (int i = 0; i < n; i++) {
beta[i] = 0.0;
for (int j = 0; j < n; j++)
beta[i] += g[i][j] * alpha[j];
}
}
for (int i = 0; i < n; i++)
h[p][i] = coef.first * sum + coef.second * h[p][i];
float result = 0.0;
for (int i = 0; i < n; i++)
result += k[i] * h[p][i];
result /= m;
printf("%f\n", result);
}
int main() {
solve();
return 0;
}