USACO Gold 2017 January - Balanced Photo

Official Analysis

The official solution uses a binary indexed tree.

An alternative solution uses an order statistic tree. This is provided in C++ with the PBDS data structure; in Java you'll have to implement your own.

Solution (C++ only)

Time Complexity: $\mathcal O(N \log N)$

We aim to quickly determine, for each cow, the number of taller cows to its left and right.

To do this, we can sweep through the cows from left to right and maintain two balanced binary search trees: one for storing the heights of cows on each side of the current cow. Then, use binary search to count the number of heights in each set that are greater than the height of the current cow.

We can use order statistic trees to achieve this in $\mathcal O(N \log N)$ time.

Copy
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>  // for policy-based data structures
using namespace __gnu_pbds;               // for policy-based data structures
using namespace std;

typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    indexed_set;  // indexed_set -> order_of_key & find_by_order
int N, h, ans;
vector<int> height;