(Analysis by Benjamin Qi)

Based off Modern Art 2, although the solution is completely different.

Subtask 2:

We can split the painting into groups of $M=12$ and run $\mathcal{O}(2^Mpoly(M))$ BFS on each group independently. A state consists of a bitmask of length $M$ where the $i$-th bit of the bitmask is equal to one if the $i$-th cell is colored the way that it should be in the final painting, as well as the minimum number of strokes required to reach that bitmask (denoted by $\texttt{dist}$ in the solution below).

To transition from a state, we go through each of the $\mathcal{O}(M^2)$ possible ranges that a stroke can paint over and through each of the $\mathcal{O}(M)$ possible colors for the stroke.

Code (courtesy of Andrew Wang):

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e9;
vector<int> dist;
queue<int> q;

void add(int mask, int distance) { //add new mask to the queue + update distance
	if(dist[mask] != MAX)
	dist[mask] = distance;

int solve(vector<int> v, int lowest_color) {
	int N = v.size();
	dist.assign(1<<N, MAX);
	add(0, 0);
	while (q.size()) {
		int x = q.front(); q.pop();
		for(int color = lowest_color; color < lowest_color+12; color++) {
			//loop through intervals with same beginning + ending color
			for(int i = 0; i < N; i++) {
				if(v[i] == color) {
					for(int j = i; j < N; j++) {
						if(v[j] == color) {
							int cur_mask = x; 
							for(int k = i; k <= j; k++) {
								//if same color, then update the mask as correctly painted
								if (v[k] == color) 
									cur_mask |= 1 << k;
								//if already painted correctly, update it as painted over incorrectly
								else if (cur_mask & (1<<k)) 
									cur_mask ^= 1 << k;
							add(cur_mask, dist[x]+1);
	return dist[(1<<N)-1];

int main() {
	int N; cin >> N;
	vector<int> cur_batch;
	int ans = 0;
	for(int i = 0; 12*i < N; i++) { //breaking it up in batches of size <= 12
		for(int j = 12*i; j < 12*(i+1) && j < N; j++) {
			int a; cin >> a;
		ans += solve(cur_batch, 12*i+1);
	cout << ans << endl;

Full Solution:

Given an optimal way to paint, draw a segment between two distinct cells if they were last painted by the same stroke $x$ and none of the cells in between them were last painted by stroke $x$. The number of strokes required is equal to $N$ minus the number of such segments. For example, we can draw at most five segments for the following test case,

1 2 3 4 1 4 3 2 1 1 6

so the number of strokes required is $11-5=6$.

1---------------1-1 6

So we've reduced the problem to computing the maximum size of a set of segments satisfying all three of the following properties:

It suffices to do dynamic programming on ranges to compute the maximum possible number of segments. Define $dp[i][j]$ to be the maximum possible number of segments if we only consider the range from cell $i$ to cell $j$ ($0\le i<j<N$).

Time Complexity: $\mathcal{O}(N^3)$

My code follows:

#include <bits/stdc++.h>
using namespace std;
int N, dp[305][305];
int main() {
	cin >> N;
	vector<int> a(N); 
	for (int& t: a) cin >> t;
	for (int i = N-1; i >= 0; --i) 
		for (int j = i+1; j < N; ++j) {
			if (a[i] == a[j]) // draw segment from i to j
				dp[i][j] = max(dp[i][j],1+dp[i+1][j-1]);
			for (int k = i+1; k < j; ++k) // split at k
				dp[i][j] = max(dp[i][j],dp[i][k]+dp[k][j]);
	cout << N-dp[0][N-1] << "\n";