TC ValidPlates
From Algorithmist
[edit] Summary
You are given a list of "forbidden pairs" of digits. Find the seqnoth 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!
