Can someone explain how is that f(x) derived?
Instead of checking how many times the second button was pressed I was checking what was the maximum answer we could get if I press the first button x times which gave me the quadratic equation for the score as ((N-x)/B )*x ,now this gives maxima at n/2 so I was checking numbers around n/2 which was giving me WA ,can anybody please point out what is wrong? Also I was keeping in mind the fact that (N-x)>B for x=n/2 ,if it was then my maximum would be around n/2 or else my maximum would be at x=N-B.
Someone please point out my mistake
1 Like
#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;
}Hey, can anyone explain why x*B used in equation: f(x)=(N−x∗B)∗x
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.
@deadwing7 . The links for contest and practice are swapped.
#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
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
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
@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:).
It was showing error even when i tried to answer a question.
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.
The division in your function is “integral” which is not the case of mathematical functions.
Yup I know that but still should’nt the maximum answer lie around n/2 ± 1?
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
TYSM vijju123! got it now 
The issue is corrected now. Thanks for pointing out ^^
1 Like
Your solution will become twice more appealing if you give a short summary of your thinking/what you did here. 
@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).