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.0k348495531


12next »

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
4577
accept rate: 23%

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%

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

2★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

1★pmj642_coder
1
accept rate: 0%

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

pshishod2645's gravatar image

5★pshishod2645
4577
accept rate: 23%

I was quite disappointed when brute force passed all tests. But I can't skip this learning.

link

answered 13 Mar, 17:22

abhidoeslinux's gravatar image

3★abhidoeslinux
576
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%

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:

×14,366
×1,398
×810
×264
×8

question asked: 12 Mar, 14:25

question was seen: 4,471 times

last updated: 20 Mar, 20:18