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

×

CHONQ - Short Editorial

4
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

asked 13 Mar, 16:06

aparichit_vyav's gravatar image

4★aparichit_vyav
706
accept rate: 0%

edited 13 Mar, 21:58

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

(13 Mar, 17:37) epsilonalpha4★
1

Nice observation, Good work bro

(13 Mar, 19:45) vipin14075★

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

link

answered 13 Mar, 17:48

dilbwag1's gravatar image

3★dilbwag1
1
accept rate: 0%

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)

(13 Mar, 18:17) aparichit_vyav4★

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

(13 Mar, 21:38) dilbwag13★

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 Mar, 21:58) aparichit_vyav4★

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]

link

answered 13 Mar, 17:55

hungrykoala's gravatar image

3★hungrykoala
1
accept rate: 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.

link

answered 13 Mar, 18:12

kmampent's gravatar image

4★kmampent
455177
accept rate: 14%

Good job there

(13 Mar, 18:34) aparichit_vyav4★

Should the first equation be $$T[i] = \sum_{j=i}^{N}\lfloor\frac{arr[j]}{j-i+1}\rfloor$$ ?

link

answered 13 Mar, 21:07

chehsunliu's gravatar image

3★chehsunliu
1
accept rate: 0%

Yes, it should. Edited

(13 Mar, 21:39) aparichit_vyav4★

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?

link

answered 14 Mar, 18:03

alpha16's gravatar image

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) aparichit_vyav4★

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

link

answered 14 Mar, 19:47

vir_mis's gravatar image

3★vir_mis
152
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) aparichit_vyav4★
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:

×968

question asked: 13 Mar, 16:06

question was seen: 1,642 times

last updated: 14 Mar, 21:55