No Time to Dry USACO 2021 February Contest

No Time to Dry 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≤2⋅1051≤N≤2⋅105). Bessie has NN different colors available, which she labels with the letters 11 through NN in increasing order of darkness (11 is a very light color, and NN is very dark). She can therefore describe the desired color she wants to paint each fence segment as an array of NN integers.

See Also : USACO 2021 Challenges

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:

0000 -> 1110 -> 1122 -> 1332

Unfortunately, Bessie doesn’t have time to waste watching paint dry. Thus, Bessie thinks she may need to leave some fence segments unpainted! Currently, she is considering QQ candidate ranges (1≤Q≤2⋅1051≤Q≤2⋅105), each described 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 painted.

For each candidate range, what is the minimum number of strokes needed to paint every fence segment inside the range with its desired color while leaving all fence segments outside 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 an array of NN integers 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 paint.

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

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

SAMPLE INPUT:

8 4
1 2 2 1 1 2 3 2
4 6
3 6
1 6
5 8

SAMPLE OUTPUT:

2
3
3
3

In this example, the sub-range corresponding to the desired pattern

1 1 2 

requires two strokes to paint. The sub-range corresponding to the desired pattern

2 1 1 2

requires three strokes to paint. The sub-range corresponding to the desired pattern

1 2 2 1 1 2

requires three strokes to paint. The sub-range corresponding to the desired pattern

1 2 3 2

requires three strokes to paint.

SCORING:

  • Test cases 1-2 satisfy N,Q≤100N,Q≤100.
  • Test cases 3-5 satisfy N,Q≤5000N,Q≤5000.
  • In test cases 6-10, the input array contains no integer greater than 1010.
  • Test cases 11-20 satisfy no additional constraints.

Problem credits: Andi Qu, Brian Dean, and Benjamin Qi

Let AaAa denote the color of fence segment aa for each a∈[1,N]a∈[1,N].

Approach 1:

The minimum number of strokes required to paint a subrange [a,b][a,b] is equal to b−a+1b−a+1 minus the number of indices (l,r)(l,r) such that Al=Ar<minl<i<rAiAl=Ar<minl<i<rAi (similarly as Modern Art from the Gold contest).

In the sample case, the pairs of indices are (1,4)(1,4), (2,3)(2,3), (4,5)(4,5), and (6,8)(6,8).

To generate all such pairs of indices (there are O(N)O(N) of them), we can use a monotonic stack (as alluded to by the analysis for the silver problem). The diagram below displays which elements are in the stack at what times for the sample case (11 and 22 remain in the stack at the end):

            3
  2-2     2---2- ...
1-----1-1------- ...

Computing the number of intervals contained within some query interval can be done offline in O(logN)O(log⁡N) per query; answer queries in increasing order of right endpoint and store a BIT for the left endpoints.

Time Complexity: O((N+Q)logN)O((N+Q)log⁡N)

#include <bits/stdc++.h>
using namespace std;
 
#define f first
#define s second

const int MX = 2e5+5;

int N,Q;
vector<pair<int,int>> query[MX];

struct {
	int bit[MX];
	int sum(int i) {
		int sum = 0;
		for (;i;i-=i&-i) sum += bit[i];
		return sum;
	}
	int query(int l, int r) { return sum(r)-sum(l-1); }
	void inc(int i) { for (;i<MX;i+=i&-i) ++bit[i]; }
} BIT;

int main() {
	cin >> N >> Q; 
	vector<int> A(N), ans(Q); 
	for (int& t: A) cin >> t;
	for (int i = 0; i < Q; ++i) {
		int l,r; cin >> l >> r; --l,--r;
		query[r].push_back({l,i});
	}
	vector<int> stk;
	for (int i = 0; i < N; ++i) {
		while (!stk.empty() && A[stk.back()] > A[i]) stk.pop_back();
		if (!stk.empty() && A[stk.back()] == A[i]) { // consider pair (stk.back(),i)
			BIT.inc(1+stk.back());
			stk.back() = i;
		} else stk.push_back(i);
		for (pair<int,int> q: query[i])
			ans[q.s] = i-q.f+1-BIT.query(q.f+1,i+1);
	}
	for (int t: ans) cout << t << "\n";
}

Approach 2 (courtesy of Spencer Compton):

The pairs of indices above join the segments into several connected components. For example, the connected components in the sample case are [1,4,5],[2,3],[6,8],[7][1,4,5],[2,3],[6,8],[7]. Define is_last[i]is_last[i] to be true if ii is the last number in its group and there exists some j>ij>i such that Aj<AiAj<Ai. So for the sample case, is_last[3]is_last[3] and is_last[7]is_last[7] are both true. As in the above solution, we can generate all such indices ii with a monotonic stack.

The answer for a query [l,r][l,r] is equal to the number of i∈[l,r]i∈[l,r] such that is_last[i]is_last[i] is true (which we can compute in O(1)O(1) using prefix sums), plus some additional contribution by connected components that continue past rr, if the greatest index included in such a component that is at most rr is at least ll.

For example, the answer to the query (3,6)(3,6) in the sample case is 33 because

  • is_last[3]is_last[3] is true
  • The component starting at index 11 continues past index 66, greatest index at most 66 is 5≥35≥3.
  • The component starting at index 66 continues past index 66, greatest index at most 66 is 6≥36≥3.

We can maintain these indices in a stack last_foundlast_found. For every query, binary search on the stack to count the number of indices at least ll. The time complexity remains the same.

#include <bits/stdc++.h>
using namespace std;

const int MX = 2e5+5;

#define f first
#define s second
#define sz(x) (int)(x).size()

int N,Q;
vector<pair<int,int>> query[MX];

int main() {
	cin >> N >> Q;
	vector<int> A(N);
	for (int& t: A) cin >> t;
	for (int i = 0; i < Q; ++i) {
		int l,r; cin >> l >> r; --l,--r;
		query[r].push_back({l,i});
	}
	vector<bool> is_last(N);
	vector<pair<int,int>> stk;
	for (int i = 0; i < N; ++i) {
		while (!stk.empty() && stk.back().f > A[i]) {
			is_last[stk.back().s] = true;
			stk.pop_back();
		}
		if (!stk.empty() && stk.back().f == A[i]) stk.back().s = i;
		else stk.push_back({A[i],i});
	}
	vector<int> cum_last{0}, last_found;
	vector<int> ans(Q);
	for (int r = 0; r < N; ++r) {
		cum_last.push_back(cum_last.back());
		if (!last_found.empty() && A[r] == A[last_found.back()]) 
			last_found.pop_back();
		last_found.push_back(r);
		if (is_last[r]) {
			++cum_last.back();
			last_found.pop_back();
		}
		for (pair<int,int> p: query[r]) {
			int lo = 0, hi = sz(last_found);
			while (lo < hi) {
				int mid = (lo+hi)/2;
				if (p.f <= last_found[mid]) hi = mid;
				else lo = mid+1;
			}
			ans[p.s] = cum_last[r+1]-cum_last[p.f]+sz(last_found)-lo;
		}
	}
	for (int t: ans) cout << t << "\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