Ex - Multiply or Divide by 2 Editorial by en_translator
Regarding the operations as those against binary notations
Let us convert each non-negative integer to its binary notation and treat it as a string. (Here, we regard that \(0\) has a binary notation of an empty string.)
Then, the two operations is rephrased as follows:
- Remove the last digit of a non-negative string in \(A\)
- Remove the last digit of a non-negative string ending with \(0\) in \(B\)
For the latter operation, instead of doubling an element of \(A\), we halve the (ultimately) corresponding element of \(B\).
Using a Trie
There is a data structure called Trie, which enables us to treat a set of strings as a rooted tree. This problem can be solved with this data structure.
Construct a Trie consisting of strings of \(A\) and \(B\). Then, each operation corresponds to moving a string to its parents.
On this Trie, from the leaves to the root, if a vertex has elements of both \(A\) and \(B\), match them greedily and eliminate them, and move the remainder towards the root. Here, a string of \(B\) not ending with \(0\) cannot be moved towards the root, so abort by printing -1
. If all elements could be matched, print the number of moves.
The time complexity \(\mathrm O(N\log A_{max})\) required for the construction of Trie and DFS is also that of this solution.
Alternatively, you may use a map and process the values in the descending order to achieve a equivalent simulation. (This case, the complexity is \(\mathrm O(N\log N\log A_{max})\).)
posted:
last update: