help in a codeforce question.

general
3

@vijju123 , @vivek_1998299 can you please look into it!

4

Which part of the editorial u couldnt understand?

5

truely speaking i didn’t understand both the implementation part and how the expression comes? (that min(…, 0))

6

“If a+x<c u’ll find finalVal=initVal,else the same as editorial.” If you don’t mind can you please explain how that expression(2*max(0, x-(ck-ak)) comes? Actually I am not clear how they are sure about max because the value (current_val - initial_val) may be positive or negative.

7

Ohk so we have initval=c-b,finalVal=a+x-b+mod(a+x-c),if(a+x)<c,mod(a+x-c)=c-x-a
So finalVal=a+x-b+c-x-a=c-b

So increment =0 -------(1)

Now if a+x>c
Mod(a+x-c)=a+x-c

So finalVal=a+x-b+a+x-c=2a+2x-b-c

So increment=finalVal-initVal=(2a+2x-b-c)-(c-b)=2a+2x-2c =2*(x-(c-a))-----(2)

From (1) and (2)

=max(0,2*(x-(c-a)))

1 Like
8

how can we take the max? as it is case dependent i.e. when we have incremented ‘a’ then we have no control whether 1st condition holds or the 2nd one. so, why max?

9

Lets say first case comes,a+x<c
So x-c+a=-ve
So max(0,2*(-ve))=max(0,-ve)=0

If second case comes a+x>c
X+a-c=+ve

So max(0,2*(+ve))=2*+ve

1 Like
10

sorry for the late reply! I am busy with my internals :frowning:

Last thing i want to ask : can you please explain the implementation approach a little bit more. More specifically how to answer : “2·max(0, x - (ci - ai)) - 2·min(bi - ai, x)”

11

For this u can find local minima ,similar to how we found local maxima(using map),lets say u got i.So diff[i] and diff[i-1] would be those differences(ci-ai,bi-ai)…

1 Like
12

if possible can you please look into my code : 935F, C++ (gcc) - rextester

It is giving WA on test 22.

13

U got the mistake?

14

sadly no :frowning:

15

have you looked into the code? If yes can you please suggest me where i can shorten the code? Because i’ve seen three or four solutions and all of them are pretty short (but sadly didn’t understand the idea of implementation)!

16

Actually i have my exams tomorrow,i will surely see when i am free

17

thanks mate :slight_smile: and good luck for the exams!

18

I too have seen many code.Some codes i saw had a worst case complexity of O(N) per query yet still they passed,and some didnt use the diff array and instead worked on original array (bt that was more difficult to understand for me)

19

@vivek_1998299 does your exams over?

20

2 days to go :slight_smile: ,on saturday

21

Did u consider the edge cases like when r-l<=2,also changing at l and r

22

This is my ac code :

see if u understand it.

If u dont,tell me.I’ll explain when i get time