## PROBLEM LINK:

**Author:** Praveen Dhinwa

**Tester:** Triveni Mahatha

**Editorialist:** Adarsh Kumar

## DIFFICULTY:

Easy-Medium

## PREREQUISITES:

Binary search

## PROBLEM:

You are given an array A of N positive integers. For all i, you need to find number of such j (j \ne i) for which sum of number between (i,j) (both exclusive) is less than or equal to j^{th} element.

## EXPLANATION:

I will try to explain the most straight forward solution that is easy to think at first.

We will try to iterate over every minion j and try to find ranges of minion that will get voted by j^{th} minion. For i^{th} minion to get voted from j^{th} one following condition must be satisfied: A[j] \ge sum(i,j).

Let’s just solve for the case i>j. We can extend this one for the case i < j too using the similar argument. You can observe that right side of our condition is an increasing function while the left side is a constant. We can use binary search on i to find the break-point now. Now you just need to add 1 to the range (j+1,\text{last_valid_i}).

This problem reduces to offline range update and point query at every point. There are many possible ways of doing this. One of them uses DP with O(n) time complexity. I will describe that one in brief.

Say, you are given q updates (l_i,r_i), where in each update you need to add 1 to the range (l_i,r_i). Also, in the end you are required to report all the values of the array. A simple pseudocode for solving this task:

```
# arrays are initialized with zeroes
A[0...(N+1)] # Our oiginal array
for i=1...q:
A[r_i]+=1
A[l_i-1]-=1
for i=N...1:
A[i]+=A[i+1] # A[i] now contains the final value at ith position
```

## ALTERNATE SOLUTION

Even a solution that will look like a brute force at first sight is sufficient. Let’s take a look at pseudocode:

```
j = 1 to N:
i = j+1 to N:
if sum(i,j) > A[j]:
break
ans[i]+=1
i = j-1 to 1:
if sum(i,j) > A[j]:
break
ans[i]+=1
```

ans[i] in the above pseudocode stores number of votes received by each minion. Time complexity of the above solution is O(N.log(MAX)). Proof is left as an exercise to reader.

## Time Complexity:

O(N.logN)