×

# CHONQ - EDITORIAL

Setter: Volodymyr Mykytsei
Tester: Encho Mishinev
Editorialist: Taranpreet Singh

Medium

# PREREQUISITES:

Basic Maths and difference arrays.

# PROBLEM:

In a queue with $N$ people standing having anger levels given in an array $A$, find out the leftmost position Chef can stand in the queue without attracting more than $K$ units of anger. If Chef joins the queue before Person $p$, He attracts total wrath $\left\lfloor \frac{A[p]}{1} \right\rfloor + \left\lfloor \frac{A[p+1]}{2} \right\rfloor + \left\lfloor \frac{A[p+2]}{3} \right\rfloor + \ldots + \left\lfloor \frac{A[N]}{N-p+1} \right\rfloor$ which should not be more than $K$. If he cannot stand before any person, he stands at the end of queue.

# QUICK EXPLANATION

• Instead of calculating the wrath level $w[p]$ for position $p$ directly, we try to find out how much anger of person at position $p$ affect wrath levels at positions.
• Person at position $p$ contribute $\left\lfloor A[p]/1 \right\rfloor$ to $w[p]$, $\left\lfloor A[p]/2 \right\rfloor$ to $w[p-1]$, $\left\lfloor A[p]/3 \right\rfloor$ to $w[p-2]$ and so on, till $\left\lfloor A[p]/(p) \right\rfloor$ to $w1$.
• We split this process into two parts. From position $p$ to $p-SQRT(A[p])$, wea update the effect on wrath levels manually. For remaining positions, we can see, that the wrath levels don't increase by $a[p]/SQRT(A[p])$, try all values $x$ from $1$ to $a[p]/SQRT(A[p])$ and find out range of elements whose wrath level is increased by $x$ and store these results in difference array.
• We can take prefix sum array of the above difference array and add to it the wrath levels calculated naively. Now we have wrath levels for each position. Just check if any valid position exist and print the required position.

# EXPLANATION

Let us define $w[p]$ as the wrath level Chef has to face if he joins the queue just before the person $p$ in the queue. We need to find the smallest $p$ such that $w[p] \leq K$ or determine if no such $p$ exist.

The main trouble here is the calculation of $w$ array, where $w[p]$ is given by $\left\lfloor \frac{A[p]}{1} \right\rfloor + \left\lfloor \frac{A[p+1]}{2} \right\rfloor + \left\lfloor \frac{A[p+2]}{3} \right\rfloor + \ldots + \left\lfloor \frac{A[N]}{N-p+1} \right\rfloor$

Let us reverse the process. Instead of considering the wrath at each position separately, we try to find out the contribution of $A[p]$ in wraths of various positions. It can be seen that the end result doesn't change.

So, Let us observe with a few values, how they contribute to adjacent positions.

10: 1 1 1 1 1 2 2 3 5 10
16: 1 1 1 1 1 1 1 1 2 2 2 3 4 5 8 16
46: 1 1 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 2 2 3 3 3 3 4 4 5 5 6 7 9 11 15 23 46

Reversing the rows now for understanding

10: 10 5 3 2 2 1 1 1 1 1
16: 16 8 5 4 3 2 2 2 1 1 1 1 1 1 1 1
46: 46 23 15 11 9 7 6 5 4 4 3 3 3 3 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

What we can notice from above is that initially, the values decrease very fast after reaching a limit, after which it reduces one by one till it becomes 1. It can also be seen by observing values of $x/v - x/(v+1)$, the change in consecutive terms, as $v$ grows large. Mathematical proof for this can also be derived in a similar manner.

It can be seen (and proved too) that after $\left\lfloor x/v \right\rfloor$ reaches $\left\lfloor \sqrt x \right\rfloor$, The value changes by at most one while moving to the right. Let us find out the range of elements (In terms of distance from position p where we are trying to find the contribution of A[p]).

To find the number of values with contribution $v$, we find the last position where contribution is $v$ and the last position where contribution is $v+1$ or higher. Last position having contribution at least $v$ is at distance $x/v$ from $p$. Similar explanation goes for $v+1$. Then, the number of occurrences of $v$ is just the difference between the above two.

