Home » 国际竞赛 » Details

USACO 2021 February Contest, Gold Problem 2. Modern Art 3

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月4日下午5:01

USACO 2021 February Contest, Gold Problem 2. Modern Art 3

Having become bored with standard 2-dimensional artwork (and also frustrated at others copying her work), the great bovine artist Picowso has decided to switch to a more minimalist, 1-dimensional style. Her latest painting can be described by a 1-dimensional array of colors of length $N$ ( $1 \leq N \leq 300$ ), where each color is specified by an integer in the range $1 \dots N$ .

To Picowso's great dismay, her competitor Moonet seems to have figured out how to copy even these 1-dimensional paintings! Moonet will paint a single interval with a single color, wait for it to dry, then paint another interval, and so on. Moonet can use each of the $N$ colors as many times as she likes (possibly none).

Please compute the number of such brush strokes needed for Moonet to copy Picowso's latest 1-dimensional painting.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains $N$ .The next line contains $N$ integers in the range $1 \dots N$ indicating the color of each cell in Picowso's latest 1-dimensional painting.

OUTPUT FORMAT (print output to the terminal / stdout):

Output the minimum number of brush strokes needed to copy the painting.

SAMPLE INPUT:

10
1 2 3 4 1 4 3 2 1 6

SAMPLE OUTPUT:

In this example, Moonet may paint the array as follows. We denote an unpainted cell by $0$ .

Initially, the entire array is unpainted:
```
0 0 0 0 0 0 0 0 0 0
```
Moonet paints the first nine cells with color 1:
```
1 1 1 1 1 1 1 1 1 0
```
Moonet paints an interval with color 2:
```
1 2 2 2 2 2 2 2 1 0
```
Moonet paints an interval with color 3:
```
1 2 3 3 3 3 3 2 1 0
```
Moonet paints an interval with color 4:
```
1 2 3 4 4 4 3 2 1 0
```
Moonet paints a single cell with color 1:
```
1 2 3 4 1 4 3 2 1 0
```
Moonet paints the last cell with color 6:
```
1 2 3 4 1 4 3 2 1 6
```

Note that during the first brush stroke, Moonet could have painted the tenth cell with color $1$ in addition to the first nine cells without affecting the final state of the array.

SCORING:

In test cases 2-4, only colors $1$ and $2$ appear in the painting.
In test cases 5-10, the color of the $i$ -th cell is in the range $[12 ⌊ \frac{i - 1}{12} ⌋ + 1, 12 ⌊ \frac{i - 1}{12} ⌋ + 12]$ for each $1 \leq i \leq N$ .
Test cases 11-20 satisfy no additional constraints.

Problem credits: Brian Dean and Benjamin Qi

USACO 2021 February Contest, Gold Problem 2. Modern Art 3 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(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 $O (2^{M} p o l y (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 $dist$ in the solution below).

To transition from a state, we go through each of the $O (M^{2})$ possible ranges that a stroke can paint over and through each of the $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:

The endpoint cells of a segment must share the same color.
If two segments share an endpoint cell, that cell is the only cell they share.
Otherwise, the range spanned by one segment is strictly contained within the range spanned by the other.

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

If we draw a segment from cell $i$ to cell $j$ (only possible when these cells have the same color), then all remaining segments must be contained within the interval from cell $i + 1$ to cell $j - 1$ . This gives the transition $d p [i] [j] = max (d p [i] [j], 1 + d p [i + 1] [j - 1])$ .
Otherwise, there must exist some $i < k < j$ such that no segment crosses over cell $k$ . This gives the transition $d p [i] [j] = max_{i < k < j} (d p [i] [j], d p [i] [k] + d p [k] [j])$ .

Time Complexity: $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";
}

[/hide]