Two Buttons from codeforces

help
, ,
1

Problem:-

Editorial:-

scroll down a bit you’ll find the editorial :sweat_smile:.

And thanks for your time in advance :smile: :upside_down_face:.

Backstory:-

Summary

I’m not sure if that’s healthy for codechef community to seek help regarding a codeforces question here, but I’m kinda desperate so bare me :raised_hands:t2:. Only, until recently have I got to know that all the work I’ve put so far is kind waste, so starting new again. I was so far into competitive coding just using the intuitions that I get after reading a question however, recently I found out that it’s not going to take me further without backing up with math…so kinda into approaching question in a math approach. In the above question, after reading editorial, I was convinced with “dfs” approach but not so with the other.

Doubts:-

1st Doubt

The above question put into equations would be something like,
2^{x} . ( n - y*k ) - y*l = m

where,
n → given number on display
m → a number that we need to attain
y → in this problem, always a “-1”
x, k, l → any non negative integer

and the answer would something be like,
x + k + l
while trying to minimize this total gives us the required answer but this is nowhere close to the actual approach of the editorial help me proceed to the next. From constraints,
0 <= x <= 14
no clue after this. If this is all trash, please help me on how to approach a problem mathematically.

2nd Doubt

From the second approach in the editorial and many other submissions, I couldn’t logically or mathematically deduce that inverting the condition like performing operations on variable “m” with “add 1” and “divide by 2” could be more yielding to minimize button clicks than performing operations on variable “n” with “subtract 1” and “multiply by 2”. Need a mathematical proof that either one deduced approach is better/worse than the other.

3rd Doubt

I know I ask a lot of questions, kinds first time in discuss_codechef. How do we use Latex for math equations and expressions, seems not working for me…I don’t want to give a eye sore for people trying to help me :innocent:.

Thank you, for you time…seriously…it helps me grow.

2

Latex is just

$Math here$

It does not support
$$Math here$$

2^{x} . ( n - y*k ) - y*l = m
I don’t think this is the correct way to put it in a mathematical equation. This assumes that all subtraction operations are done at the start and end if I’m not mistaken.

The DFS approach is equivalent in both .

However inverting the condition gives us a nice greedy method to choose the operations.

When n is smaller, There is absolutely no reason to divide by 2.

When n is larger, It is optimal to make it even and then divide by 2. That is because, An increase of 2 in this step, will become an increase of 1 in the next step. So we should delay the operation.

for example
n=13 and m=8
13 ->14->7->8
13->14->15->16->8
When we didn’t divide by 2 immediately, it took us 2 operations to get the effect of +1, So it’s optimal to instantly divide. This gives a time complexity of O(log\ n), as n will get halved at least once every 2 steps.

1 Like
3

@everule1
Firstly, thanks for your time.
"2^{x}.(n−y.k)−y.l=m
I don’t think this is the correct way to put it in a mathematical equation. This assumes that all subtraction operations are done at the start and end if I’m not mistaken."
True, but we are always welcome to make k or l to be 0's right, like 0 \leq l, k and k would be, I guess somewhere at \log_{2}{l}, a integer.

"When n is smaller, There is absolutely no reason to divide by 2.

When n is larger, It is optimal to make it even and then divide by 2. That is because, An increase of 2 in this step, will become an increase of 1 in the next step. So we should delay the operation."

I suppose you were talking about m, and putting it into generic way,
for non negative integer x,
2.x-1 \geq 2.(x-1)
2.x -1 \geq 2.x - 2
So to sum it up, using the RHS, would closer the gap between n and m faster than using LHS. I feel like, this is the proper way of approaching this question via math rather just random intuition. Thanks for your help, got a new way of approaching things now.