×

# CHONQ - Short Editorial

$$T[i] = \sum_{j=i}^{N} \lfloor\frac{arr[j]}{j-i+1}\rfloor$$

# Brute Force: $O(N^2)$

The naive solution is easy to see, for each index, starting from the left calculate the tolerance value(the equation given) in $O(N)$ and stop as soon as you find the value <= K

To more efficient solution

Instead of adding the contribution of elements from the right of an index, we would take elements one by one from right and add its contribution to every index on its left. Also, it is easy to see that an element contributes only indices left to it.

$$f(i, j) = \lfloor \frac{arr[i]}{(i-j+1)} \rfloor$$

f(i, j) is the contribution of element i to the index j, clearly if j > i then the contribution is 0

### OBSERVATION 1

An element stop contributing to indices which are at distance greater then the element value.

### OBSERVATION 2

The sequence of contribution of an element to the left only decreases.

This comes from the fact that, as j recedes away from i, denominator in f(i, j) increases

### OBSERVATION 3

There are atmost 2*$\\sqrt{arr[i]}$ distinct value of f(i, j).

This is same as saying, $\\lfloor \\frac{N}{i} \\rfloor$, as i goes from N to i, has at most 2*$\\sqrt{N}$ distinct values. For all i greater then $\\sqrt{N}$ the value of $\\lfloor \\frac{N}{i} \\rfloor$ will lie between [1, $\\sqrt{N}$]. Thus there can be at most 2*$\\sqrt{N}$ distinct value.

Since there are only O($\\sqrt{arr[i]}$) values to fill arr[i] places and sequence only decreases, it is easy to conclude number forms a contiguous segment.

We are now in a position to do range update instead of point updates. We would be doing O($\\sqrt{arr[i]}$) range updates as only these many distinct elements will emanate from arr[i]

Example: Let the last element be 39, here is how its contribution to different indices would look like

. . .0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 10 10 10 10 4 4 5 6 7 9 13 19 39

Only thing left to do is to figure out the range endpoints. Which I believe one can figure out if one draws some examples on paper

For range updates use difference array as they give O(1) updation time

After seeing a increasing/decreasing sequence I was tempted to binary search the range endpoints, turned out TL is strict enough to not let that pass.

Only O(1) update and O(1) range endpoint calculation passes, i am inclined to believe

Total time Complexity: $\mathcal{O}(N\sqrt{N})$

My Submission

706
accept rate: 0%

How did you arrive at the conclusion of your third observation?

(13 Mar, 17:37)
1

Nice observation, Good work bro

(13 Mar, 19:45)

 0 This is a very useful trick that I'll have to contemplate further on. I also wanted to comment that, if the problem statement is changed to not use floor function, but rather standard floating point division, then the problem could be solved even faster - in O(n.logn) time using FFT, as then it could be cast as a standard convolution problem for the arrays [a1, a2, ..., an] and [1/n, 1/(n-1), ..., 1/2, 1] answered 13 Mar, 17:55 1 accept rate: 0%
 0 I was able to make my binary search approach pass the tests by using precomputation and observing that the range on which you have to apply binary search decreases over time. answered 13 Mar, 18:12 4★kmampent 455●1●7●7 accept rate: 14% Good job there (13 Mar, 18:34)
 0 Should the first equation be $$T[i] = \sum_{j=i}^{N}\lfloor\frac{arr[j]}{j-i+1}\rfloor$$ ? answered 13 Mar, 21:07 1 accept rate: 0% Yes, it should. Edited (13 Mar, 21:39)
 0 https://www.codechef.com/viewsolution/23579984 I had the same approach but I don't know why am I having tle. I am stuck on this question for past week . Please suggest where i went wrong. P.S: while suggesting the optimizations can you implement them and check if its passing the time constrain? answered 14 Mar, 18:03 5★alpha16 1 accept rate: 0% you can pre-calculate the range endpoints for every number upto 1e5. This is what I have been told to do. for example range[10] = [1, 2, 3, 4, 6, 11]. number changes at these thresholds. Rest is same. (14 Mar, 19:07)
 0 I am not able to understand the third observation. In your comment you wrote that $N/i$ can have atmost $2*\sqrt{N}$ distinct values and that is fine because $i$ lies in the range$[1, N]$. But in the question we have to find out the value of terms like $\cfrac{arr[i]}{den}$ where the $den$ variable lies in the range $[1, last possible index]$. So how can you apply that logic here since this possible range has nothing to do with the numerator $arr[i]$ answered 14 Mar, 19:47 3★vir_mis 15●2 accept rate: 33% 1 After den goes over arr[i], result of $\frac{arr[i]}{den}$ will be 0. So Effective range of den is always [1, min(i, arr[i])] (14 Mar, 21:55)
 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:

×968