Home » 国际竞赛 » Details

USACO 2021 December Contest, Gold Problem 2. HILO

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月5日下午1:03

USACO 2021 December Contest, Gold Problem 2. HILO

Bessie knows a number $x + 0.5$ where $x$ is some integer between $0$ to $N,$ inclusive ( $1 \leq N \leq 2 \cdot 10^{5}$ ).

Elsie is trying to guess this number. She can ask questions of the form "is $i$ high or low?" for some integer $i$ between $1$ and $N,$ inclusive. Bessie responds by saying "HI" if $i$ is greater than $x + 0.5$ , or "LO" if $i$ is less than $x + 0.5$ .

Elsie comes up with the following strategy for guessing Bessie's number. Before making any guesses, she creates a list of $N$ numbers, where every number from $1$ to $N$ occurs exactly once (in other words, the list is a permutation of size $N$ ). Then she goes through the list, guessing numbers that appear in the list in order.

However, Elsie skips any unnecessary guesses. That is, if Elsie is about to guess some number $i$ and Elsie previously guessed some $j < i$ and Bessie responded with "HI", Elsie will not guess $i$ and will move on to the next number in the list. Similarly, if she is about to guess some number $i$ and she previously guessed some $j > i$ and Bessie responded with "LO", Elsie will not guess $i$ and will move on to the next number in the list. It can be proven that using this strategy, Elsie always uniquely determines $x$ regardless of the permutation she creates.

If we concatenate all of Bessie's responses of either "HI" or "LO" into a single string $S$ , then the number of times Bessie says "HILO" is the number of length $4$ substrings of $S$ that are equal to "HILO."

Bessie knows that Elsie will use this strategy; furthermore, she also knows the exact permutation that Elsie will use. However, Bessie has not decided on what value of $x$ to choose.

Help Bessie determine how many times she will say "HILO" for each value of $x$ .

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

The first line contains $N .$ The second line contains Elsie's permutation of size $N .$

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

For each $x$ from $0$ to $N$ , inclusive, output the number of times Bessie will say HILO on a new line.

SAMPLE INPUT:

5
5 1 2 4 3

SAMPLE OUTPUT:

For $x = 0$ , Bessie will say "HIHI," for a total of zero "HILO"s.

For $x = 2$ , Bessie will say "HILOLOHIHI," for a total of one "HILO".

For $x = 3$ , Bessie will say "HILOLOHILO", for a total of two "HILO"s.

SCORING:

Tests 1 to 4 satisfy $N \leq 5000$ .
Tests 5 to 8 have a uniformly random permutation.
Tests 9 to 20 satisfy no further constraints.

Problem credits: Richard Qi

USACO 2021 December Contest, Gold Problem 2. HILO 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Andi Qu, Benjamin Qi)

To solve this problem in $O (N^{2})$ time, we can simulate the process for each $x$ .

#include <iostream>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int n, p[200001];
    std::cin >> n;
    for (int i = 0; i < n; i++) std::cin >> p[i];
    for (int x = 0; x <= n; x++) {
        int mn = 0, mx = n + 1, ans = 0;
        bool hi = false;
        for (int i = 0; i < n; i++) {
            if (p[i] > mx || p[i] < mn) continue;
            if (p[i] > x) {
                hi = true;
                mx = p[i];
            } else {
                ans += hi;
                hi = false;
                mn = p[i];
            }
        }
        std::cout << ans << '\n';
    }
    return 0;
}

Another solution that takes $O (N^{2})$ time in the worst case is to keep track of each "HI" and "LO" for each $x$ , and then go through the 2 lists to find the number of "HILO" pairs. However, this solution passes the test cases with data generated uniformly at random because the expected number of "HI"s and "LO"s is $O (\log N)$ for each $x$ , resulting in an overall expected runtime of $O (N \log N)$ .

To keep track of the 2 lists, we can use 2 monotone stacks. Essentially, we maintain a sorted list of indices where Bessie says "LO". When we transition from $x$ to $x + 1$ , we know that the last "LO" that Bessie will say will be to $x + 1$ . If Bessie doesn't say "LO" to $k$ while thinking of $x + 1$ , then she will never say "LO" to some $k$ while thinking of $y > x + 1$ , so we can remove all "LO"s that used to be said after the index of $x + 1$ in the permutation.

