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

×

CHONQ - EDITORIAL

3
2

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

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

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]}{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".

asked 13 Mar, 18:06

taran_1407's gravatar image

6★taran_1407
4.0k31104
accept rate: 22%

edited 17 Mar, 00:01

akashbhalotia's gravatar image

5★akashbhalotia
865214

1

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

(13 Mar, 21:54) vjvjain05★

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

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

link

answered 14 Mar, 09:44

udayan14's gravatar image

3★udayan14
864
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) ankit_btech4★
  1. Open Editorial
  2. Look at expected time complexity.
  3. Hit DownVote.
  4. 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."

link

answered 13 Mar, 21:52

aryanc403's gravatar image

5★aryanc403
2.7k1618
accept rate: 10%

edited 14 Mar, 06:20

1
(13 Mar, 23:17) l_returns5★

Optimizations at it's peak.
This Long Challenge was a complete lesson of Time Complexities. :D

link

answered 14 Mar, 00:02

nuttela's gravatar image

3★nuttela
863
accept rate: 14%

Time complexity ignores constant optimizations :p

(14 Mar, 00:07) vijju123 ♦♦5★

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

@thesmartguy dope code man!! Really liked your idea!

(18 Mar, 08:24) rahul_bhati3★

When will the editorial of PTREE be out ?

link

answered 13 Mar, 19:46

aparichit_vyav's gravatar image

4★aparichit_vyav
706
accept rate: 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.

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.

link

answered 13 Mar, 20:18

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

Mine runs in 1.58 seconds out of 4 seconds in java.

(13 Mar, 20:28) taran_14076★
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) vijju123 ♦♦5★
1

XD......... (dots due to char limits)

(13 Mar, 22:05) l_returns5★
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) l_returns5★

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

@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) l_returns5★

same optimization advice to both of you

(13 Mar, 22:15) l_returns5★
1

Thanks @l_returns that helps.

(13 Mar, 22:58) vijju123 ♦♦5★

anytime @viiju123 :D

(13 Mar, 23:16) l_returns5★

@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) swapnil1595★

I am pretty much sure its because you used only 1 division @swapnil159

(14 Mar, 01:23) vijju123 ♦♦5★
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!

link

answered 13 Mar, 21:07

pk301's gravatar image

2★pk301
62710
accept rate: 16%

"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

link

answered 13 Mar, 21:30

aneesh2312's gravatar image

6★aneesh2312
49438
accept rate: 7%

2

Yes, test cases did not have maximal constraint. This TL limit felt really bad to me.

(13 Mar, 22:59) vijju123 ♦♦5★

Agreed. Either the TL should have been more relaxed, or they should have included testcases for maximum constraints.

(14 Mar, 10:55) aneesh23126★
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★

It would be helpful if you can tell the time complexity of my solution.

https://www.codechef.com/viewsolution/23384243

link

answered 13 Mar, 22:08

manan2go's gravatar image

3★manan2go
1
accept rate: 0%

This Problem taught me that division is a costly opertaion

link

answered 14 Mar, 00:38

sj444's gravatar image

4★sj444
111
accept rate: 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

link

answered 14 Mar, 13:04

thesmartguy's gravatar image

4★thesmartguy
786
accept rate: 7%

Last two TC for my solution is something...... My solution

link

answered 16 Mar, 15:32

starboy_jb's gravatar image

4★starboy_jb
111
accept rate: 0%

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:

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

question asked: 13 Mar, 18:06

question was seen: 3,890 times

last updated: 18 Mar, 08:24