DIFFICULTY:
Medium
PREREQUISITES:
Two Pointers
PROBLEM:
Alice is a college student. Her favourite subject is Statistics and probability. For testing her Bob, his friend gives her a question. Bob give her a list LL of NN integers, and an integer TT, and ask after that he will choose two numbers LL and RR randomly such that 0≤L≤R≤N0≤L≤R≤N. He asked Alice to find the probability that sum{A[L], … A[R]} <= T.
Help Alice to find the probability.
EXPLANATION:
We know that the total number of possible L, R pairs would be n*(n-1)/2. Now we simply need to calculate the number of sequences that would have sum <= T and divide to get the probability. To do this we can use the two-pointer technique by maintaining a left pointer and a right pointer and incrementing the right pointer until the sum(of numbers between the left pointer and the right pointer) is <= T and then only incrementing the left pointer.
TIME COMPLEXITY:
O(NlogN)
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
using namespace std;
#define M 2*100005
#define MAX (int)1e9
int main(){
double n , t , a , b , sum = 0;
cin >> n >> t;
double poss = (n*(n+1))/2, valid = 0;
vector<long long> v(n);
for(int i=0; i<n ; i++) cin >> v[i];
a = 0 , b = 1 , sum = v[0];
if(sum <= t) valid++;
while(b < n){
sum += v[b];
while(sum > t && a<b) sum -= v[a] , a++;
if(sum <= t) valid += (b-a+1);
b++;
}
}