Official Analysis (C++, Java, Python)

Explanation

Let $a_{i}$ be the hay cow $i$ likes.

If there are adjacent hays such that $a_{i} = a_{i+1}$, we can run a focus group on $i, i+1, i+2$ or $i-1, i, i+1$. This will result in cow $i$ and $i+1$ infecting cow $i+2$ or $i-1$ with the type of hay they like. We can keep running focus groups like this to eventually infect every cow with hay $a_{i}$.

Situations where $a_{i} = a_{i+2}$ will also create adjacent hays of the same type (by running a focus group on $i,i+1, i+2$) and therefore this also makes $a_{i}$ part of the answer.

Implementation

Time Complexity: $\mathcal{O}(N)$

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

int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n;
		cin >> n;
		vector<int> hay(n);