Conveniently, the indices that we remove form a suffix of the list (because the list is sorted), so we can use a stack and pop elements from it. Since each index is pushed into and popped from the stack at most once, this takes $O (N)$ time overall; iterating through the stack for each $x$ takes a further $O (N)$ time per element.

Here's a C++ code snippet for finding the list of "LO"s for each $x$ :

std::vector<int> los[200001];
for (int i = 1; i <= n; i++) {
    los[i] = los[i - 1];
    while (los[i].size() != 0 && los[i].back() > pos[i]) los[i].pop_back();
    los[i].push_back(pos[i]);
}

(Bonus: Find out how the rest of the test data for this problem was generated.)

To solve the problem in $O (N)$ time, we need a way to efficiently transition from $x$ to $x + 1$ .

Full Solution 1:

Claim: Let $p$ be the given permutation. If index $i$ is the "LO" in a "HILO" pair, then the "HI" in the pair must be the index $k$ such that $k < i$ , $p [k] > p [i]$ , and $p [k]$ is minimal.

Proof: If no such $k$ exists, then there is no greater element before $i$ , so $i$ can't be the "LO" in a "HILO" pair. If Bessie says "LO" to $p [k]$ , then Elsie will not guess $p [i]$ , so $i$ can't be the "LO" in a "HILO" pair. Otherwise, the last "HI" that Bessie says, before saying "LO" to $p [i]$ , must be to $p [k]$ .

Knowing this, we can compute an array $prv$ where $prv [i] = k$ as described above using a monotone stack.

Claim: Let index $j$ be the last "LO" before Bessie says "LO" to $p [i]$ . For each $x$ where Elsie doesn't skip $p [i]$ , $j$ is the same.

Proof: Let $j_{1} < j_{2} < i$ and $p [j_{1}], p [j_{2}] < p [i]$ . If Bessie says "LO" to $p [i]$ , then there are 3 possibilities:

Bessie never says "LO" to either $p [j_{1}]$ or $p [j_{2}]$ because she already said "LO" at some index $k < j_{1}$ where $p [k] > p [j_{1}], p [j_{2}]$ .
Bessie always says "LO" to $p [j_{1}]$ but never to $p [j_{2}]$ because she said "LO" at some index $j_{1} \leq k < j_{2}$ where $p [k] > p [j_{2}]$ .
Bessie always "LO" to both $p [j_{1}]$ and $p [j_{2}]$ because neither of the above happen.

If transitioning causes Bessie to stop saying "LO" to some index before $i$ , then it must also cause her to stop saying "LO" to $p [i]$ too. Therefore, $j$ is the same for each $p [i]$ .

Claim: Let $j$ be defined as above. Index $i$ is the "LO" in a "HILO" pair if and only $prv [i]$ exists, and $j$ doesn't exist or $prv [i] \neq prv [j]$ .

Proof: If $prv [i]$ doesn't exist, then Bessie never says "HI" before saying "LO" to $p [i]$ , so it can't be the "LO" in a "HILO" pair. Otherwise, if $prv [i] \neq prv [j]$ , then the last "HI" that Bessie says before saying "LO" to $p [i]$ must be after saying "LO" to $p [j]$ by definition. In this case, index $i$ is the "LO" in a "HILO" pair.

Knowing this, we can then determine, once for each index, whether it's the "LO" in a "HILO" pair, and thus how many "HILO" pairs there are for each $x$ .

Andi's code:

#include <iostream>
#include <stack>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int n, pos[200001], prv[200001];
    bool hilo[200001];
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        int p;
        std::cin >> p;
        pos[p] = i;
    }

    std::stack<int> stck;
    stck.push(0);
    for (int i = n; i > 0; i--) {
        while (stck.top() > pos[i]) stck.pop();
        prv[pos[i]] = stck.top();
        stck.push(pos[i]);
    }
    while (stck.size() != 1) stck.pop();

    std::cout << "0\n";
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        while (stck.top() > pos[i]) {
            cnt -= hilo[stck.top()];
            stck.pop();
        }
        hilo[pos[i]] = prv[pos[i]] != 0 &&
                       (stck.top() == 0 || prv[pos[i]] != prv[stck.top()]);
        stck.push(pos[i]);
        cnt += hilo[pos[i]];
        std::cout << cnt << '\n';
    }
    return 0;
}

