Reverse Hash

As it is a binary string, the hash value of a string will be the sum of some distinct power of base $b$. So let’s try to generate all the hash values that can be generated. It can be done using dynamic programming, we keep track of all the hash values that we already generated for power < $i$, and then we add $b^i$to all the generated data to get some new hash values that are possible. The transition will be, $dp[i][h]$$=dp[i][h]$ or $dp[i-1][h-b^i]$. Here means hash value $h$can be generated using some powers of $b$upto $i$. After processing this for $i$upto $n$, if we didn’t get hash value $h$ then it is not possible to generate $h$.

Otherwise, we need to generate the lexicographically smallest string. How do we do that?

Notice if a lexicographically smaller string will have a higher power of $b$for some index $i$. So if we start from the highest value of $i$and come downwards we will encounter the lexicographically smaller one first. So, we will start from $i=n$and come downwards keeping track of the highest index where we first encountered the hash value $h$. Now using these values we can generate the string.

Complexity: $O(n*m)$

Judge solution(C++): https://paste.ofcode.org/zQwCrDESwTFB4SpNYnGz2E