×

# MINVOTE - Editorial

Div1, Div2
Practice

Author: Praveen Dhinwa
Tester: Triveni Mahatha

Easy-Medium

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)$

# AUTHOR'S AND TESTER'S SOLUTIONS

This question is marked "community wiki".

306719
accept rate: 7%

19.7k350498541

 6 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_{i-1} + a_{i-2} .....+a_1$ for all $1<{i}\leq{n}$. For extreme case we have, $$a_i-1=a_{i-1}+a_{i-2}....+a_1 \text{for all } 1<{i}\leq{n}$$ $$a_i-1=a_{i-1}+(a_{i-2}....+a_1)$$ $$a_i-1=a_{i-1} + a_{i-1}-1, \text{which gives } a_i=2a_{i-1}$$ 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 825●1●12 accept rate: 13%
 2 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). But we cannot create the worst case array for large array length. An array of power of 2's will reach 10^9 just with 31 element. answered 12 Mar '18, 19:36 5★kdark884 53●1 accept rate: 0%
 1 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 12●2 accept rate: 0% that's why too many submissions came for this problem :p (15 Mar '18, 01:13)
 0 Setter and tester solution is showing Access Denied!! answered 12 Mar '18, 16:58 164●9 accept rate: 4%
 0 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 11●2 accept rate: 0%
 0 Yeah, but still I'm not able to figure out the time complexity O(N*Log N). answered 13 Mar '18, 09:43 1 accept rate: 0%
 0 @pshishod2645 How did u got this equation ai−1=ai−1+ai−2....+a1 for all 1< i ≤n answered 13 Mar '18, 17:49 1 accept rate: 0%
 0 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 3★avwl017 11●1 accept rate: 0%
 0 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 10●1 accept rate: 0%
 0 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 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,629
×1,668
×1,038
×265
×8

question asked: 12 Mar '18, 14:25

question was seen: 5,158 times

last updated: 02 Feb, 19:37