CHONQ - Short Editorial

general
1

Link To Problem

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

4 Likes
2

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

3

Please explain the third observation by taking an example more robustly.

4

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]

5

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.

6

say N = 10, then all you want to see is that the value of N/i , where i goes from 1 to 10, have atmost 2*root(N) distinct values.

divide [1, N] in two ranges, A = [1, root(N)] and B = (root(N), N].

for every value of i in A, N / i would lie in (root(N), N] actually we dont care where they lie, the point is there can be at most root(N) distinct value of N/i if i is in A. Because i goes from 1 to root(N) only.

When i is in B, the result of N/i would lie in A, that is in the range [1, root(N)], so N/i have only root(N) value to take for every i in the range(root(N), N].

Total = 2*root(N)

7

Good job there

8

Nice observation, Good work bro

1 Like
9

Should the first equation be

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

?

10

Okay Thank you.
And also did not understand how are we able to do range updates?
Can you please explain that too?

11

Yes, it should. Edited

12

Adding x to index i would mean we added x to all indices >= i.

So, if we have to add x to range [L, R] we should do

arr[L] += x
arr[R+1] -= x.

After doing all updates take the prefix array.

arr = [0, 0, 0, 0, 0]
add 3 to [2, 4]
arr = [0, 3, 0, 0, -3]
add -5 to [1, 3]
arr = [-5, 3, 0, 5, -3]
add 1 to [3, 5]
arr = [-5, 3, 1, 5, -3]

Now take the prefix sum of indices
arr = [-5, -2, -1, 4, 1]. Verify this

13

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?

14

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.

15

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]

16

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])]

1 Like