No Time to Paint USACO 2021 January Contest

No Time to Paint USACO Solution

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.

See Also: USACO 2021 January Contest

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.

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

The first line contains NN and QQ.

The next line contains a string of length NN characters representing the desired color for each fence segment.

The next QQ lines each contain two space-separated integers aa and bb representing a candidate range to possibly leave unpainted.

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

For each of the QQ candidates, output the answer on a new line.

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

SCORING:

  • Test cases 1-4 satisfy N,Q≤100N,Q≤100.
  • Test cases 5-7 satisfy N,Q≤5000N,Q≤5000.
  • Test cases 8-13 satisfy no additional constraints.

Problem credits: Andi Qu and Brian Dean

Solution

For a candidate range (a,b)(a,b), it suffices to compute the minimum number of strokes for the prefix of length a−1a−1 and suffix of length N−bN−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 cc, we pop from the stack every color larger than cc, since those brush strokes need to be ended for color cc 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)O(N+Q) time:

#include <iostream>
#include <algorithm>
#include <stack>
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<char> 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]prefix[x] denote the answer for the prefix of length xx. Given prefix[x]prefix[x], how do we compute prefix[x+1]prefix[x+1]?

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

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

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

Brian Dean’s code:

#include <iostream>
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);
    }
}

USACO 2021 January Contest Solution

Leave a Comment