TC ValidPlates

From Algorithmist
Jump to navigation Jump to search


You are given a list of "forbidden pairs" of digits. Find the seqno</syntaxhighlight>th positive integer whose decimal representation has no forbidden pairs.

An outright difficult problem, it combines dynamic programming with some non-straightforward mathematical reasoning. There is an easy recurrence to figure out the answer when it has a small (say, at most 100000) digits. But sometimes the correct answer may have more than a billion digits, so you need to apply careful reasoning and a clever trick.

From TopCoder Single Round Match 341.

Only one coder, xhl_kogitsune, got this one right!