Number of ways to fill a 2xN grid with M colors

Question

This question was asked in the onsite regionals for ACM ICPC 2013 at Amritapuri. In short, the question asked to find the number of ways to fill a $ 2\times N$ grid with $M$ colors such that no two cells with the same row or same column have the same color.

The limits given are $1 \leq N$, and $M \leq 1000$ with 1000 test cases per input.

Based on the constraints the approach that comes to my mind after a long struggle includes having a precomputed DP table which can be used for every test case. I tried to apply the inclusion-exclusion principle but could not come up with any solution. I also tried to solve it using bipartite perfect matchings, but no success. How should I approach this question?

Answer 1

You can use inclusion-exclusion. There are $M!/(M-N)!$ choices for the first row. Fix these choices. The number of choices for the second row in which $T$ specific columns are bad (but the row itself is good) is $(M-T)!/(M-N)!$. According to the inclusion-exclusion principle, the required number is $$ \frac{M!}{(M-N)!} \sum_{T=0}^N (-1)^T \binom{N}{T} \frac{(M-T)!}{(M-N)!}. $$ I'll let you take it from here.

Answer 2

There is a simpler way to solve your problem, but just for fun, I'll outline a different approach that generalizes nicely. For a real-world implementation, the advantages should also be clear.

You can cast this problem, and similar problems like Sudoku as constraint satisfaction problems. After modeling the problem, you can feed it to a state-of-the-art solver such as MINION that does the dirty work for you. MINION can handle finding a single solution, as well as counting all the solutions to a problem.

In what follows, I'll present a short input file to MINION to solve an $2 \times M$ instance of your problem, where $M=3$.

MINION 3

**VARIABLES**
DISCRETE q[3] {0..2}
DISCRETE r[3] {0..2}

**CONSTRAINTS**
alldiff(q)
alldiff(r)
diseq(q[0],r[0])
diseq(q[1],r[1])
diseq(q[2],r[2])

**EOF**

There is a variable corresponding to every vertex in the grid graph, the other side of the graph is modeled by the array $q$, and the other one with $r$, if you will. Each one takes a value from the domain $0..M$, where $M=3$ in this example. The constraints ensure that vertices in a row must be colored with different colors, and that opposite vertices (meaning the two vertices in a column) receive different colors.

Answer 3

Your problem statement says you want to find one example of a solution. If that is really correct, here is a very simple way to find one solution.

• If $M < N$, there is no solution. (Proof: consider how you're going to fill in the top row. You're screwed no matter what you do.)

• If $M=N$, it is easy solution. Fill in the top row with any permutation of the $M$ colors. You can make the second row the same as the first row, but shifted over by one place. That will satisfy all the constraints.

• If $M>N$, then throw away $M-N$ of the colors (your solution won't use them) and fill in the grid using just the first $M$ colors, using the method of the previous case.