CALC - Editorial

editorial
, , , ,
13

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include 

using namespace std;
#define ll long long
 
ll val(ll s, ll n, ll b, ll x)
{
	return ((s+b*x)*((n-b*x)/b));
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while(t--)
	{
		ll n, b;
		cin >> n >> b;
		ll sc1 = n%b;
		n -= sc1;
		if((n/b)%2)
			cout << max(val(sc1,n,b,n/b/2), val(sc1,n,b,n/b/2+1)) << endl;
		else
			cout << val(sc1,n,b,n/b/2) << endl;
	}
	return 0;
}
14

Hey, can anyone explain why x*B used in equation: f(x)=(N−x∗B)∗x

15

I just did this and it worked…

mod=N%B;
 div=N/B;
 if(mod>0)
 {
     div++;
     mod=B-mod;
     N=B*div;
 }
 k=div/2;
 e=(long)Math.ceil(div/2)*B;
 if(N<=B)
 System.out.println(0);
 else
 System.out.println((long)((N-e-mod)*k));

I never thought that it would require parabola or derivatives, I just took some examples, found out what common technique worked for them, and the solution worked.

16

@deadwing7 . The links for contest and practice are swapped.

17

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
int t;
cin>>t;
ll n,b;
while(t–)
{
cin>>n>>b;
ll val = n/b;
if(val%2==1)
val+=1;
ll mid = val/2;
ll answer = mid (n - (midb));
cout<<answer<<endl;
}
}

–possibly the simplest solutions you can get

1 Like
18

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

the simplest one thank me later.

19

Too many of the solutions above have strange tests and conditionals. These are not really necessary, and the required effect can be handled in the division sum.

If x is the number of times button 2 is pressed, then the final score S is given by

S = x(N-Bx)

Using simple manipulation to complete-the-square gives

S = x(N-Bx) = Nx-Bx^2 = B \left(\frac N {2B}\right)^2 - B \left(\frac N {2B} - x\right) ^2

To maximize S, we make \left| \frac N {2B} -x \right| as small as possible. The number of button presses x has to be an integer, so we seek the nearest integer to \frac N {2B}. Using the integer arithmetic of C, we set

x = \left\lfloor\frac {N+B} {2B}\right\rfloor

.

Hence a solution:

#include <bits/stdc++.h>
using namespace std;
int main( int argc, char ** argv )
{
    uint32_t T,N,B;
    cin >> T;
    while (T--) {
         cin >> N >> B;
         uint64_t x = (N+B)/(B+B);
         cout << x*(N-x*B) << endl;
    }
    return 0;
}
1 Like
20

Hi! It seems you commented thrice the same thing by mistake! It would be good if you delete the unwanted stuff. It will help organize comments better!

2 Likes
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