Full Solution 2: Another way we can solve this problem in $O (N \log N)$ time is with stacks plus a sorted set.

First, we compute, for each $x \to x + 1$ event, which elements of the permutation start and stop becoming "HI"s and "LO"s. We can do this with a stack.

Next, we process the events for each $x$ . We can maintain an ordered map of "HI"s and "LO"s, and inserting or erasing any element from that map changes a constant number of "HILO" pairs. Using C++'s iterators, we can process these changes efficiently.

Ben's code:

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

template <class T> using V = vector<T>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int N;
	cin >> N;
	V<int> P(N);
	for (auto &t : P) {
		cin >> t;
		--t;
	}
	V<int> pos(N);
	for (int i = 0; i < N; ++i)
		pos[P[i]] = i;
	V<V<pair<int, char>>> to_ins(N + 1);
	V<V<int>> to_del(N + 1);
	{ // process "LO"s from lowest to highest, record insertions and deletions
		stack<int> cur;
		for (int i = 0; i < N; ++i) {
			while (!cur.empty() && cur.top() > pos[i]) {
				to_del.at(i + 1).push_back(cur.top());
				cur.pop();
			}
			cur.push(pos[i]);
			to_ins.at(i + 1).push_back({pos[i], 'L'});
		}
	}
	{ // process "HI"s from highest to lowest, record insertions and deletions
		stack<int> cur;
		for (int i = N - 1; i >= 0; --i) {
			while (!cur.empty() && cur.top() > pos[i]) {
				to_ins.at(i + 1).push_back({cur.top(), 'H'});
				cur.pop();
			}
			cur.push(pos[i]);
			to_del.at(i + 1).push_back(pos[i]);
		}
		while (!cur.empty()) {
			to_ins.at(0).push_back({cur.top(), 'H'});
			cur.pop();
		}
	}
	int ans = 0;
	map<int, char> m; // maps each position to 'H' or 'L'
	auto hilo = [&](map<int, char>::iterator it,
					map<int, char>::iterator next_it) {
		return it->second == 'H' && next_it->second == 'L';
	};
	auto get_dif = [&](map<int, char>::iterator it) {
		int dif = 0;
		if (it != begin(m))
			dif += hilo(prev(it), it);
		if (next(it) != end(m))
			dif += hilo(it, next(it));
		if (it != begin(m) && next(it) != end(m))
			dif -= hilo(prev(it), next(it));
		return dif;
	};
	for (int i = 0; i <= N; ++i) { // to finish, go from lowest to highest again
		for (auto &t : to_del.at(i)) {
			auto it = m.find(t);
			assert(it != end(m));
			ans -= get_dif(it);
			m.erase(it);
		}
		for (auto &t : to_ins.at(i)) {
			auto it = m.insert(t).first;
			assert(it->second);
			ans += get_dif(it);
		}
		cout << ans << "\n";
	}
}

Full Solution 3: Here is a simpler solution that also runs in $O (N \log N)$ . This one doesn't explicitly make use of monotonic stacks, though it is possible to modify it to run in $O (N)$ time with them.

Allen Wu's code:

#include <iostream>
#include <map>
#include <set>
#include <utility>
#include <vector>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; ++i)
		cin >> arr[i];
	vector<int> pos(n + 1);
	for (int i = 0; i < n; ++i)
		pos[arr[i]] = i;
	map<int, int> existing;
	vector<int> changes(n + 1);
	for (int i = 0; i < n; ++i) {
		int num = arr[i];
		// goal is to compute how the number of HILOs changes
		// when we go from x = num-1 to x = num
		auto it = existing.upper_bound(num);
		if (it != existing.end()) {
			// add one if num is involved in a HILO when x = num
			if (it == existing.begin())
				++changes[num];
			else if (it->second > prev(it)->second)
				++changes[num];
		}
		// subtract one if num is involved in a HILO when x = num-1
		if (pos[num - 1] > pos[num])
			--changes[num];
		existing[num] = i;
	}
	int sum = 0;
	for (int i = 0; i <= n; ++i) {
		sum += changes[i];
		cout << sum << "\n";
	}
}

[/hide]