paint wall with k colour

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

Obviously, it is a DP problem. But giving a solution would kill your opportunity to learn.

Rather, there is a similar problem that appeared in Topcoder. Here is the Editorial for the same -

https://apps.topcoder.com/wiki/display/tc/SRM+532

Go through it and learn the concept of Profiling. That would help you in solving your problem.

1 Like

Where is the problem link? Is it from an ongoing contest?

No, it is not from any contest. I remember this QS from some OJ, idk the name of the OJ.