Firstly, let us notice that each picture can be represented as a graph where the number of nodes corresponds to the number of areas that need to be filled out, and two nodes are connected if the corresponding areas are adjacent. Each node has to be paired with one of the ~K~ colors in a way that two adjacent nodes are colored differently and three different colors are used at most.

A significant part of the official test cases contained a small enough ~K~ and an image with small enough number of nodes so that naive implementations of the aforementioned procedure were enough for ~50\%~ of points on this task.

Let ~j(n)~, ~d(n)~ and ~t(n)~ denote the number of ways the ~n^\text{th}~ image can be colored exactly with one, exactly with two and exactly with three different colors, respectively. Then the final solution is equal to ~j(n) \times K + d(n) \times K \times (K-1)/2 + t(n) \times K \times (K-1) \times (K-2)/6~. In all pictures, it holds ~j(n) = 0~ so we can ignore coloring using only one color. If the picture can be colored using two colors, then ~d(n) = 2~. We are still left with finding ~t(n)~.

All pictures beside the caterpillar, pyramid and trampoline are represented by a graph with a small enough number of nodes ~v~ so determining the number ~t(n)~ in the complexity of ~\mathcal O(3^v)~ is fast enough. This approach was enough for ~62.5\%~ of points on this task.

It needs to be pointed out that it was possible to calculate the numbers ~j(n)~, ~d(n)~ and ~t(n)~ for each picture by hand. A lot of competitors approached the task in this way, but often made a mistake during calculation.

The mentioned three images (caterpillar, pyramid and trampoline) should be analyzed in more detail. For example, we can notice that, by filling out the second row of the pyramid, we will unambiguously determine the rest of the pyramid. We leave similar observations as practise to the reader.