CALC - Editorial

editorial
, , , , ,
1

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
2

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

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

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
5

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

6

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

7

Yes, this is what I did too!

Here’s my code.

8

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

9

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

10

One-line solution.

11

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.

12

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

13

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

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

15

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

16

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

17

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

18

#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;
}
19

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

20

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