batman121's blog

Interview Problem (Coloring grid hackerrank Problem for larger inputs)
By batman121, history, 5 years ago, In English

I was giving hackerrank test for some company recently and came across the following question. I searched and found out that it's unsolvable(NP-hard) for the given constraint. Please let me know if you know how to solve this one.

Problem

Calculate the number of ways to color an N * M grid using K colors. Adjacent squares in the grid should have different colors. Squares are considered adjacent if they share an edge.

Constraint : 1<=N,W,K<=10^5

Thanks

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Some mathematical background:

https://math.stackexchange.com/questions/642921/chromatic-polynomial-of-a-grid-graph

I should note that finding the chromatic polynomial (i.e. a formula where you can plug in different different K to get the number of colorings) is open as you said, but this problem isn't asking for the chromatic polynomial, just for its value at a particular K. So maybe you are supposed to do a DP and calculate NumColorings(K) in terms of NumColorings(K-1).

→ Reply