divad's blog

By divad, 4 days ago, In English

Introduction

This is a tutorial/explanation on how DFS and BFS can be used for the following problem: 1141A - Game 23

Statement

We are given two integers $$$n$$$ and $$$m$$$ and are asked to determine in how many steps can we tranform $$$n$$$ to $$$m$$$ with the following steps:

  • multiply $$$n$$$ by $$$2$$$
  • multiply $$$n$$$ by $$$3$$$

If $$$n$$$ can not be made equal to $$$m$$$ using the transformations mentioned above then the answer show be $$$-1$$$

Solution

Let's try and visualize the following example: $$$120, 51840$$$

The highlighted path is the one from $$$n$$$ to $$$m$$$, so we can see that it takes $$$7$$$ transformations

Observations:

  • every number generated is the form of $$$n \cdot 2^{k_1} \cdot 3^{k_2}$$$
  • distance from $$$n$$$ to $$$n \cdot 2^{k_1} \cdot 3^{k_2}$$$ is $$$k_1 + k_2$$$
  • the tree follows this rule:

  • there is one particular case where $$$n = m$$$, then the answer is $$$0$$$

Now that we know what rule it follows we can generate the tree itself. But since we want to know if a path exists from $$$n$$$ to $$$m$$$ we can use any graph treversal algorithm, in this blog im going to show you how it can be done using DFS and BFS.

So that we dont generate a number multiple times we will use a frequency array. The problem is that we haven’t got enough memory to store for each number up to $$$10^{18}$$$. As mentioned before all numbers generated are in the form of $$$n \cdot 2^{k_1} \cdot 3^{k_2}$$$ so we can use a frequency matrix in which $$$viz[i][j]$$$ is equal to $$$1$$$ if $$$n \cdot 2^{i} \cdot 3^{j}$$$ has already been generated, or $$$0$$$ it that numbers has not been generated yet

Implementation

DFS implementation
BFS implementation
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it
  • multiply n by 2
  • multiply m by 3

That m should be n according to the problem statement. Regardless of that, your approach is interesting.

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for pointing that out. I have now changed it