United Cows of Farmer John USACO 2021 US

United Cows of Farmer John USACO

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.

See Also : USACO 2021 Challenges

The delegation will consist of a contiguous interval of at least three cows – that is, cows l…rl…r for integers ll and rr satisfying 1≤l<r≤N1≤l<r≤N and r−l≥2r−l≥2. Three of the cows in the chosen interval are marked as delegation leaders. For legal reasons, the two outermost cows of the chosen interval must be leaders. Moreover, 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. Two delegations are considered different if they have different members or different leaders.

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

The first line contains NN.

The second line contains NN integers b1,b2,…,bNb1,b2,…,bN, each in the range [1,N][1,N].

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

The number of possible delegations, on a single line.

Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a “long long” in C/C++).

SAMPLE INPUT:

7
1 2 3 4 3 2 5

SAMPLE OUTPUT:

9

Each delegation corresponds to one of the following triples of leaders:(1,2,3),(1,2,4),(1,3,4),(1,4,7),(2,3,4),(4,5,6),(4,5,7),(4,6,7),(5,6,7).(1,2,3),(1,2,4),(1,3,4),(1,4,7),(2,3,4),(4,5,6),(4,5,7),(4,6,7),(5,6,7).

SCORING:

  • Test cases 1-2 satisfy N≤50N≤50.
  • Test cases 3-4 satisfy N≤500N≤500.
  • Test cases 5-8 satisfy N≤5000N≤5000.
  • Test cases 9-20 satisfy no additional constraints.

Problem credits: 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 iterate over all possible ll in decreasing order. Let uniquel,runiquel,r equal the number of cows in the interval l…rl…r whose breeds are unique within that interval. When we decrease ll by one,

  • If Bl=BrBl=Br, then cow rr cannot be a leader in l…rl…r. Break.
  • If BlBl is unique in the range l…rl…r, then add uniquel+1,r−1uniquel+1,r−1 to the answer and set uniquel,r−1=uniquel+1,r−1+1uniquel,r−1=uniquel+1,r−1+1.
  • If BlBl occurs exactly once in the range l+1…rl+1…r, then BlBl was unique in l+1…rl+1…r but not l…rl…r. Set uniquel,r−1=uniquel+1,r−1−1uniquel,r−1=uniquel+1,r−1−1.
#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<int> occ(N+1);
		int unique = 0;
		for (int l = r-1; l >= 0; --l) {
			if (B[l] == B[r]) break;
			int& o = occ[B[l]]; ++o;
			if (o == 1) {
				ans += unique;
				++unique;
			} else if (o == 2) {
				--unique;
			}
		}
	}
	cout << ans << "\n";
}

Essentially, we’re computing arrays activer[l]activer[l], uniquer[l]uniquer[l], valr[l]valr[l] for each rr from 0…N−10…N−1. For each l≤rl≤r, define

  • activer[l]=1activer[l]=1 if BlBl is unique among Bl,Bl+1,…,BrBl,Bl+1,…,Br, and 00 otherwise.
  • uniquer[l]=uniquel+1,r−1uniquer[l]=uniquel+1,r−1.
  • valr[l]=activer[l]⋅uniquel+1,r−1valr[l]=activer[l]⋅uniquel+1,r−1.

For every rr, we add a suffix of valrvalr to the answer.

To solve this problem in O(NlogN)O(Nlog⁡N) time, we must be able to efficiently transition from r−1r−1 to rr. Define prev_oc[j]prev_oc[j] to equal the maximum index i<ji<j such that Bi=BjBi=Bj. activeractiver and uniqueruniquer are the same as activer−1activer−1 and uniquer−1uniquer−1 respectively except for the following changes:

  • activer[r]=1activer[r]=1.
  • activer[prev_oc[r]]=0activer[prev_oc[r]]=0.
  • uniquer[prev_oc[r]…r−1]uniquer[prev_oc[r]…r−1] must be incremented by 11.
  • uniquer[prev_oc[prev_oc[r]]…prev_oc[r]−1]uniquer[prev_oc[prev_oc[r]]…prev_oc[r]−1] must be decremented by 11.

These updates and range sum queries over valrvalr can be supported in O(logN)O(log⁡N) time each using a segment tree with lazy propagation. At each segment x…yx…y of the tree, maintain ∑yi=xactiver[i]∑i=xyactiver[i], ∑yi=xvalr[i]∑i=xyvalr[i], and a lazy value that the values of all active indices in the segment should be increased by. You can check the analysis for Counting Haybales for an introduction to lazy segment trees.

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

using T = uint64_t;
const int SZ = 1<<18;