Consider example. Let $x = 46$ and we want to find the range of positions where contribution is 2. Last position where contribution is at least 2 is $46/2 = 23$ while last position where contribution is at least $(2+1) = 3$ is $46/3 = 15$. So, $23-15 = 8$ positions have contribution 2, the positions at distance 16 to 23 from position of $x$ in array $A$.

But handling contribution value by value also leads to $O(N*max(A_i))$ solution, since it requires us to calculate the contribution of each value from $1$ to $A_i$.

So, We merge the naive solution with this one. Up to first $\sqrt x$ positions from position $p$, we can update contribution value by value in $O(\sqrt{A[i]})$ complexity. Now, The remaining positions all have contribution from current position is up to $\sqrt x$, so for every value from $1$ to $\sqrt x$, we find the ranges where contribution is exactly a given value. This also takes $O(\sqrt{A[i]})$ time per value.

So, our final solution looks like

For every position $p$, we try to calculate its contribution in wrath levels of all positions which are affected by $A[p]$. This we do in two steps. For positions within range $p-\sqrt{A[p]}$, we update each value manually using naive approach. For remaining positions, we find the range of positions which gets affected by the same value due to $A[p]$. Since there are only $\sqrt{A[p]}$ different values left now, This step also takes $O(N*\sqrt{A[i]})$ time.

For implementation, we can use difference arrays. For incrementing range $[l,r]$ by $x$, we increase diff[l] by x, reduce diff[r+1] by x. Now, When we take the summation array of this array as sum[i] = sum[i-1]+diff[i], we automatically have increased values in range $[l,r]$ by $x$ in sum array.

Hence, Overall solution has the time complexity $O(N*\sqrt{max(A_i)})$.

A note on Time Limit

I know the Time Limit for this problem was quite strict and many of you had to go for constant optimizations and reducing constant factors just to make that last TLE file to AC. The reason behind such tight TL is that to prevent non-intended solutions to pass. The solution which tries to calculate all wrath levels naively. To fit the time limit, you have to realize that division is a heavy operation as compared to other arithmetic operations and using it sparingly makes sense.

# Time Complexity

Time complexity is $O(N* \sqrt{max(A[i])})$ per test case.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Setter's solution

View Content

Tester's solution

View Content

Editorialist's solution

View Content

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

4.0k31104
accept rate: 22%

865214

1

https://codeforces.com/problemset/problem/616/E this problem is based on same idea

(13 Mar, 21:54) 5★

for all getting TLE with same logic...
Just preprocess that sqrt(value) loop for each value and it will pass...
HERE is my soln.. passes in 1.07 secs

