1032HardDynamic ProgrammingGraph Coloring

Colouring a Three-Wide Panel

Tracked in this browser only

Trains the technique from

LeetCode 1411Number of Ways to Paint N × 3 Grid

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A panel is n rows tall and three cells wide. Each cell is to be painted red, yellow or green so that no two cells sharing an edge carry the same colour.

Return how many paintings there are, given as the remainder after dividing by 1000000007.

Examples

Example 1

Input: n = 2
Output: 54

Twelve rows are legal on their own. Each of the six whose ends match allows five rows below it and each of the six with three different colours allows four, which comes to fifty-four two-row panels.

Example 2

Input: n = 6
Output: 23346

Six rows deep, the two running tallies have been stepped down five times and add to twenty-three thousand three hundred and forty-six.

Example 3

Input: n = 3
Output: 246

Three rows deep the count is two hundred and forty-six, small enough that the remainder never bites.

Constraints

1 <= n <= 5000

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def num_of_ways(n: int) -> int:

Java

public int numOfWays(int n)

The intended approach

Time O(n) over the panel's height.Space O(1).

Only the row just painted constrains the next one, and within a row the three cells already have to avoid their neighbours. That leaves two shapes of row: the two outer cells sharing a colour with a different one between them, and all three colours different. Each shape can be coloured six ways, so twelve rows are legal in all. Next, how many rows can follow a given one? A row whose ends match allows five: three of its own shape and two of the other. A row of three different colours allows four: two of each shape. Neither count depends on which colours were used, only on the shape, so two running totals carry everything needed. Start both totals at six for the first row, then step down the panel. The next tally of matching-ended rows is three of the current matching-ended plus two of the current all-different, and the next tally of all-different rows is two of each. Adding the two totals at the bottom gives the answer. Every step is a few multiplications taken to the remainder, so the panel costs its height.

Pythonentry point: num_of_ways

def num_of_ways(n):
    mod = 1000000007
    same = 6
    apart = 6
    for _ in range(n - 1):
        same, apart = (3 * same + 2 * apart) % mod, (2 * same + 2 * apart) % mod
    return (same + apart) % mod

The obvious version

Work with the twelve legal rows themselves rather than the two shapes. List every triple of colours whose neighbours differ, then step down the panel carrying a count for each particular row, and for each pair of rows check cell by cell that they differ before adding the count across. Adding the counts at the bottom gives the answer. Costs the rows squared per step rather than two numbers.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_num_of_ways(n):
    mod = 1000000007
    rows = []
    for a in range(3):
        for b in range(3):
            for c in range(3):
                if a != b and b != c:
                    rows.append((a, b, c))
    count = [1] * len(rows)
    for _ in range(n - 1):
        nxt = [0] * len(rows)
        for i in range(len(rows)):
            for j in range(len(rows)):
                if (rows[i][0] != rows[j][0] and rows[i][1] != rows[j][1]
                        and rows[i][2] != rows[j][2]):
                    nxt[j] = (nxt[j] + count[i]) % mod
        count = nxt
    total = 0
    for value in count:
        total = (total + value) % mod
    return total

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in