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)