Overview

This problem asks us to find the minimum total cost to paint \(N\) boards using \(K\) colors such that adjacent boards have different colors. It can be solved by speeding up dynamic programming (DP) through an optimized state representation.

Analysis

Naive Dynamic Programming (DP)

Consider painting the boards from left to right. When deciding the color of the \(i\)-th board, the only factor that affects the choice is the color of the immediately preceding board (the \((i-1)\)-th board). Therefore, we can formulate the following dynamic programming (DP):

• \(DP[i][j]\): the minimum cost to paint boards \(1\) through \(i\) such that board \(i\) is painted with color \(j\).

The transition is as follows: $\(DP[i][j] = C_{i, j} + \min_{k \neq j} DP[i-1][k]\)$

However, naively computing this transition takes \(O(K)\) time for each board \(i\) (\(1 \le i \le N\)) and each color \(j\) (\(1 \le j \le K\)) to find the minimum over all other colors \(k \neq j\), resulting in an overall time complexity of \(O(N \times K^2)\). Since \(K\) can be up to \(10^6\), this approach will exceed the time limit (resulting in TLE).

Optimization Idea (Minimum and Second Minimum)

Let us focus on the expression \(\min_{k \neq j} DP[i-1][k]\). This computes “the minimum cost when the color of the previous board is anything other than \(j\).”

What happens if we precompute only the following two values among the costs of all colors for board \(i-1\)? 1. The minimum value (the cost and its corresponding color) 2. The second minimum cost

Then: - If the current color \(j\) is different from the color of the previous minimum: it is optimal to choose the previous minimum value. - If the current color \(j\) is the same as the color of the previous minimum: since adjacent boards cannot share the same color, we must choose the previous second minimum cost.

With this observation, we can compute the transition for each color \(j\) in \(O(1)\) time. Furthermore, for board \(i\), we only need to record its minimum and second minimum values before proceeding to the next board, eliminating the need to maintain an entire array for all colors.

Algorithm

1. From the costs \(C_{1, j}\) of board \(1\), find the minimum value (cost and color) and the second minimum value.
2. For \(i = 2, 3, \dots, N\), process board \(i\) in order:
   • Maintain the minimum and second minimum values of the previous board.
   • For each color \(j = 1, 2, \dots, K\):
     • If the color of the previous minimum is not \(j\), the cost is \((\text{previous minimum}) + C_{i, j}\).
     • If the color of the previous minimum is \(j\), the cost is \((\text{previous second minimum}) + C_{i, j}\).
     • Update the minimum and second minimum values for board \(i\) based on the computed cost.
3. After processing up to board \(N\), the minimum value for board \(N\) is the answer.

Complexity

• Time Complexity: \(O(N K)\)
  • Since the transition is computed in \(O(1)\) time for each board and each color, the total number of loop iterations is \(N \times K\).
  • Given the constraint \(N \times K \le 10^6\), this easily runs well within the execution time limit.
• Space Complexity: \(O(N K)\)
  • Instead of maintaining the entire DP table, we can process the boards by only storing the previous state (the minimum and second minimum values).
  • Reading the entire input at once uses \(O(NK)\) memory, which runs without issue under the given constraints.

Implementation Notes

• Fast I/O: Because the number of input elements can be up to approximately \(10^6\), repeatedly calling input() in Python will become an I/O bottleneck. Reading all input at once using sys.stdin.read().split() significantly speeds up execution.

• Initialization Values: Use a sufficiently large value (e.g., \(10^{18}\)) as the initial value when updating the minimums. Note that the total cost can reach up to \(10^5 \times 10^9 = 10^{14}\), which exceeds the range of a \(32\)-bit integer.

• Updating the Minimums: When a new cost is encountered:

  1. If it is smaller than the minimum, demote the current minimum to the second minimum, and update the minimum.

  2. If it is greater than or equal to the minimum and smaller than the second minimum, update only the second minimum. Be sure to perform this two-step check correctly.

     Source Code

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    K = int(input_data[1])

    INF = 10**18
    idx = 2

    min1_val = INF
    min1_idx = -1
    min2_val = INF

    for j in range(K):
        c = int(input_data[idx])
        idx += 1
        if c < min1_val:
            min2_val = min1_val
            min1_val = c
            min1_idx = j
        elif c < min2_val:
            min2_val = c

    for _ in range(1, N):
        next_min1_val = INF
        next_min1_idx = -1
        next_min2_val = INF

        prev_min1_val = min1_val
        prev_min1_idx = min1_idx
        prev_min2_val = min2_val

        for j in range(K):
            c = int(input_data[idx])
            idx += 1
            cost = (
                prev_min2_val + c if j == prev_min1_idx else prev_min1_val + c
            )

            if cost < next_min1_val:
                next_min2_val = next_min1_val
                next_min1_val = cost
                next_min1_idx = j
            elif cost < next_min2_val:
                next_min2_val = cost

        min1_val = next_min1_val
        min1_idx = next_min1_idx
        min2_val = next_min2_val

    print(min1_val)


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.8-flash-high.