Overview

We want to find the minimum total cost to paint the boards such that no two adjacent boards have the same color. By using dynamic programming (DP) and maintaining the “minimum value” and the “second minimum value” up to the previous board, this problem can be solved in \(O(NK)\) time.

Analysis

Using the Last Painted Color as the State

The colors that can be used for board \(i\) depend on the color of board \(i-1\). Therefore, we consider the following DP:

\(dp[i][j] =\) the minimum total cost to paint boards \(1\) through \(i\) satisfying the condition, such that board \(i\) is painted with color \(j\)

Since the first board has no adjacency constraints, \(dp[1][j] = C_{1,j}\).

When painting board \(i\) with color \(j\), the previous board must be painted with a color other than \(j\). Therefore, for \(i \geq 2\), the transitions are as follows:

\(dp[i][j] = C_{i,j} + \min_{x \neq j} dp[i-1][x]\)

However, checking all colors other than \(j\) for each state would result in a time complexity of \(O(NK^2)\), which will exceed the time limit.

Tracking Only the Minimum and Second Minimum Values

What we need for the transition is “the minimum value when excluding a specific single color.”

For the previous board’s DP values, we maintain the following three quantities:

• best: the minimum value among all colors
• best_color: one of the colors that achieves this minimum value
• second: the minimum value among colors excluding best_color

When painting the current board with color color, we can determine the transition as follows:

• If color != best_color, we can transition from best_color, so we use best.
• If color == best_color, we cannot transition from that color, so we use second.

This allows us to compute each state in \(O(1)\) time.

For example, if the previous DP values for colors \(1,2,3\) in order are \((4,4,9)\), we can set best = 4, best_color = 1, and second = 4. This is because even if color \(1\) is excluded, the value \(4\) of color \(2\) is still available.

Note that the “second minimum value” here is not strictly the smallest value that is greater than the minimum. If different colors have the same value, best and second can be equal.

Algorithm

In the implementation, rather than maintaining the entire DP array, we only update the three pieces of information described above.

1. Initialize best = second = 0 and best_color = -1.

   • -1 represents a non-existent color.
   • For the first board, best = 0 will be used for all colors, so the computed values naturally become \(C_{1,j}\).

2. Process the boards from left to right.

   • Initialize new_best (the minimum value for the current board) and new_second (the second minimum value for the current board) to sufficiently large values.
   • For each color color, compute the following value:

   value = cost + (second if color == best_color else best)

   • Update the information for the current board using value:
     • If value < new_best, move the current new_best to new_second, and update new_best and its corresponding color.
     • Otherwise, if value < new_second, update only new_second.

3. After processing all colors for that board, replace best, second, and best_color with the newly obtained values.

4. After processing all boards, output best.

The value for each color is the sum of the minimum cost of painting the previous board with a different color and the cost of painting the current board. Therefore, this update correctly computes the DP transition formula. The final best represents the minimum cost regardless of the color of the last board.

Complexity

• Time complexity: \(O(NK)\)
  For each color of each board, we perform a constant-time computation. Given the constraints \(NK \leq 10^6\), this is sufficiently fast.
• Space complexity: \(O(NK)\)
  The provided code reads the entire input at once using read().split(), which takes \(O(NK)\) memory to store. The additional space required for the DP computation itself is \(O(1)\).

Implementation Notes

• Include other colors with the same value as candidates for the second minimum.
  In the code, even if value == new_best, it can be recorded in new_second by the subsequent elif value < new_second.

• Separate the information of the previous board from that of the current board.
  If you overwrite best and other variables while iterating through colors, information from the current board will mix into the calculations for other colors. Aggregate values into new_best, etc., and replace them only after processing all colors.

• Handle large integers.
  The total cost can be up to \(N \times 10^9 \leq 10^{14}\). Python handles arbitrarily large integers automatically, but languages with fixed-width integer types require 64-bit integers. In the code, inf = 10**30 is sufficiently larger than any possible answer.

• In the code, color indices range from \(0\) to \(K-1\). The initial value best_color = -1 does not match any actual color.

  Source Code

import sys


def main():
    data = map(int, sys.stdin.buffer.read().split())
    n = next(data)
    k = next(data)

    inf = 10**30
    best = second = 0
    best_color = -1

    for _ in range(n):
        new_best = inf
        new_second = inf
        new_color = -1

        for color in range(k):
            cost = next(data)
            value = cost + (second if color == best_color else best)

            if value < new_best:
                new_second = new_best
                new_best = value
                new_color = color
            elif value < new_second:
                new_second = value

        best = new_best
        second = new_second
        best_color = new_color

    print(best)


if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-6-astra-medium.