PROBLEM LINK:Author: Arkapravo Ghosh DIFFICULTY:EASYMEDIUM PREREQUISITES:Graph, BFS PROBLEM:Given a number A, you have to reach another number B using the minimum number of operations, given you can only perform the following operations: QUICK EXPLANATION:We can simply consider this as a graph problem. We can consider A as a node in a graph and start a BFS from that node till we reach B. Here each node will have three outgoing edges. EXPLANATION:We can consider this problem as a graph problem. Here each number will represent a node in the graph. Each node will have three outgoing edges. We can first start BFS from node A till we reach node B. The three nodes outgoing nodes from a node numbered N will be N1, N+3 and N*2. But the graph now has infinite number of nodes. However we can limit the range of the node numbering with a simple observation that we don’t need to go below 0 and above B + (BA)/3. In the worst case we can reach B from A in (BA)/3 steps, since we can increment by 3 in each step. Again from B + (BA)/3, we can reach B in (BA)/3 steps decrementing by 1 each time, since it is the only way of decrementing a number. So, going upto B + (BA)/3 from A and then decrementing by 1 for (BA)/3 times is as good as incrementing A to B in (BA)/3 steps. So we can limit the range of nodes from 0 to B+(BA)/3. If B is less than A, then decrementing by 1 in each step is the only way to reach B from A. So it will take (AB) steps. The time complexity of this algorithm is proportional to the number of vertices and edges in the graph. In the worst case the no of vertices and edges is (B + (BA)/3) * 3 = O(B), thus worst case time for BFS will be O(B) i.e. linear time. AUTHOR'S AND EDITORIALIST'S SOLUTIONS:Author's and editorialist’s solution can be found here. asked 07 Aug '18, 00:23

I didn't use this limit since the space of values was small enough already, but the path from $A$ to a larger $B$ doesn't need to cross approximately $8B/7$, since stepping from below $B$ to above by doubling to an equal number of steps away $s$, gives $2(B3s) = (B+s) => s = B/7$. I would add 3 to that limit: 8B/7 + 3 to allow for detailed adjustment. Thus the best path from say 4 to 91 shouldn't need to go above 107. On further reflection, if the better option in the above analysis is to come down to $B$ from above, it makes more sense to do the subtractions before the doubling, since only half as many will be required. This simplifies all the above analysis to expecting that the best path from $A$ to a larger $B$ can be achieved without going above $B+2$. On the lower end, there's clearly no point in going below $A/2$. answered 07 Aug '18, 18:47
