CALC - Editorial

PROBLEM LINK:

Contest
Practice

Author: Hasan Jaddouh
Primary Tester: Misha Chorniy
Editorialist: Hussain Kara Fallah

DIFFICULTY:

Easy

PREREQUISITES:

Simple Math

PROBLEM:

We have a calculator with 2 screens and 2 buttons. Each screen shows number zero initially. Pressing the first button increments the number on the first screen by 1, and each press of this button consumes 1 unit of energy. Pressing the second button increases the number on the second screen by the number appearing on the first screen. Each click of this button consumes B units of energy. Given B,N what’s the maximum possible number that may show on the second screen without consuming more than N units of energy?

EXPLANATION:

First of all, it’s obvious that it’s not optimal to press the first button after pressing the second. We must press the first button for number of times, after that we should spend the remaining energy on pressing the second button.

Let’s define a function f(x) where f(x) represents the maximum number displayed on the second screen if we pressed the second button exactly x times.

f(x) = (N-x*B) * x

f(x) = -x^2 * B + Nx

We can notice that the graph of this function is a parabola. Our best answer would be
f(k) = h

where the point (k,h) is the vertex of the parabola. It’s well known that

k = \frac{-b}{2a}

for any parabola following the form f(x) = ax^2 + bx + c

So here : k = \frac{N}{2*B}

We can also deduce that from the derivative and find the local extrema of the function.

Since we can press the second button only integer number of presses so we must try,
k1 = \lfloor \frac{N}{2*B}\rfloor AND k2 = \lceil \frac{N}{2*B}\rceil and pick the better choice.

Ternary search is another possible solution for this problem.

AUTHOR’S AND TESTER’S SOLUTIONS:

AUTHOR’s solution: Will be found here
TESTER’s solution: Will be found here
EDITORIALIST’s solution: Will be found here

9 Likes

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

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

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

Yes, this is what I did too!

Here’s my code.

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

One-line solution.

1 Like

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

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

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: !

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

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

the simplest one thank me later.

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