Modern Art 3 USACO 2021 February Contest

Modern Art 3 USACO Solution

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 NN (1≤N≤3001≤N≤300), where each color is specified by an integer in the range 1…N1…N.

See Also : USACO 2021 Challenges

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 NN 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 NN.

The next line contains NN integers in the range 1…N1…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:

6

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

  • Initially, the entire array is unpainted:0 0 0 0 0 0 0 0 0 0
  • Moonet paints the first nine cells with color 11:1 1 1 1 1 1 1 1 1 0
  • Moonet paints an interval with color 22:1 2 2 2 2 2 2 2 1 0
  • Moonet paints an interval with color 33:1 2 3 3 3 3 3 2 1 0
  • Moonet paints an interval with color 44:1 2 3 4 4 4 3 2 1 0
  • Moonet paints a single cell with color 11:1 2 3 4 1 4 3 2 1 0
  • Moonet paints the last cell with color 66: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 11 in addition to the first nine cells without affecting the final state of the array.

SCORING:

  • In test cases 2-4, only colors 11 and 22 appear in the painting.
  • In test cases 5-10, the color of the ii-th cell is in the range [12⌊i−112⌋+1,12⌊i−112⌋+12][12⌊i−112⌋+1,12⌊i−112⌋+12] for each 1≤i≤N1≤i≤N.
  • Test cases 11-20 satisfy no additional constraints.

Problem credits: Brian Dean and Benjamin Qi

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

Subtask 2:

We can split the painting into groups of M=12M=12 and run O(2Mpoly(M))O(2Mpoly(M)) BFS on each group independently. A state consists of a bitmask of length MM where the ii-th bit of the bitmask is equal to one if the ii-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 distdist in the solution below).

To transition from a state, we go through each of the O(M2)O(M2) possible ranges that a stroke can paint over and through each of the O(M)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 xx and none of the cells in between them were last painted by stroke xx. The number of strokes required is equal to NN 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=611−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 dp[i][j]dp[i][j] to be the maximum possible number of segments if we only consider the range from cell ii to cell jj (0≤i<j<N0≤i<j<N).

  • If we draw a segment from cell ii to cell jj (only possible when these cells have the same color), then all remaining segments must be contained within the interval from cell i+1i+1 to cell j−1j−1. This gives the transition dp[i][j]=max(dp[i][j],1+dp[i+1][j−1])dp[i][j]=max(dp[i][j],1+dp[i+1][j−1]).
  • Otherwise, there must exist some i<k<ji<k<j such that no segment crosses over cell kk. This gives the transition dp[i][j]=maxi<k<j(dp[i][j],dp[i][k]+dp[k][j])dp[i][j]=maxi<k<j(dp[i][j],dp[i][k]+dp[k][j]).

Time Complexity: O(N3)O(N3)

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";
}

USACO 2021 February Contest

Weekly Contest 247

Biweekly Contest 55

Codechef Long Challenge Solutions

July Long Challenge 2021 Solutions

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Leave a Comment