HackerRank Probability – Vertical Sticks

Challenge: Vertical Sticks

Subdomeniu: Probability (probability)

Scor cont: 50.0 / 50

Submission status: Accepted

Submission score: 1.0

Submission ID: 464732323

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/vertical-sticks/problem

Cerință

Given an array of integers Y=[y_1, y_2, …, y_n], we have n line segments, such that, the endpoints of i-th segment are (i, 0) and (i, y_i). Imagine that from the top of each segment a horizontal ray is shot to the left, and this ray stops when it touches another segment or it hits the y-axis. We construct an array of n integers, [v_1, v_2, …, v_n], where v_i is equal to length of ray shot from the top of segment i. We define V(y_1, y_2, …, y_n) = v_1 + v_2 + … + v_n.

For example, if we have Y=[3,2,5,3,3,4,1,2], then v_1, v_2, …, v_8 = [1,1,3,1,1,3,1,2], as shown in the picture below:

For each permutation p of [1, 2, …, n], we can calculate V(y_p_1, y_p_2, …, y_p_n). If we choose a uniformly random permutation p of [1, 2, …, n], what is the expected value of V(y_p_1, y_p_2, …, y_p_n)?

Input Format

Output Format

Cod sursă

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 50;
int t, n, arr[N];
double dp[N + 1];

int main() {
    for (cin >> t; t--;) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        double result = 0;
        for (int i = 0; i < n; i++) {
            int gte = 0;
            for (int j = 0; j < n; j++)
                if (arr[i] <= arr[j])
                    gte++;
            gte--;
            for (int j = 1; j <= n; j++) {
                dp[0] = j;
                for (int k = 1; k < j; k++) {
                    double p = (double)gte / (double)(n - j + k);
                    dp[k] = p * (j - k) + (1 - p) * dp[k - 1];
                }
                result += dp[j - 1] / n;
            }
        }
        cout.precision(2);
        cout.setf(ios::fixed | ios::showpoint);
        cout << result << endl;
    }
    return 0;
}