As it is a binary string, the hash value of a string will be the sum of some distinct power of base bb. 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 < ii, and then we add bib^ito all the generated data to get some new hash values that are possible. The transition will be, dp[i][h]dp[i][h]=dp[i][h]=dp[i][h] or dp[i1][hbi]dp[i-1][h-b^i]. Here means hash value hhcan be generated using some powers of bbupto ii. After processing this for iiupto nn, if we didn’t get hash value hh then it is not possible to generate hh.

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 bbfor some index ii. So if we start from the highest value of iiand come downwards we will encounter the lexicographically smaller one first. So, we will start from i=ni=nand come downwards keeping track of the highest index where we first encountered the hash value hh. Now using these values we can generate the string.

Complexity: O(nm)O(n*m)

Judge solution(C++):


74% Solution Ratio
Wojciech.324122Earliest, Feb '22
flukehn.841988Fastest, 0.0s
ArcturusLightest, 393 kB
Xi.498579Shortest, 779B
Toph uses cookies. By continuing you agree to our Cookie Policy.