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, 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, 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, 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, 00:56

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

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

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

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

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, 12:27

I was quite disappointed when brute force passed all tests. But I can't skip this learning. answered 13 Mar, 17:22

@pshishod2645 answered 13 Mar, 17:49
