Counting Distinct Moos

Question

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≤106
) integers a1,a2,…,aN
(1≤ai≤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 (input arrives from the terminal / stdin):
The first line contains N
.
The second line contains N
space-separated integers a1,a2,…,aN
.

OUTPUT FORMAT (print output to the terminal / stdout):
Output the number of distinct moos that occur in the contest.
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" in Java, a "long long" in C/C++).

SAMPLE INPUT:
6
1 2 3 4 4 4
SAMPLE OUTPUT:
3
This contest has three distinct moos: "1 4 4", "2 4 4", and "3 4 4".

SCORING:
Inputs 2-4: N≤102
Inputs 5-7: N≤104
Inputs 8-11: No additional constraints.

in c++

Answer 1

To solve this problem, we need to count the number of distinct "moos" in the contest array. A "moo" is defined as a triplet $(x, y, y)$ where $x \neq y$ and this triplet appears as a subsequence in the array. Two moos are considered distinct if they consist of different $x$ and $y$ values.

Step-by-Step Solution:

Identify the Second Occurrence of Each Element:
- For each element $y$ in the array, determine the position of its second occurrence (if it exists). This is crucial because a valid "moo" requires two $y$ 's following an $x$ .
Compute Prefix Sums for Unique Elements:
- Create a prefix array where prefix[i] represents the number of unique elements up to the $i$ -th position in the array. This helps in efficiently counting how many distinct $x$ 's exist before the second occurrence of any $y$ .
Count Valid Moos:
- For each $y$ that appears at least twice, the number of valid $x$ 's that can form a "moo" with $y$ is given by prefix[p2[y] - 1] - 1. Here, p2[y] is the position of the second occurrence of $y$ , and we subtract 1 to exclude $y$ itself.
Sum Up All Valid Moos:
- The total number of distinct moos is the sum of valid moos for all $y$ that appear at least twice.

Implementation:

Below is the C++ implementation of the above approach. The code efficiently handles large inputs by using fast I/O methods and optimizing memory usage.

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

typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    vector<int> a(N+1);
    for(int i=1;i<=N;i++) cin >> a[i];
    
    // Step 1: Find p2[y]
    vector<int> p2(N+1, 0);
    vector<int> count_y(N+1, 0);
    for(int i=1;i<=N;i++){
        int y = a[i];
        if(count_y[y] ==1 && p2[y]==0){
            p2[y] = i;
        }
        count_y[y]++;
    }
    
    // Step 2: Compute prefix[i]
    vector<int> seen(N+1, 0);
    vector<int> prefix(N+1, 0);
    int count_unique =0;
    for(int i=1;i<=N;i++){
        int y = a[i];
        if(!seen[y]){
            seen[y] =1;
            count_unique++;
        }
        prefix[i] = count_unique;
    }
    
    // Step 3: Iterate over y and sum
    ll ans =0;
    for(int y=1;y<=N;y++){
        if(p2[y] !=0){
            if(p2[y]-1 >=0){
                ans += (ll)(prefix[p2[y]-1] -1);
            }
        }
    }
    
    cout << ans;
}

Explanation of the Code:

Input Handling:
- The code reads the number of elements $N$ and the array elements.
Finding Second Occurrences:
- It iterates through the array to find the second occurrence (p2[y]) of each element $y$ .
Prefix Array Construction:
- It constructs a prefix array that keeps track of the number of unique elements encountered up to each position in the array.
Counting Distinct Moos:
- For each $y$ with a valid second occurrence, it calculates the number of valid $x$ 's and adds to the total count of distinct moos.
Output:
- Finally, it outputs the total number of distinct moos.

Sample Input and Output:

Input:

text
6
1 2 3 4 4 4

Output:

This corresponds to the three distinct moos: (1, 4), (2, 4), and (3, 4).

Counting Distinct Moos

Question

Thought

Answer

Step-by-Step Solution:

Implementation:

Explanation of the Code:

Sample Input and Output:

Share this Q&A