PLYNUM – Editorial

general
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Arkapravo Ghosh
Tester: Arkapravo Ghosh
Editorialist: Arkapravo Ghosh

DIFFICULTY:

EASY-MEDIUM

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:-
1) Decrement the current number by 1
2) Increment the current number by 3
3) Multiply the current number by 2

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 N-1, 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 + (B-A)/3. In the worst case we can reach B from A in (B-A)/3 steps, since we can increment by 3 in each step. Again from B + (B-A)/3, we can reach B in (B-A)/3 steps decrementing by 1 each time, since it is the only way of decrementing a number. So, going upto B + (B-A)/3 from A and then decrementing by 1 for (B-A)/3 times is as good as incrementing A to B in (B-A)/3 steps. So we can limit the range of nodes from 0 to B+(B-A)/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 (A-B) 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 + (B-A)/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.

2 Likes
2

How is the max no of steps required (B-A)/3 ? Please explain :slight_smile: I am not able to get it from the above explanation.

3

Suppose you have two numbers 0 and 100. So according to the given problem, you can increment by 3 every time instead of using the multiplication operation(which will make the no of steps less, as you increment fast). If you increment by 3 every time, then you will take (100 - 0)/3 i.e. ~33 steps. So this is the worst case, as you can simply multiply by 2 in the intermediate numbers and reduce the no. of steps. So, the maximum number of steps will be O((B-A)/3). I hope this clears your doubt. If not, feel free to ask again. :slight_smile:

2 Likes
4

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(B-3s) = (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.

1 Like