CALC - Editorial

editorial
, , , ,
21

@dishant_18 actually when i was commenting codechef showed some error.I guess due to this reason i commented it thrice by mistake. I have removed it now Thanks:).

22

It was showing error even when i tried to answer a question.

23

https://www.codechef.com/viewsolution/14444469
Ternary search is not much different from binary search only difference is that after reaching mid you have to check whether the right is smaller of greater than present value.
Also to apply ts you need to know which type of parabola it is.
Hope solution is clear.

24

The division in your function is “integral” which is not the case of mathematical functions.

25

Yup I know that but still should’nt the maximum answer lie around n/2 ± 1?

26

Button A has cost 1. Button B has cost B.x is number of times button B is pressed. So points left for button A = N-x*B. So number of times A is pressed = (N-x*B)/1=N-x*b

27

TYSM vijju123! got it now :slight_smile:

28

The issue is corrected now. Thanks for pointing out ^^

1 Like
29

Your solution will become twice more appealing if you give a short summary of your thinking/what you did here. :smiley:

30

@soheb17 that was a good observation. @vijju123 Actually In this question you will always get a maximum solution when you do half times 1 and remaining half do the other. You can notice this by custom inputs. What i mean to say is that in this question quadratic equation having roots first (no on the first) and second(no on the second) are equal.
In other words equal values has given extrema in this quadratic equation and so you know that how much to press on first and on second and you get the answer in O(1).

31

Can someone please explain, why this is incorrect?
I am not able to understand what is wrong with the approach as given by @harsh24

32

Problem is that in the equation he ignored the remainder of (N - x) / B. It is optimal to use the remainder in increasing number on first digit. If B * q + r = (N - x) then maximum answer should be q * (x + (N - x) - B * q) = q * (N - B * q) but this becomes equivalent to fixing the number of times second button was pressed.

1 Like
33

Yes, got it!
Thanks.

34

Hi. Can anyone tell why my code is showing WA?
I have run some random 30-40 test cases and all are coming out to be correct (i.e same output as of the editorialist’s solution). Are there any exceptions which I am missing out?

Following is my logic:
if b>n/2
output= n-b
if b>=1 && b<=n/2
output=(n * n)/4b (or result=x(n-x * b) when x=n/(2*b))
else
output=0