ddeka's blog

paint wall with k colours
By ddeka, history, 5 years ago, In English

Given a wall of L*W size. The wall is made up of bricks of sizes 1*1. We need to color the wall with K(given) colors such that no two adjacent bricks (bricks sharing a side) get the same coloring. How many ways to do achieve that? constraint: K, L and W are in the range of 100000.

-- how to approach this QS? Simple dynamic programming (states as position and check all colors etc.) is not feasible with given constraint. Thanks!

  • Vote: I like it
  • -18
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Problem link? As far as I know, computing chromatic polynomials for grids is an open problem.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    There is no problem-link with me. This problem asked in some company coding test.

    → Reply