struct LazySeg {
	T sum[2*SZ], lazy[2*SZ], num_active[2*SZ];
	LazySeg() {
		for (int i = 0; i < SZ; ++i) 
			num_active[SZ+i] = 1;
		for (int i = SZ-1; i > 0; --i) 
			num_active[i] = num_active[2*i]+num_active[2*i+1];
	}
	void push(int ind, int L, int R) {
		sum[ind] += num_active[ind]*lazy[ind];
		if (L != R) for (int i = 0; i < 2; ++i) 
			lazy[2*ind+i] += lazy[ind];
		lazy[ind] = 0;
	}
	void pull(int ind) {
		sum[ind] = sum[2*ind]+sum[2*ind+1];
		num_active[ind] = num_active[2*ind]+num_active[2*ind+1];
	}
	void increment(int lo,int hi, int val, int ind=1,int L=0, int R=SZ-1) {
		push(ind,L,R); if (hi < L || R < lo) return;
		if (lo <= L && R <= hi) { 
			lazy[ind] = val; push(ind,L,R); return; }
		int M = (L+R)/2; 
		increment(lo,hi,val,2*ind,L,M); 
		increment(lo,hi,val,2*ind+1,M+1,R); 
		pull(ind);
	}
	T query(int lo, int hi, int ind=1, int L=0, int R=SZ-1) {
		push(ind,L,R); 
		if (lo > R || L > hi) return 0;
		if (lo <= L && R <= hi) return sum[ind];
		int M = (L+R)/2;
		return query(lo,hi,2*ind,L,M)+query(lo,hi,2*ind+1,M+1,R);
	}
	void deactivate(int pos, int ind=1, int L=0, int R=SZ-1) {
		push(ind,L,R); 
		if (pos > R || L > pos) return;
		if (pos <= L && R <= pos) {
			assert(num_active[ind] == 1);
			sum[ind] = num_active[ind] = 0;
			return;
		}
		int M = (L+R)/2; 
		deactivate(pos,2*ind,L,M);
		deactivate(pos,2*ind+1,M+1,R);
		pull(ind);
	}
} Seg;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int N; cin >> N;
	vector<int> B(N); for (int& b: B) cin >> b;
	vector<int> last(N+1,-1), prev_oc(N);
	int64_t ans = 0;
	for (int r = 0; r < N; ++r) {
		int& last_oc = last[B[r]];
		ans += Seg.query(last_oc+1,SZ-1);
		if (last_oc != -1) {
			Seg.deactivate(last_oc);
			Seg.increment(prev_oc[last_oc],last_oc-1,-1);
		}
		Seg.increment(last_oc,r-1,1);
		prev_oc[r] = last_oc; last_oc = r;
	}
	cout << ans << "\n";
}

Danny Mittal’s code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class TriplesOfCows {
 
    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[] last2 = new int[n + 1];
        int[] last = new int[n + 1];
        long answer = 0;
        SegmentTree segTree = new SegmentTree(n);
        for (int j = 1; j <= n; j++) {
            int k = Integer.parseInt(tokenizer.nextToken());
            segTree.updateSingle(last[k], -1);
            segTree.updateRange(last2[k] + 1, last[k] - 1, -1);
            answer += segTree.query(last[k] + 1, j - 1);
            segTree.updateRange(last[k] + 1, j - 1, 1);
            segTree.updateSingle(j, 1);
            last2[k] = last[k];
            last[k] = j;
        }
        System.out.println(answer);
    }
 
    static class SegmentTree {
        final int n;
        final long[] value = new long[530000];
        final long[] singles = new long[530000];
        final long[] lazy = new long[530000];
 
        SegmentTree(int n) {
            this.n = n;
        }
 
        void propagate(int node) {
            value[2 * node] += lazy[node] * singles[2 * node];
            value[(2 * node) + 1] += lazy[node] * singles[(2 * node) + 1];
            lazy[2 * node] += lazy[node];
            lazy[(2 * node) + 1] += lazy[node];
            lazy[node] = 0;
        }
 
        void updateSingle(int index, long delta, int node, int segFrom, int segTo) {
            if (segFrom == segTo) {
                value[node] += delta * lazy[node];
                singles[node] += delta;
            } else {
                propagate(node);
                int mid = (segFrom + segTo) / 2;
                if (index <= mid) {
                    updateSingle(index, delta, 2 * node, segFrom, mid);
                } else {
                    updateSingle(index, delta, (2 * node) + 1, mid + 1, segTo);
                }
                value[node] = value[2 * node] + value[(2 * node) + 1];
                singles[node] = singles[2 * node] + singles[(2 * node) + 1];
            }
        }
 
        void updateSingle(int index, long delta) {
            if (index > 0) {
                updateSingle(index, delta, 1, 1, n);
            }
        }
 
        void updateRange(int from, int to, long delta, int node, int segFrom, int segTo) {
            if (segTo < from || to < segFrom) {
 
            } else if (from <= segFrom && segTo <= to) {
                value[node] += delta * singles[node];
                lazy[node] += delta;
            } else {
                propagate(node);
                int mid = (segFrom + segTo) / 2;
                updateRange(from, to, delta, 2 * node, segFrom, mid);
                updateRange(from, to, delta, (2 * node) + 1, mid + 1, segTo);
                value[node] = value[2 * node] + value[(2 * node) + 1];
                singles[node] = singles[2 * node] + singles[(2 * node) + 1];
            }
        }
 
        void updateRange(int from, int to, long delta) {
            updateRange(from, to, delta, 1, 1, n);
        }
 
        long query(int from, int to, int node, int segFrom, int segTo) {
            if (segTo < from || to < segFrom) {
                return 0;
            } else if (from <= segFrom && segTo <= to) {
                return value[node];
            } else {
                propagate(node);
                int mid = (segFrom + segTo) / 2;
                return query(from, to, 2 * node, segFrom, mid) + query(from, to, (2 * node) + 1, mid + 1, segTo);
            }
        }
 
        long query(int from, int to) {
            return query(from, to, 1, 1, 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