PROBLEM LINK:Div1, Div2 DIFFICULTY:EasyMedium 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 breakpoint 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:
ALTERNATE SOLUTIONEven a solution that will look like a brute force at first sight is sufficient. Let's take a look at pseudocode:
$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)$ AUTHOR'S AND TESTER'S SOLUTIONS
This question is marked "community wiki".
asked 12 Mar '18, 14:25

Here is my explanation for the time complexity. Consider the worst case situation. $(a_1, a_2...., a_n)$are such that $a_i>a_{i1} + a_{i2} .....+a_1 $ for all $1<{i}\leq{n}$. For extreme case we have, $$a_i1=a_{i1}+a_{i2}....+a_1 \text{for all } 1<{i}\leq{n}$$ $$a_i1=a_{i1}+(a_{i2}....+a_1)$$ $$a_i1=a_{i1} + a_{i1}1, \text{which gives } a_i=2a_{i1}$$ Now, if the loop goes from $j$ to $j+k$ , it follows the above condition, implies $$ a_{j+k} > 2^ka_{j} \text { which gives } {k}<{ \log_2{(a_{j+k} / a_j)} }$$ $$k=O(\log{MAX})$$ where $MAX$ is the maximum element in $a[1.....n]$. Hence the time complexity $O(N\log{MAX})$........ If you understand my explanation please upvote as I need karma points to ask questions ( I don't have any now ).... You can ask any doubt regarding explantation. answered 13 Mar '18, 12:26

Alternate solution looks like O(n^2). but it's not. Think about the worst case values (power of 2's).
[64, 32, 16, 8, 4, 2]... in this array each number will go to the end value, so O(n^2). answered 12 Mar '18, 19:36

this also can be done with the help of vector using upper bound and lower bound and we have to compute prefix sum also !! answered 15 Mar '18, 00:56

Setter and tester solution is showing Access Denied!! answered 12 Mar '18, 16:58

The alternate solution given above should take O(n^2) for the worst case...?? Then how it's working answered 12 Mar '18, 19:17

Yeah, but still I'm not able to figure out the time complexity O(N*Log N). answered 13 Mar '18, 09:43

@pshishod2645 answered 13 Mar '18, 17:49

What a simple solution ! :o I used fenwick tree for suffix and prefix distances, I also had to sort queries offline :/ Feeling embarrassed answered 13 Mar '18, 18:30

This question requires you to calculate the prefix sum beforehand but you also need to start the solution with the optimal approach of selecting the "voter" first and iterating over the rest of the "candidates". Its amazing how a simple hack can reduce the complexity ! answered 20 Mar '18, 20:18

Nice Question! Can be solved easily by efficient range update and binary_search for lower bound in left and right direction for each index. answered 02 Feb, 19:37
