You are not logged in. Please login at www.codechef.com to post your questions!

×

MINVOTE - Editorial

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

This question is marked "community wiki".

asked 12 Mar, 14:25

adkroxx's gravatar image

7★adkroxx
306718
accept rate: 7%

edited 13 Mar, 15:04

admin's gravatar image

0★admin ♦♦
19.3k348495534


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.

link

answered 13 Mar, 12:26

pshishod2645's gravatar image

5★pshishod2645
47410
accept rate: 16%

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.

link

answered 12 Mar, 19:36

kdark884's gravatar image

5★kdark884
531
accept rate: 0%

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

link

answered 15 Mar, 00:56

abhi007rider's gravatar image

2★abhi007rider
122
accept rate: 0%

that's why too many submissions came for this problem :p

(15 Mar, 01:13) harrypotter02★

Setter and tester solution is showing Access Denied!!

link

answered 12 Mar, 16:58

chunky_2808's gravatar image

3★chunky_2808
1538
accept rate: 4%

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

link

answered 12 Mar, 19:17

shivansh100's gravatar image

4★shivansh100
1
accept rate: 0%

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

link

answered 13 Mar, 09:43

pmj642_coder's gravatar image

3★pmj642_coder
1
accept rate: 0%

@pshishod2645
How did u got this equation
ai−1=ai−1+ai−2....+a1 for all 1< i ≤n

link

answered 13 Mar, 17:49

sagar57patil57's gravatar image

3★sagar57patil57
1
accept rate: 0%

What a simple solution ! :o

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

Feeling embarrassed

link

answered 13 Mar, 18:30

avwl017's gravatar image

4★avwl017
1
accept rate: 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 !

link

answered 20 Mar, 20:18

shivan111's gravatar image

2★shivan111
101
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,006
×1,487
×941
×264
×8

question asked: 12 Mar, 14:25

question was seen: 4,764 times

last updated: 20 Mar, 20:18