PROBLEM LINK:Practice Setter: Volodymyr Mykytsei DIFFICULTY: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]}{Np+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
EXPLANATIONLet 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]}{Np+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 Reversing the rows now for understanding 10: 10 5 3 2 2 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, $2315 = 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[i1]+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 nonintended 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 ComplexityTime complexity is $O(N* \sqrt{max(A[i])})$ per test case. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Tester's solution Editorialist's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 13 Mar, 18:06

answered 13 Mar, 21:52

Optimizations at it's peak. answered 14 Mar, 00:02
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)

My solution uses only $2$ divisions and still gets TLE. Link  https://www.codechef.com/viewsolution/23487508 Any tips/tricks/tutorials for optimizing this further :p. I am pretty sure I cannot reduce more divisions. answered 13 Mar, 20: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" ....
(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...
(13 Mar, 22:14)
same optimization advice to both of you
(13 Mar, 22:15)
anytime @viiju123 :D
(13 Mar, 23:16)
@vijju123 I got passed in 0.66
(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

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

"The reason behind such tight TL is that to prevent nonintended 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 answered 13 Mar, 21:30
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)

It would be helpful if you can tell the time complexity of my solution. answered 13 Mar, 22:08

This Problem taught me that division is a costly opertaion answered 14 Mar, 00:38

have a look at my solution: it taking 1.5*10^8 loops in the worst case, with three divisions answered 14 Mar, 13:04

Last two TC for my solution is something...... My solution answered 16 Mar, 15:32

https://codeforces.com/problemset/problem/616/E this problem is based on same idea
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