分散型の検索

トップコーダオープンのプログラミング試合に出た問題を考えました。複雑性はO(N^２M)でした。

友人が数字のパスワードを推量みました。すべての推量が一桁に違いました。目的は推量の行列を知って可能なパスワードの数を出力する事です。
The algorithm is basically a doubly-nested for loop. The outer loop considers each digit in the first guess as a candidate to be different in the actual password. The second loop iterates over all other guesses. This inner loop itself is actually O(NM), as it checks all digits in the guess against those in the first one. Basically, for each ith digit in the first guess, the jth later guess (from 1 to M-1) can either change or not change. If it changes then this digit cannot be in the actual password. A separate data structure, which updates for each "for i" iteration, tracks which digits must be excluded. If the ith digit in the jth guess is not changed, then the ith digit of this guess must be in the actual password. In addition, exactly one digit in the jth guess must differ from its corresponding digit in the first guess (non-ith digits). If any contradictions in the above statements occur (e.g. jth guess needs to fix ith digit, but it has been fixed to something else by an earlier guess), then the number of valid passwords resulting from the ith digit of the first guess changing is zero.