HackerRank Coder Trophy challenges @ https://www.hackerrank.com/codertrophy/challenges

randomsum.cpp

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 100000
static unsigned long long N,T;
static unsigned long long d[MAXN+5];
static unsigned long long lookup[MAXN+5];

int main()
{
    scanf("%d%d", &N,&T);
    int num_elem = N;
    N++;
    d[0]=0;
    for(int i=1; i<N; i++)
        scanf("%d", &d[i]);

    unsigned long long sum = 0LL;
    for(int i=0; i<N; i++)
    {
        sum += d[i];
        lookup[i] = sum;
    }

    unsigned long long num = 0LL, diff = 0LL;
    int last_success = 1;
    for(int i=0; i<N; i++)
        for(int j=N-1; j>=last_success; j--)
      {
        	if (lookup[j]-lookup[i]<=T)
            {
                last_success = j;
                num += j-i;
                break;
            }
    	}

    double count = (double) (num_elem+1)*(num_elem)/2;
    printf("%f", num/count);
    return 0;
}

randomsum.txt

Random Array Sum

Given a list D of N integers, and an integer T, two numbers L and R are randomly chosen such that 0 ≤ L ≤ R < N.
What is the probability that sum{D[L],… D[R]} <= T ?

Input Format:
The first line will contain two numbers: N and T. N lines follow, each containing one number from list D.

Output Format:
Output one number P to a maximum of 8 decimal places, the probability that sum{D[L],… D[R]} <= T.

Constraints:
1 <= N < 100000
0 <= D[i] < 1e7

Sample Input:
5 10
4 
5 
3 
7
1

Sample Output:
0.6

Explanation
[4,5,3,7,1]
[4],[5],[3],[7],[1],[4,5],[5,3],[3,7],[7,1]
out of possible 15.
thus 9/15 = 0.6

randomsumexpected.cpp

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

#define FOR(i,a,b)   for(int(i)=int(a);(i)<int(b);(i)++)

#define MAXN 100000

static unsigned long long N,T;
static unsigned long long d[MAXN+5];
static unsigned long long lookup[MAXN+5];
static unsigned long long lookup2[MAXN+5];

int main() {
    scanf("%d%d", &N,&T);
    N++;
    d[0]=0;
    FOR(i,1,N)
    {
        scanf("%d", &d[i]);
    }
/*
    FOR(i,0,N)
        printf("%d ", d[i]);
    printf("\n");
*/
    unsigned long long sum = 0LL;
    FOR(i,0,N)
    {
        sum += d[i];
        lookup[i] = sum;
        //printf("%d ", lookup[i]);
    }
    //printf("\n");

    sum = 0LL;
    FOR(i,0,N+1)
    {
        sum += lookup[i];
        lookup2[i] = sum;
        //printf("%d ", lookup2[i]);
    }
    //printf("\n");

    unsigned long long total = 0LL;
    unsigned long long num = 0LL;
    unsigned long long diff = 0LL;
    int last_success = 1;
    FOR(i,0,N)
        for(int j=N-1; j>=last_success; j--)
    	{
            diff = lookup[j]-lookup[i];
        	if (diff<=T)
            {
                last_success = j;
                //printf("%d: last_success=%d\n", i,last_success);
                total += lookup2[j]-(j-i)*lookup[i]-lookup2[i];
                num += j-i;
                break;
            }
    	}

    printf("%f", total/(double)num);
    return 0;
}

randomsumexpected.txt

Random Sum - Expected Sum

Given an a list D of N integers, and an integer T, two numbers L and R are randomly chosen such that 0≤L≤R<N.
What is the expected sum of the subarray {d[L]…d[R]} given that (sum{d[L],…d[R]} <= T)?

Input Format:
The first line will contain two numbers: N and T. N lines follow, each containing one number from list D.

Output Format:
Output one number P, the expected sum of D[L]…D[R] upto 9 decimal places.

Constraints:
1 <= N < 100000
0 <= D[i] < 10^7
0 < T <= 10^9

Sample Input:
5 10
4 
5 
3 
7
1

Sample Output:
6.111111111

Explanation
[4],[5],[3],[7],[1],[4,5],[5,3],[3,7],[7,1] subarrays satisfy the property.
4 + 5 + 3 + 7 + 1 + 9 + 8 + 10 + 8 = 55
55/9 = 6.11111111