USACO 2021 January Contest, Silver Problem 2. No Time to Paint

USACO 2021 January Contest, Silver Problem 2. No Time to Paint

Bessie has recently received a painting set, and she wants to paint the long fence at one end of her pasture. The fence consists of NN consecutive 1-meter segments (1≤N≤1051≤N≤105). Bessie has 26 different colors available, which she labels with the letters 'A' through 'Z' in increasing order of darkness ('A' is a very light color, and 'Z' is very dark). She can therefore describe the desired color she wants to paint each fence segment as a length-NN string where each character is a letter.

Initially, all fence segments are uncolored. Bessie can color any contiguous range of segments with a single color in a single brush stroke as long as she never paints a lighter color over a darker color (she can only paint darker colors over lighter colors).

For example, an initially uncolored segment of length four can be colored as follows:

 

.... -> BBB. -> BBLL -> BQQL

Running short on time, Bessie thinks she may need to leave some consecutive range of fence segments unpainted! Currently, she is considering QQ candidate ranges (1≤Q≤1051≤Q≤105), each described by by two integers (a,b)(a,b) with 1≤a≤b≤N1≤a≤b≤N giving the indices of endpoints of the range a…ba…b of segments to be left unpainted.

For each candidate range, what is the minimum number of strokes needed to paint every fence segment outside those in the range with its desired color while leaving all fence segments inside the range uncolored? Note that Bessie does not actually do any painting during this process, so the answers for each candidate range are independent.

 

 

 

SAMPLE INPUT:

8 2
ABBAABCB
3 6
1 4

SAMPLE OUTPUT:

4
3

In this example, excluding the sub-range corresponding to the desired pattern BAABBAAB requires four strokes to paint while excluding ABBAABBA requires only three.

 

.... -> AA.. -> ABBB -> ABCB

 

 

Problem credits: Andi Qu and Brian Dean

USACO 2021 January Contest, Silver Problem 2. No Time to Paint 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Brian Dean and Benjamin Qi)
For a candidate range (a,b), it suffices to compute the minimum number of strokes for the prefix of length a−1 and suffix of length N−b independently and add them up. Now let's describe how to compute the minimum number of strokes for each prefix (suffixes are computed similarly).

There are a few ways to accomplish this. Perhaps the easiest is to scan the input from left to right while maintaining a stack of "active brush strokes". Every time we see a higher color than the one on top of the stack, we push it onto the stack (so the stack will contain ascending colors from bottom to top). Every time we see a color c, we pop from the stack every color larger than c, since those brush strokes need to be ended for color c to be visible. The aggregate number of pushes onto the stack tells us the number of brush strokes required for each prefix. Here is Brian Dean's code that implements this idea, running in O(N+Q) time:

#include
#include
#include
using namespace std;
const int MAX_N = 100000;

string S;
int N, prefix_sol[MAX_N+1], suffix_sol[MAX_N+1];

void build_sol(int *sol)
{
stack active_colors;
for (int i=0; i<N; i++) { sol[i+1] = sol[i]; while (!active_colors.empty() && active_colors.top() > S[i]) active_colors.pop();
if (active_colors.empty() || active_colors.top() < S[i]) { active_colors.push(S[i]); sol[i+1]++; } } } int main(void) { int Q, i, j; cin >> N >> Q >> S;
build_sol(prefix_sol);
reverse (S.begin(), S.end());
build_sol(suffix_sol);
for (int q=0; q<Q; q++) { cin >> i >> j;
cout << prefix_sol[i-1] + suffix_sol[N-j] << "\n";
}
}
For another approach, let prefix[x] denote the answer for the prefix of length x. Given prefix[x], how do we compute prefix[x+1]?

Let c denote the color of fence segment x+1. If c already appeared within the prefix of length x and there is no segment with a lighter color between the last occurrence of c and segment x+1, then we can simply extend the stroke that painted that previous occurrence of c to paint segment x+1 as well. In this case, prefix[x+1]=prefix[x]. Otherwise, the best we can do is to use an additional stroke to paint the new occurrence of c, so prefix[x+1]=prefix[x]+1.

The code below maintains the lightest color that has appeared since the last occurrence of color t in min_since_last[t]. When a new color c is added, we set min_since_last[t]=min(min_since_last[t],c) for all t≠c and min_since_last[c]=c.

Both of the solutions below run in O(N⋅Σ+Q) time, where Σ is the number of different colors.

Brian Dean's code:

#include
using namespace std;

#define MAX_N 100000
int N, Q, min_since_last[26], prefix[MAX_N+1], suffix[MAX_N+2];

int main(void)
{
string s;
cin >> N >> Q >> s;

// Build prefix counts of # of strokes needed
for (int c=0; c<26; c++) min_since_last[c] = -1;
for (int i=1; i<=N; i++) {
int curchar = s[i-1] - 'A';
for (int c=0; c<26; c++) min_since_last[c] = min(curchar, min_since_last[c]);
prefix[i] = prefix[i-1];
if (min_since_last[curchar] < curchar) prefix[i]++;
min_since_last[curchar] = curchar;
}

// Build suffix counts of # of strokes needed
for (int c=0; c<26; c++) min_since_last[c] = -1; for (int i=N; i>=1; i--) {
int curchar = s[i-1] - 'A';
for (int c=0; c<26; c++) min_since_last[c] = min(curchar, min_since_last[c]);
suffix[i] = suffix[i+1];
if (min_since_last[curchar] < curchar) suffix[i]++;
min_since_last[curchar] = curchar;
}

for (int i=0; i<Q; i++) { int x, y; cin >> x >> y;
cout << prefix[x-1] + suffix[y+1] << "\n";
}
}
Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class NoTimeToPaint {

public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(in.readLine());
int n = Integer.parseInt(tokenizer.nextToken());
int m = Integer.parseInt(tokenizer.nextToken());
String colors = " " + in.readLine();
int[] last = new int[26];
int[] prefixes = new int[n + 1];
for (int j = 1; j <= n; j++) {
prefixes[j] = prefixes[j - 1];
int letter = colors.charAt(j) - 'A';
boolean isLeft = last[letter] == 0;
for (int lighter = 0; lighter < letter; lighter++) { if (last[lighter] > last[letter]) {
isLeft = true;
}
}
if (isLeft) {
prefixes[j]++;
}
last[letter] = j;
}
Arrays.fill(last, n + 1);
int[] suffixes = new int[n + 2];
for (int j = n; j >= 1; j--) {
suffixes[j] = suffixes[j + 1];
int letter = colors.charAt(j) - 'A';
boolean isRight = last[letter] == n + 1;
for (int lighter = 0; lighter < letter; lighter++) {
if (last[lighter] < last[letter]) {
isRight = true;
}
}
if (isRight) {
suffixes[j]++;
}
last[letter] = j;
}
StringBuilder out = new StringBuilder();
for (int j = 1; j <= m; j++) {
tokenizer = new StringTokenizer(in.readLine());
int a = Integer.parseInt(tokenizer.nextToken());
int b = Integer.parseInt(tokenizer.nextToken());
out.append(prefixes[a - 1] + suffixes[b + 1]).append('\n');
}
System.out.print(out);
}
}
[/hide]