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

Cerinta

Given an array of integers $Y=[y_1, y_2, \ldots, 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, \ldots, 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, \ldots, y_n) = v_1 + v_2 + \ldots + v_n$.  
<br>
For example, if we have $Y=[3,2,5,3,3,4,1,2]$, then $v_1, v_2, \ldots, v_8 = [1,1,3,1,1,3,1,2]$, as shown in the picture below:

<img src="https://s3.amazonaws.com/hr-challenge-images/65/1466136228-1e0f816996-vertical.png" title="vertical.png" />

For each permutation $p$ of $[1, 2, \ldots, n]$, we can calculate $V(y_{p_1}, y_{p_2}, \ldots, y_{p_n})$. If we choose a uniformly random permutation $p$ of $[1, 2, \ldots, n]$, what is the expected value of $V(y_{p_1}, y_{p_2}, \ldots, y_{p_n})$?

Input Format

The first line contains a single integer _T_ (1 <=_T_<= 100). _T_ test cases follow.  
The first line of each test-case is a single integer _N_ (1 <= _n_ <= 50), and the next line contains positive integer numbers $y_1, y_2 ..., y_n$ separated by a single space ($0 < y_i <= 1000$).

Output Format

For each test-case output expected value of $V(y_{p_1}, y_{p_2}, \ldots, y_{p_n})$, rounded to two digits after the decimal point.

Cod sursa

#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;
}