(13 Mar, 22:17)

 2 Can this be done in O(N log(N))? We use the fact that circulant matrix multiplication with a vector is fast if we use FFT. I could do it if instead of the floor function, there was normal division(floating points). Any known fix for this? This constraints at first glance seemed to be asking to implement this O(N log(N)) solution answered 14 Mar, 09:44 3★udayan14 86●4 accept rate: 0% Yes, please can someone tell if we can do some trick for floor function for using FFT or karatsuba? (14 Mar, 11:41) adzo2614★ I did something similar to this. Made use of the fact that the floating point division can at max be larger than the floor division by N. But I couldn't get an AC on all test cases. TLE on 2 while all others passed in 0.23. (16 Mar, 15:51)
 1 Open Editorial Look at expected time complexity. Hit DownVote. Close Tab. The reason behind such tight TL is that to prevent non-intended solutions to pass. replace it with "The reason behind such tight TL is that to prevent intended solutions to pass." answered 13 Mar, 21:52 2.7k●1●6●18 accept rate: 10% 1 (13 Mar, 23:17)
 1 Optimizations at it's peak. This Long Challenge was a complete lesson of Time Complexities. :D answered 14 Mar, 00:02 3★nuttela 86●3 accept rate: 14% Time complexity ignores constant optimizations :p (14 Mar, 00:07) I learned that it is bad to use ceil... even wrote in the solution https://www.codechef.com/viewsolution/23438371 :D (14 Mar, 09:50) @thesmartguy dope code man!! Really liked your idea! (18 Mar, 08:24)
 0 When will the editorial of PTREE be out ? answered 13 Mar, 19:46 70●6 accept rate: 0%
 0 To fit the time limit, you have to realize that division is a heavy operation as compared to other arithmetic operations and using it sparingly makes sense. My solution uses only $2$ divisions and still gets TLE. Any tips/tricks/tutorials for optimizing this further :p. I am pretty sure I cannot reduce more divisions. answered 13 Mar, 20:18 15.5k●1●20●66 accept rate: 18% Mine runs in 1.58 seconds out of 4 seconds in java. (13 Mar, 20:28) 2 Cool. How do I optimize my code though? You can have all the bragging rights, just help this noob in learning some basic optimizations :p (13 Mar, 20:31) 1 XD......... (dots due to char limits) (13 Mar, 22:05) 1 you should create a blog on "vijju's optimization techniques" .... U convert int to long long int and switch to java from c++ for removing TLE XDD (13 Mar, 22:08) If i am not wrong you are doing the same thing as this solution https://www.codechef.com/viewsolution/23480958 I could not get it passed. It too has only 2 divisons, but the inner loops runs 2*root(N) time instead of root(N), same as yours I believe (13 Mar, 22:12) @vijju Just preprocess that sqrt(value) loop for each value and it will pass... HERE is my soln.. passes in 1.07 secs (13 Mar, 22:14) same optimization advice to both of you (13 Mar, 22:15) 1 Thanks @l_returns that helps. (13 Mar, 22:58) anytime @viiju123 :D (13 Mar, 23:16) @vijju123 I got passed in 0.66 I feel it is because of the way you are using difference arrays i used one division operation though You can see my solution if you want-> https://www.codechef.com/viewsolution/23337676 (14 Mar, 01:04) I am pretty much sure its because you used only 1 division @swapnil159 (14 Mar, 01:23) showing 5 of 11 show all
 0 Kudos to problem setter and also to editorialist for such a nice editorial. Although the problem uses basic concept but I didn't get it during contest time :P Thanks again! answered 13 Mar, 21:07 2★pk301 627●10 accept rate: 16%
 0 "The reason behind such tight TL is that to prevent non-intended solutions to pass. The solution which tries to calculate all wrath levels naively." I kind of bypassed that by calculating the wrath levels naively, but only those that are actually required. And it passed. So I think the test cases didn't have anything like 5 1 100000 1 2 ... 10^5 1 100000 1 2 ... 10^5 1 100000 1 2 ... 10^5 1 100000 1 2 ... 10^5 1 100000 1 2 ... 10^5 answered 13 Mar, 21:30 494●3●8 accept rate: 7% 2 Yes, test cases did not have maximal constraint. This TL limit felt really bad to me. (13 Mar, 22:59) Agreed. Either the TL should have been more relaxed, or they should have included testcases for maximum constraints. (14 Mar, 10:55) 1 Codechef is cheating xD I just created a sample input with maximum constaints (with random arrays). Tester's solution takes 2.056 secs, but mine is 0.4 secs (Code::blocks execution time). A little partial score would be nice. Here is my easy solution on C++: https://www.codechef.com/viewsolution/23560514 (14 Mar, 14:41) tieros4★
 0 It would be helpful if you can tell the time complexity of my solution. https://www.codechef.com/viewsolution/23384243 answered 13 Mar, 22:08 3★manan2go 1 accept rate: 0%
 0 This Problem taught me that division is a costly opertaion answered 14 Mar, 00:38 4★sj444 11●1 accept rate: 0%
 0 have a look at my solution: it taking 1.5*10^8 loops in the worst case, with three divisions https://pastebin.com/qZkGRXrk answered 14 Mar, 13:04 78●6 accept rate: 7%
 0 Last two TC for my solution is something...... My solution answered 16 Mar, 15:32 11●1 accept rate: 0%
 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:

×2,657
×1,220
×724
×83
×75
×20