MINVOTE - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Div1, Div2

Practice

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)

AUTHOR’S AND TESTER’S SOLUTIONS

Setter’s solution

Tester’s solution

2 Likes
2

Setter and tester solution is showing Access Denied!!

3

The alternate solution given above should take O(n^2) for the worst case…??
Then how it’s working

4

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.

2 Likes
5

Yeah, but still I’m not able to figure out the time complexity O(N*Log N).

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.

6 Likes
7

@pshishod2645

How did u got this equation

ai−1=ai−1+ai−2…+a1 for all 1< i ≤n

8

What a simple solution ! :o

I used fenwick tree for suffix and prefix distances, I also had to sort queries offline :confused:

Feeling embarrassed

9

this also can be done with the help of vector using upper bound and lower bound and we have to compute prefix sum also !!

1 Like
10

that’s why too many submissions came for this problem :stuck_out_tongue:

11

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 !

12

Nice Question! Can be solved easily by efficient range update and binary_search for lower bound in left and right direction for each index.