Page Contents

*Modern Art 3 USACO Solution*

*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*

*USACO 2021 February Contest*

*Clockwise Fence USACO 2021 February Contest**Just Green Enough USACO 2021 February Contest**Year of the Cow USACO 2021 February Contest**Comfortable Cows USACO 2021 February Contest**Count the Cows USACO 2021 February Contest**Modern Art 3 USACO 2021 February Contest**Stone Game USACO 2021 February Contest**Counting Graphs USACO 2021 February Contest**Minimizing Edges USACO 2021 February Contest**No Time to Dry USACO 2021 February Contest**Maze Tac Toe USACO 2021 US**Balanced Subsets USACO 2021 US**Routing Schemes USACO 2021 US**United Cows of Farmer John USACO 2021 US*

*Weekly Contest 247*

*Weekly Contest 247*

- Maximum Product Difference Between Two Pairs
- Cyclically Rotating a Grid
- Number of Wonderful Substrings
- Count Ways to Build Rooms in an Ant Colony

*Biweekly Contest 55*

*Biweekly Contest 55*

- Remove One Element to Make the Array Strictly Increasing
- Remove All Occurrences of a Substring
- Maximum Alternating Subsequence Sum
- Design Movie Rental System

*Codechef Long Challenge Solutions*

*Codechef Long Challenge Solutions*

*July Long Challenge 2021 Solutions*

*July Long Challenge 2021 Solutions*

*Maximum Production**Relativity**XxOoRr**Optimal Denomination**K Path Query**Chef vs Bharat**Chef and Pairs**Even Odd Partition**Dakimakura Distribition**Madoka and Ladder Decomposition*

*June Long Challenge 2021 Solutions*

*June Long Challenge 2021 Solutions*

*Maximum Frequent Subarray Sum solution codechef**Dual Distance solution codechef**Optimal Xor Set solution codechef**Minimum Subtree Cover solution codechef**Minimum Dual Area solution codechef**Bitwise Tuples solution codechef**Shortest Route solution codechef**Bella ciao solution codechef**Summer Heat solution codechef*

*March Long Challenge 2021 Solutions*

*March Long Challenge 2021 Solutions*

*An Interesting Sequence ISS SOLUTION**Tree House THOUSES SOLUTION**Valid Paths VPATH SOLUTION**Modular Equation MODEQ SOLUTION**Tic Tac Toe TCTCTOE SOLUTION**Xor Equality XOREQUAL SOLUTION**Golf LKDNGOLF SOLUTION**Solubility SOLBLTY SOLUTION*

*April Long Challenge 2021 Solutions*

*April Long Challenge 2021 Solutions*

*Chef and Dice SDICE Solution**Worthy Matrix KAVGMAT Solution**Binary String MEX MEXSTR Solution**Boolean Game BOOLGAME Solution**Tree Permutations TREEPERM Solution**Destroy the EMP Chip CHAOSEMP Solution**Chef and Pair Flips PAIRFLIP Solution**String Power STRPOW Solution**Brahma and Shiva SHRINES Solution**Water Sort Puzzle (Challenge) WTRSORT Solution**World Record BOLT Solution**Strong Language SSCRIPT Solution**Valid Pair SOCKS1 Solution*

*February Long Challenge 2021*

*February Long Challenge 2021*

- 1. Frog Sort Solution Codechef
- 2. Chef and Meetings Solution Codechef
- 3. Maximise Function Solution Codechef
- 4. Highest Divisor Solution Codechef
- 5. Cut the Cake Challenge Solution Codechef
- 6. Dream and the Multiverse Solution Codechef
- 7. Cell Shell Solution Codechef
- 8. Multiple Games Solution Codechef
- 9. Another Tree with Number Theory Solution Codechef
- 10. XOR Sums Solution Codechef
- 11. Prime Game Solution CodeChef
- 12. Team Name Solution Codechef

*January Long Challenge 2021*

*January Long Challenge 2021*

**Chef and Division 3 DIVTHREE SOLUTION Code Chef****Encoded String DECODEIT SOLUTION Code Chef****Point Of Impact BILLRD SOLUTION Code Chef****Fair Elections FAIRELCT SOLUTION Code Chef****Watching CPL WIPL SOLUTION Code Chef****Chef and Ants ANTSCHEF SOLUTION Code Chef****Blackjack BLKJK SOLUTION Code Chef****And-Or Game ORAND SOLUTION Code Chef****Stack-Queue Sort (Challenge) SQSORT SOLUTION Code Chef****Expected Number of SCCs RCTEXSCC SOLUTION Code Chef****Curious Matrix CURMAT SOLUTION Code Chef****Cool Subsets COOLSBST SOLUTION Code Chef****Sequence Creation ARCRT SOLUTION Code Chef****Greedy Students GRDSTD SOLUTION Code Chef**

*November Challenge 2020 SOLUTION CodeChef*

*November Challenge 2020 SOLUTION CodeChef*

- Ada and Dishes SOLUTION ADADISH
- Iron Magnet and Wall SOLUTION FEMA2
- Magical Candy Store SOLUTION CNDYGAME
- Unusual Queries SOLUTION UNSQUERS
- Red-Black Boolean Expression SOLUTION RB2CNF
- Chef and the Combination Lock SOLUTION CHEFSSM
- Scalar Product Tree SOLUTION SCALSUM
- Connect on a Grid (Challenge) SOLUTION CONGRID

*October Lunchtime 2020 CodeChef SOLUTIONS*

*October Lunchtime 2020 CodeChef SOLUTIONS*

- AND Plus OR SOLUTION ANDOR
- Chef and Subtree MEXs SOLUTION SUBMEXS
- Chef Likes Good Sequences SOLUTION GSUB
- Cute Chef Gift SOLUTION COPAR
- Chef Is Just Throwing Random Words SOLUTION SSO
- Counting Spaghetti SOLUTION CDSUMS
- Chef and Edge Flipping SOLUTION EFLIP