Number card trick

Maryam and Peiling practice a number trick. It works like this.

Maryam picks $N$ integers between $2$ and $M$, inclusive. The numbers are independent and every allowed value is equally likely. She writes them on $N$ cards, one number per card, so the same number can appear several times. She then repeats the following $K$ times. She takes a random subset of the cards, putting each card in with probability $0.5$ independently of the others, and writes down the product of the numbers on those cards. The empty subset gives the product $1$.

Maryam shows the $K$ products to Peiling. Knowing only $N$, $M$, $K$ and the products, Peiling has to name the numbers on the cards.

The products often fail to pin the numbers down. When every product is $1$, they say nothing at all about the cards. This problem therefore asks for the candidate with the largest posterior probability.

Call a sequence $B$ with $2 \le B_1 \le B_2 \le \dots \le B_N \le M$ a candidate. Let $P_1, P_2, \dots, P_K$ be the observed products, and let $c_B(p)$ be the number of subsets of $\{1, 2, \dots, N\}$ whose product is $p$. The empty subset has product $1$. Let $o(B)$ be the number of distinct orderings of $B$: if the value $v$ appears $m_v$ times in $B$, then $o(B) = N! / \prod_v m_v!$. Define the weight of a candidate as

$W(B) = o(B) \times \prod_{j=1}^{K} c_B(P_j)$

$W(B)$ is proportional to the probability that Maryam's numbers form the multiset $B$, given the observed products.

For each set, print the candidate with the largest $W(B)$. If several candidates tie for the largest weight, print the lexicographically smallest one.

The first line contains the number of test cases $T$, which is always $1$. The second line contains four space separated integers $R$, $N$, $M$ and $K$. Each of the next $R$ lines contains $K$ space separated products and describes one independent set produced by the procedure above.

Print "Case #1:" on the first line. Then print $R$ lines, one answer per set, in order. Each answer is $N$ digits in non-decreasing order with no spaces between them. Because $M < 10$, every number is a single digit.

• $T = 1$
• $1 \le R \le 100$
• $1 \le N \le 6$
• $2 \le M \le 9$
• $1 \le K \le 10$
• Every input was produced by the procedure in the statement, so each $P_j$ is the product of some subset of that set's hidden numbers.

The first set of the first example has $N = 3$, $M = 4$ and lists the product $36$. The only way to write $36$ as a product of three numbers between $2$ and $4$ is $3 \times 3 \times 4$, so the answer is 334. In the second set every product is $1$, so $c_B(1) = 1$ for every candidate and the largest $o(B)$ wins. A candidate with three distinct values has $o(B) = 6$, the largest possible, and 234 is the lexicographically smallest of those.