USACO 2021 US Open, Gold Problem 1. United Cows of Farmer John

USACO 2021 US Open, Gold Problem 1. United Cows of Farmer John

The United Cows of Farmer John (UCFJ) are sending a delegation to the International bOvine olympIad (IOI).

There are NN cows participating in delegation selection (1≤N≤2⋅1051≤N≤2⋅105). They are standing in a line, and cow ii has breed bibi.

The delegation will consist of a contiguous interval of at least two cows - that is, cows l…rl…r for integers ll and rr satisfying 1≤l<r≤N1≤l<r≤N. The two outermost cows of the chosen interval will be designated as "leaders." To avoid intra-breed conflict, every leader must be of a different breed from the rest of the delegation (leaders or not).

Help the UCFJ determine (for tax reasons) the number of ways they might choose a delegation to send to the IOI.

 

 

 

SAMPLE INPUT:

7
1 2 3 4 3 2 5

SAMPLE OUTPUT:

13

Each delegation corresponds to one of the following pairs of leaders:

 

 

Problem credits: Benjamin Qi

USACO 2021 US Open, Gold Problem 1. United Cows of Farmer John 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

Note: I index the cows as 0…N−10…N−1 rather than 1…N1…N.

To solve this problem in O(N2)O(N2) time, fix rr and count the number of ll such that both cows and ll and rr can be leaders. We do this by iterating over all possible ll in decreasing order.

 

• If Bl=BrBl=Br, then cow rr cannot be a leader in l…rl…r. Break.
• Otherwise, if BlBl is unique in the range l…rl…r, then we increment the answer by one.

My code:

 

#include<bits/stdc++.h>
using namespace std;
 
int main() {
	int N; cin >> N;
	vector<int> B(N); for (int& b: B) cin >> b;
	int64_t ans = 0;
	for (int r = 0; r < N; ++r) {
		vector<bool> occ(N+1);
		for (int l = r-1; l >= 0; --l) {
			if (B[l] == B[r]) break;
			if (!occ[B[l]]) {
				++ans;
				occ[B[l]] = 1;
			}
		}
	}
	cout << ans << "\n";
}

To solve this problem in O(NlogN)O(Nlog⁡N) time, for each l≤rl≤r define activer[l]activer[l] to equal 11 if cow ll's breed is unique in the range l…rl…r, and 00 otherwise. Also let prev_oc[j]prev_oc[j] equal the maximum index i<ji<j such that Bi=BjBi=Bj.

For each rr, we need to sum activer[l]activer[l] over all l∈[prev_oc[r]+1,r−1]l∈[prev_oc[r]+1,r−1]. Note that activer[l]=activer−1[l]activer[l]=activer−1[l] for almost all ll, aside from for l=rl=r and l=prev_oc[r]l=prev_oc[r]. Therefore, when transitioning from r−1r−1 to rr, we need to make up to two point updates while allowing range sum queries over activeactive. This can be done using a data structure such as a binary indexed tree.

Danny Mittal's code:

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class PairsOfCows {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        int[] last = new int[n + 1];
        long answer = 0;
        BinaryIndexTree bit = new BinaryIndexTree(n);
        for (int j = 1; j <= n; j++) {
            int k = Integer.parseInt(tokenizer.nextToken());
            if (last[k] != 0) {
                bit.update(last[k], -1L);
            }
            answer += bit.query(j) - bit.query(last[k]);
            last[k] = j;
            bit.update(j, 1L);
        }
        System.out.println(answer);
    }
 
    static class BinaryIndexTree {
        final int n;
        final long[] bit;
 
        BinaryIndexTree(int n) {
            this.n = n;
            this.bit = new long[n + 1];
        }
 
        void update(int j, long delta) {
            for (; j <= n; j += j & -j) {
                bit[j] += delta;
            }
        }
 
        long query(int j) {
            long res = 0;
            for (; j > 0; j -= j & -j) {
                res += bit[j];
            }
            return res;
        }
    }
}

Alternatively, use an order statistic tree (also mentioned in the link above).

My code:

 

#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>,
	rb_tree_tag, tree_order_statistics_node_update>;
 
int main() {
	int N; cin >> N;
	Tree<int> T;
	vector<int> last_oc(N+1,-1);
	int64_t ans = 0;
	for (int i = 0; i < N; ++i) {
		int b; cin >> b;
		ans += T.size()-T.order_of_key(last_oc[b]+1);
		T.insert(i);
		if (last_oc[b] != -1) T.erase(last_oc[b]);
		last_oc[b] = i;
	}
	cout << ans << "\n";
}

[/hide]