2025 January USACO Bronze Problems/Problem 2
Contents
Problem
Problem
Farmer John is trying to describe his favorite USACO contest to Elsie, but she is having trouble understanding why he likes it so much. He says "My favorite part of the contest was when Bessie said 'It's Mooin' Time' and mooed all over the contest."
Elsie still doesn't understand, so Farmer John downloads the contest as a text file and tries to explain what he means. The contest is defined as an array of N (1≤N≤10^6) integers a_1,a_2,…,a_N (1≤a_i≤N). Farmer John defines a moo as an array of three integers where the second integer equals the third but not the first. A moo is said to occur in the contest if it is possible to remove integers from the array until only the moo remains.
As Bessie allegedly "mooed all over the contest", help Elsie count the number of distinct moos that occur in the contest! Two moos are distinct if they do not consist of the same integers in the same order.
Input Format
The first line contains N.
The second line contains N space-separated integers a_1,a_2,…,a_N.
Output Format
Output the number of distinct moos that occur in the contest.
Sample Input
6 1 2 3 4 4 4
Sample Output
3
Scoring
Inputs 2-4: N≤10^2
Inputs 5-7: N≤10^4
Inputs 8-11: No additional constraints.
Solution
Imagine that some integer o appears more than two times. Any moo of the form [m,o,o] that exists can always be constructed using the rightmost two occurrences of o in the original array.
This motivates the following O(N^2) solution - scan over the array from right to left and keep track of how many times each integer has been seen. When we see an integer for the second time, count the number of distinct different integers to the left of that one. The sum of these counts is therefore the answer.
