Description

It has been a while since the last time Pak Dengklek painted the walls in his house, so he wants to repaint them. The wall consists of $N$ sections, numbered from $0$ to $N - 1$. In this problem, we assume there are $K$ different colors, represented by integers from $0$ to $K - 1$ (for example, red is represented by $0$, blue by $1$, and so on). Pak Dengklek wants to paint wall section $i$ with color $C[i]$.

To paint the wall, Pak Dengklek hired a contractor company with $M$ contractors, numbered from $0$ to $M - 1$. Unfortunately for Pak Dengklek, contractors are only willing to paint using colors they like. Specifically, contractor $j$ likes $A[j]$ colors, and only wants to paint using one of the following colors: color $B[j][0]$, color $B[j][1]$, $\dots$, or color $B[j][A[j] − 1]$.

Pak Dengklek can give the contractor company some instructions. In a single instruction, Pak Dengklek gives two parameters $x$ and $y$, where $0 \leq x < M$ and $0 \leq y \leq N - M$. The contractor company will assign contractor $((x + l) \mod M)$ to paint wall section $(y + l)$, where $0 \leq l < M$. If there exists an $l$ such that contractor $((x + l) \mod M)$ does not like color $C[y + l]$, then that instruction is invalid.

Pak Dengklek has to pay for each instruction, so he wants to know the minimum number of instructions he must give so that every wall section is painted in its intended color, or determine that his goal is impossible. Each wall section may be painted multiple times, but every time it is painted, the color must be the one Pak Dengklek intends.

You must implement the function minimumInstructions:

• minimumInstructions(N, M, K, C, A, B) - This function will be called exactly once by the grader.
  • $N$: an integer representing the number of wall sections.
  • $M$: an integer representing the number of contractors.
  • $K$: an integer representing the number of colors.
  • $C$: an integer sequence of length $N$, representing the intended color of each wall section.
  • $A$: an integer sequence of length $M$, representing how many colors each contractor likes.
  • $B$: a sequence (of length $M$) whose elements are sequences, representing the specific colors each contractor likes.
  • The function must return an integer: the minimum number of instructions Pak Dengklek needs to ensure the wall is painted as intended; return $-1$ if it is impossible.

Input Format

The sample grader reads input in the following format:

N M K
C[0] C[1] ... C[N-1]
A[0] B[0][0] B[0][1] ... B[0][A[0]-1]
A[1] B[1][0] B[1][1] ... B[1][A[1]-1]
.
.
.
A[M-1] B[M-1][0] B[M-1][1] ... B[M-1][A[M-1]-1]

Output Format

The sample grader outputs the return value of the function minimumInstructions.

8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4

3

5 4 4
1 0 1 2 2
2 0 1
1 1
1 2
1 3

-1

Hint

In the first sample, $N = 8$, $M = 3$, $K = 5$, $C = [3, 3, 1, 3, 4, 4, 2, 2]$, $A = [3, 2, 2]$, $B = [[0, 1, 2], [2, 3], [3, 4]]$. Pak Dengklek can give the following instructions.

1. $x = 1$, $y = 0$. This is a valid instruction. Contractor $1$ can paint wall section $0$, contractor $2$ can paint wall section $1$, and contractor $0$ can paint wall section $2$.
2. $x = 0$, $y = 2$. This is a valid instruction. Contractor $0$ can paint wall section $2$, contractor $1$ can paint wall section $3$, and contractor $2$ can paint wall section $4$.
3. $x = 2$, $y = 5$. This is a valid instruction. Contractor $2$ can paint wall section $5$, contractor $0$ can paint wall section $6$, and contractor $1$ can paint wall section $7$.

It is easy to see that Pak Dengklek cannot achieve his goal with fewer than $3$ instructions, so minimumInstructions(8, 3, 5, [3, 3, 1, 3, 4, 4, 2, 2], [3, 2, 2], [[0, 1, 2], [2, 3], [3, 4]]) should return $3$.

In the second sample, $N = 5$, $M = 4$, $K = 4$, $C = [1, 0, 1, 2, 2]$, $A = [2, 1, 1, 1]$, $B = [[0, 1], [1], [2], [3]]$. Since contractor $3$ only likes color $3$, but no wall section is intended to be painted with that color, Pak Dengklek cannot give any valid instruction. Therefore, minimumInstructions(5, 4, 4, [1, 0, 1, 2, 2], [2, 1, 1, 1], [[0, 1], [1], [2], [3]]) should return $-1$.

For $0 \leq k < K$, let $f(k)$ denote the number of contractors who like color $k$.

Constraints

• $1 \leq N \leq 10^5$.
• $1 \leq M \leq \min(N, 5 \times 10^4)$.
• $1 \leq K \leq 10^5$.
• $0 \leq C[i] < K$.
• $1 \leq A[j] \leq K$.
• $0 \leq B[j][0] < B[j][1] < \dots < B[j][A[j] − 1] < K$.
• $\sum f(k)^2 \leq 4\times 10^5$.

Subtask $1$ ($12$ points)

• $f(k) \leq 1$.

Subtask $2$ ($15$ points)

• $N \leq 500$.
• $M \leq \min(N, 200)$.
• $\sum f(k)^2 \leq 1 000$.

Subtask $3$ ($13$ points)

• $N \leq 500$.
• $M \leq \min(N, 200)$.

Subtask $4$ ($23$ points)

• $N \leq 20 000$.
• $M \leq \min(N, 2 000)$.

Subtask $5$ ($37$ points)

• No additional constraints.

Translated by ChatGPT 5