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) return; dist[mask] = distance; q.push(mask); } 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() { cin.tie(0)->sync_with_stdio(0); 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; cur_batch.push_back(a); } ans += solve(cur_batch, 12*i+1); cur_batch.clear(); } 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,
11 1 2 3 4 1 4 3 2 1 1 6
so the number of strokes required is $11-5=6$.
1 4---4 3-------3 2-----------2 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"; }