# Cow Frisbee, 2022 Jan Silver

Could any one explain the logic about “pre[n] = p” and “nex[p] = n” in the official link list solution? For sure this solution is correct. I am just not clear how to understand this logic. Could anyone provide a comments/example in more detail?

vector with_h(N+1);
for (int i = 0; i < N; ++i) with_h[h[i]] = i;
vector pre(N), nex(N);
for (int i = 0; i < N; ++i) {
pre[i] = i-1;
nex[i] = i+1;
}
for (int cur_h = 1; cur_h <= N; ++cur_h) {
int pos = with_h[cur_h];
int p = pre[pos], n = nex[pos];
if (n != N) ans += n-pos+1, pre[n] = p;
if (p != -1) nex[p] = n;
}
}

Subtask: You can solve the problem in O(N^2) by brute forcing over every possible pair (i, j) and adding j - i + 1 to the total if every single cow between cows i and j have a height less than \min(h_i, h_j).

Full Solution: Suppose that you fix the cow at position j as the cow with \min(h_i, h_j). Since h is a permutation of 1 \ldots N, it is guaranteed that h will only contain unique cow heights! Since h_j is fixed as the minimum of the two cow heights and h only stores unique cow heights, we can ensure that h_i > h_j. Suppose that we had another cow at position k to the left of the cow at position i that satisfied h_k > h_i. The pair (k, i) would not be a valid pair of cows to throw the frisbee back and forth to, since h_i > h_j and h_j is \min(h_k, h_j).

This indicates that there will be at most one cow at position i for every cow at position j, such that cows at positions i and j can throw the frisbee back forth to each other.
Similarly, this also indicates that there will be at most one at position j, for every cow at the position, i, using similar reasoning.

To find the position i such that the cow at position j can throw to the cow located at position i, we can use a monotonic stack to find the closest index i at which h_i > h_j is satisfied in O(N) time. Similar reasoning holds for fixing cow i as the cow with \min(h_i, h_j). You can find an easier version of a similar problem here or a trickier problem, which I wrote here.

Problem 2 Code:

``````#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pl = pair<ll, ll>;
using vl = vector<ll>;

#define forn(i, n) for(ll i = 0; i < n; i++)
#define rofn(i, n) for(ll i = n - 1; i >= 0; i--)
#define f first
#define s second

int main(){
ll n; cin >> n;
vl h(n), l(n), r(n);
stack<pl> st1, st2;
forn(i, n){
cin >> h[i];
l[i] = i, r[i] = i;
}
forn(i, n){
while(!st1.empty()){
if(st1.top().f > h[i]){
l[i] = st1.top().s;
break;
} else {
st1.pop();
}
}
st1.push({h[i], i});
}
rofn(i, n){
while(!st2.empty()){
if(st2.top().f > h[i]){
r[i] = st2.top().s;
break;
} else {
st2.pop();
}
}
st2.push({h[i], i});
}
ll res = 0;
forn(i, n){
if(i != l[i]){
res += (i - l[i] + 1);
}
if(i != r[i]){
res += (r[i] - i + 1);
}
}
cout << res << endl;
}
``````
1 Like

Not sure how the above post answers the OP.

Does this help? Delete a node in a Doubly Linked List - GeeksforGeeks

Have you tried running the code on the sample case and verifying that the pairs that are added to the answer are precisely those described in the problem statement?

2 Likes