PROBLEM LINK:
Author and Editorialist : Anish Kumar
DIFFICULTY:
Easy-Medium
PREREQUISITES:
BFS
EXPLANATION:
The simplest solution is simply doing a breadth-first search. Construct a graph with numbers as vertices and edges leading from one number to another if an operation can be made to change one number to the other. We may note that it is never reasonable to make the number larger than 2m, so under provided limitations the graph will contain at most 2·10^4 vertices and 4·10^4 edges, and the BFS should work real fast.
There is, however, an even faster solution. The problem can be reversed as follows: we should get the number n starting from m using the operations “add 1 to the number” and “divide the number by 2 if it is even”.
Suppose that at some point we perform two operations of type 1 and then one operation of type 2; but in this case one operation of type 2 and one operation of type 1 would lead to the same result, and the sequence would contain less operations then before. That reasoning implies that in an optimal answer more than one consecutive operation of type 1 is possible only if no operations of type 2 follow, that is, the only situation where it makes sense is when n is smaller than m and we just need to make it large enough. Under this constraint, there is the only correct sequence of moves: if n is smaller than m, we just add 1 until they become equal; else we divide n by 2 if it is even, or add 1 and then divide by 2 if it is odd. The length of this sequence can be found in O(logN).