$$T[i] = \sum_{j=i}^{N} \lfloor\frac{arr[j]}{ji+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]}{(ij+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 1An element stop contributing to indices which are at distance greater then the element value. OBSERVATION 2The 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 3There 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 Submissionasked 13 Mar, 16:06

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/(n1), ..., 1/2, 1] answered 13 Mar, 17:55

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

Should the first equation be $$T[i] = \sum_{j=i}^{N}\lfloor\frac{arr[j]}{ji+1}\rfloor$$ ? answered 13 Mar, 21:07

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
you can precalculate 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)

How did you arrive at the conclusion of your third observation?
Nice observation, Good work bro