CALC - Editorial

editorial
, , , ,
3

Very nice!!
What I did was used ternary search because the results after pressing some 1 and some 2 first increase and then decrease as we go on increasing number of times we pressed 1.
Though this was simple to think better one is this one (admin).

4

Nice Solution, I used loops after figuring out the first equation. got TLE. Never actually thought of transforming the equation.

5

Yes, this is what I did too!

Here’s my code.

6

can anyone post the ternary search solution to this problem.
Thanks in advance :slight_smile:

7

One-line solution.

1 Like
8

Same approach :slight_smile: that ceil and floor caused me a couple of WAs but was able to figure that out

9

Here is my solution

for i in range(int(input())):
	N,B= map(int, input().split())
	print(round(N/(2*B))*(N-(B*round(N/(2*B)))))
10

Can someone prove the optimality clause made by the poster of this editorial ? I mean seriously, I did get the rationale behind the question, and it became pretty straightforward once I assumed that the solution will be optimal this way. A mathematical proof would be great! Thanks in advance :slight_smile: !

11

Can someone explain how is that f(x) derived?

12

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
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.